2017_11_24<백준>2504번 괄호의 값 (c++)

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

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

문제 해결 과정:

-(,[ 일때는 스택에 넣는다

-],) 일때는 두가지 경우로 나눈다: 1.스택의 top이 [,( 일때 : 3또는 2를 스택에 push

2.스택의 top이 숫자일때: CalculateStack에서 result값을 얻는다.

-스택의 top이 숫자이면 괄호가 나올때까지 숫자를 곱하고 괄호가 닫히면 다시 push한후 result를 return 한다

-정상적인 경우 괄호 읽기가 끝나면 스택에는 숫자만 남는다.

-마지막으로 스택에 모든 숫자를 더한다.

 

#include<iostream>
#include<stack>
#include<string>
using namespace std;
 
int CalculateResult(stack<string>& stack,string a, string b, int value) {
 
    int result = 0;
    while (!stack.empty()) {
        string top = stack.top();
        if (top == a) {
            return -1;
        }
        else if (top == b) {
            stack.pop();
            result *= value;
            stack.push(to_string(result));
            break;
        }
        else {
            result += atoi(top.c_str());
            stack.pop();
        }
    }
    return result;
}
 
int main() {
 
    string a;
    stack<string> b;
    cin >> a;
    int sum = 0;
    int ans = 0;
    int check=0;
 
    for (int i = 0; i < a.length(); i++) {
        if (check == -1) {
            break;
        }
        string temp = a.substr(i, 1);
        if (temp == "(" || temp == "[")
        {
            b.push(temp);
        }
        else if (temp == ")") {
            if (b.top() == "(")
            {    
                b.pop();
                b.push("2");
            }
            else {
 
                check =CalculateResult(b,"[","(",2);
                
            }
        }
        else if (temp == "]") {
            if (b.top() == "[")
            {
                b.pop();
                b.push("3");
            }
            else {
                check = CalculateResult(b, "(", "[", 3);
            }
        }
    }
 
 
    if (check == -1) {
        sum = 0;
    }
    else {
        while (!b.empty()) {
            if (b.top() == ")" || b.top() == "(" || b.top() == "[" || b.top() == "]") {
                sum = 0;
                break;
 
            } else{
                sum += atoi(b.top().c_str());
                b.pop();
            }
        }
        
    }
 
    cout << sum<<endl;
 
    return 0;
}