백준 2504번 : 괄호의 값 c++

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

2504번: 괄호의 값

스택의 활용(수식의 괄호 쌍) 문제이다.

💡접근 방법

스택이 단순히 문자만 가지고 있는게 아니라, 값도 같이 가지고 있으면 될 것 같다는 느낌. 분배 법칙을 이용해서 문제를 풀 수 있다.

제시된 예시 중 일부분을 살펴보자.

(()[[]])

이 문자열을 살펴보면, 2x(2+3x3)=22 로 계산되는데, 이는 결국 (2x2) + (2x3x3) 과 같다. 왼쪽 괄호가 나오면 num에 2나 3을 곱한 뒤 스택에 push하고, 오른쪽 괄호가 나오면 num을 2나 3으로 나눈 뒤 스택을 pop 한다. 이때 ( ( ) [ [ ] ] ) 빨간색으로 표시된 괄호처럼 괄호 값이 '( )' 또는 '[ ]'인 경우 num을 나눠주기 전에 답(sum) 에 더한다.

 

num: sum(괄호의 값)에 더하기 전 중간값을 계산하기 위한 변수(1로 초기화)

Case 분류

1. case '('

num에 2를 곱하고 스택에 '(' 를 push 한다.

2. case ')'

  1) 스택이 비어있거나 스택 top이 '(' 가 아닌 경우

   올바르지 못한 괄호열이므로 0을 출력하고 return한다.

  2) 이전 문자열이 '(' 일 경우

   괄호 값이 '('이므로 계산된 num 값을 sum에 더한 후 num을 2로 나눈다. 스택을 pop 한다.

  3) 이전 문자열이 '(' 가 아닐 경우 

   제일 안쪽 괄호, 즉 '( )' 형태가 아니므로 이미 sum에 값이 더해져 있는 상태이다. 따라서 sum에 값을 더하지 않고 num을 2로 나눈다.

   그 후 스택을 pop 한다.

3. case'[' , ']'

1,2 번 케이스와 유사하게 처리한다.

코드

string a;
stack<char> st;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a;
    int sum = 0;
    int num = 1;
    for(int i=0;i<a.size();i++){
        if(a[i]=='('){
            st.push(a[i]);
            num *=2;
        }
        else if(a[i]=='['){
            st.push(a[i]);
            num*=3;
        }
        else if(a[i]==')'){
            if(st.empty() || st.top() !='('){
                cout << 0;
                return 0;
            }
            if(a[i-1]=='(') sum+=num;
            st.pop();
            num /=2;
        }
        else{//a[i]==']'
            if(st.empty() || st.top() !='['){
                cout << 0;
                return 0;
            }
            if(a[i-1]=='[') sum+=num;
            st.pop();
            num /=3;
        }
    }
    if(st.empty()) cout << sum;
    else cout << 0;

 

    return 0;
}