BOJ - 2504번_괄호의 값

주어진 괄호열을 읽고 그 괄호값을 정의한대로 계산하여 출력하는 프로그램 작성하기

  • 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
  • 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
  • X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
    • ()’ 인 괄호열의 값은 2이다.
    • ‘[]’ 인 괄호열의 값은 3이다.
    • ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
    • ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
    • 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.


풀이

C++ STL stack을 이용하여 여는 괄호가 나오면 스택에 추가하고 sum에 2 또는 3을 곱한다.

닫힌 괄호가 나오면 sum을 2 또는 3으로 나누고, 만약 바로 이전의 문자가 짝을 이루는 열린 괄호였다면 ans에 sum만큼 더한다.

닫힌 괄호가 나욌는데 짝을 이루는 열린 괄호가 없거나 스택이 비어있을 경우, 올바르지 않은 괄호열이므로 check를 false로 바꿔준다.


소스코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	
	int sum = 1;
	int ans = 0;
	bool check = true;
	stack<char> st;
	
	for(int i=0; i<s.size(); i++) {
		if(s[i]=='(') {
			sum *= 2;
			st.push(s[i]);
		}
		else if(s[i]=='[') {
			sum *= 3;
			st.push(s[i]);
		}
		else if(s[i]==')') {
			if(st.empty() || st.top()!='(') {
				check = false;
				break;
			}
			else {
				if(s[i-1]=='(') {
					ans += sum;
				}
				sum /= 2;
				st.pop();
			}
		}
		else { // s[i]==']'
			if(st.empty() || st.top()!='[') {
				check = false;
				break;
			}
			else {
				if(s[i-1]=='[') {
					ans += sum;
				}
				sum /= 3;
				st.pop();
			}
		}
	}
	if(!check || !st.empty()) cout << "0\n";
	else cout << ans;
}