[BOJ 2504] 괄호의 값

스택의 괄호쌍 유형의 응용 버전.

처음에 괄호 안에 괄호가 들어있는 형태랑 닫힌 괄호 옆에 새로운 괄호가 있는 경우를 판단하는게 너무 어려웠다.그래서 보니까 일단 열린 괄호가 '(' 면 2를 곱해놓고 '[' 면 3을 곱해놓은 다음에, 스택에 문자를 넣는다.그리고 열린 괄호가 계속 나올때 까지 해당 괄호에 해당하는 숫자를 계속 곱하다가, 닫는 괄호가 나올 때가 중요한데, 한번 닫는 괄호가 나오면 지금까지 열린 괄호 만큼 곱해준걸 ans변수에 더한다. (이러면 이전 괄호 개수만큼 값을 고려할 수 있음)

 

그리고 닫는 만큼 계속 나눠주다가 다시 열린게 나오면 반복... 그 외에 경우는 모두 괄호쌍이 맞지 않으니까 ans = 0 넣어놓고 탈출하면 된다. 그리고 저 과정을 거쳐도 스택이 모두 안 비어질때가 있는데 그 땐 올바르지 않으니까 empty인지 체크하고 0 넣어주면 된다.

#include <bits/stdc++.h>
using namespace std;
string x;
stack<int> s;
int ans;
void solve() {
    int tmp = 1;
    char pre = ' ';
    for(int i = 0; i < x.length(); i++) {
        if(x[i] == '(' || x[i] == '[') {
            s.push(x[i]);
            if(x[i] == '(') tmp *= 2;
            else tmp *= 3;
        } else {
            if(x[i] == ')') {
                if(s.empty()) {
                    ans = 0;
                    break;
                }
                if(s.top() == '[') {
                    ans = 0;
                    break;
                }
                s.pop();
                if(pre == '(') {
                    ans += tmp;
                    tmp /= 2;
                } else {
                    tmp /= 2;
                }
            } else {
                if(s.empty()) {
                    ans = 0;
                    break;
                }
                if(s.top() == '(') {
                    ans = 0;
                    break;
                }
                s.pop();
                if(pre == '[') {
                    ans += tmp;
                    tmp /= 3;
                } else  {
                    tmp /= 3;
                }
            }
        }
        pre = x[i];
    }    
    if(!s.empty()) cout << 0;
    else cout << ans;
}
int main() {
    cin >> x;
    solve();
}