[백준 2504] 괄호의 값 (C++)

https://www.acmicpc.net/problem/2504

문제

주어진 올바른 괄호 문자열에 대해서만 규칙대로 값을 계산해서 출력하는 것

규칙은 (()[[]]) 이런 문자열이라면 2*(2+3*3) = 22 가 된다.

 

접근방법

다른 블로그들을 참고해서 풀었는데, 풀이 방법은 '겉 괄호는 본인이 끝날때까지 안쪽 괄호 모두에게 영향을 미친다'라고 생각하면 될 것 같다.

그리고 계산식을 모두 풀어서 최대한 긴 다항식으로 만든다. 가 포인트인듯

뭔말이냐면 위에서 2*(2+3*3) -> 2*2 + 2*3*3 으로 만든다는 것임

이걸 만드는 방향으로 코드를 짜서 풀었다.

 

따라서 tmp 변수를 선언해두고 answer 변수에 값을 더해가면서 풀어야 함

(, [ 가 나오면 우선 tmp에 2를 곱한다. 이제 앞으로 나오는 계산에는 모두 이 괄호가 영향을 준다.(값이 곱해져야함)

), ] 가 나올 때 우선 1. 올바른 괄호 문자열인지 확인하고 2. 완전 안쪽의 괄호인지 (()) << 이런 친구들 --> 그러면 우선 괄호 하나가 끝나는 건데, 여기서 다항식의 항이 하나 나오게 되므로 (그게 겉의 단항식 내부의 항이라고 할지라도,,) answer에 우선 여기까지의 값을 더해준다. 3. 올바른 괄호문자열이긴 하지만 완전 안쪽의 괄호가 아니라 내부에 무언가라도 포함하고 있는 괄호가 끝나는 것이므로 2나 3으로 tmp를 나눠준다 즉 본인의 영향력을 거둔다. (앞으로 계산되는 값에 본인의 값이 곱해지지 않음) 이때는 괄호가 끝나도 값을 더해주진 않는데 이미 안쪽에 있는 괄호의 값들이 더해질때 값이 반영되었기 때문

 

소스코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main(){
    string str;
    cin >> str;
    
    int tmp = 1;
    int ans = 0;
    stack<char> stack;

    for(int i = 0 ; i < str.size(); i++) {
        if (str[i] == '(') {
            stack.push('(');
            tmp *= 2;
        } else if (str[i] == '[') {
            stack.push('[');
            tmp *= 3;
        } else if (str[i] == ')') {
            if (stack.empty() || stack.top() != '('){
                ans = 0;
                break;
            } else if (str[i-1] == '(') {
                ans += tmp;
                tmp /= 2;
                stack.pop();
            } else {
                tmp /= 2;
                stack.pop();
            }
        } else {
            if(stack.empty() || stack.top() != '[') {
                ans = 0;
                break;
            } else if (str[i-1] == '[') {
                ans += tmp;
                tmp /= 3;
                stack.pop();
            } else {
                tmp /= 3;
                stack.pop();
            }
        }
    }
    
    if(!stack.empty())
        ans = 0;
    
    cout << ans;
    
    return 0;
}