BOJ 2504] 괄호의 값

[ 생각해야 할 점 ]

- 괄호의 짝이 맞을 때, 그 괄호는 어디에 있는 괄호인지 구분해야함 (+와 *의 차이를 위해)

-  연산을 하기 위해 따로 피연산자와 수를 넣는 스택이 필요한지 고민해야함

- 입력을 모두 받고 할지, 입력받으면서 할지 고민해야함

 

[ 첫번째 시도 ] 

- 연산을 모두 받고 계산하기로 함

- 연산을 하기 위한 피연산자와 연산자를 넣을 스택을 구비함

- 다음 조건을 생각해냄

 

(*가 오는 경우)

- (나 [가 들어오면

 

(+가 오는 경우)

- 쌍이 맞아 pop한 후, 여는 괄호가 들어올때

 

(연산하는 경우)

- *이 스택에 들어올때

- 스택이 비었을 때

 

 

 

코드가 너무 길어지고, 복잡해서 그냥 int 변수에 연산을 하기로 결정

#include <iostream>
#include <stack>
#include <queue>

#include <vector>

using namespace std;

stack<char> charStk;
stack<char> symStk;
stack<int> intStk;

string str;
bool chk = false;

void calc() {
    int a = intStk.top();
    intStk.pop();
    int b = intStk.top();
    intStk.pop();
    int sym = symStk.top();
    symStk.pop();

    if (sym == '*') {
        intStk.push(a * b);
    }if (sym == '+') {
        intStk.push(a + b);
    }
    
}

bool error(char top) {
    cout << top << endl;
    cout << charStk.top() << endl;
    if (top == ')' && charStk.top() != '(')
        return true;
    if (top == ']' && charStk.top() != '[')
        return true;
    
    return false;
}

int main()
{
    cin >> str;

    intStk.push(1);

    for (int i = 0; i < str.length(); i++) {
        if (charStk.empty()) break;

        if (str[i] == '(') {
            if (chk) {
                symStk.push('+');
                chk = false;
            }

            if (charStk.empty()) {
                while (!symStk.empty())
                    calc();
            }
            charStk.push(str[i]);
            symStk.push('*');
            intStk.push(2);
            
            calc();
        }
        else if (str[i] == '[') {
            if (chk) {
                symStk.push('+');
                chk = false;
            }

            if (charStk.empty()) {
                while(!symStk.empty())
                    calc();
            }
            charStk.push(str[i]);
            symStk.push('*');
            intStk.push(3);
            
            calc();
        }
        else if (str[i] == ')') {
            if (error(str[i])) {
                cout << 0;
                return 0;
            }
            
            charStk.pop();
            
            chk = true;
            
        }
        else if (str[i] == ']') {
            if (error(str[i])) {
                cout << 0;
                return 0;
            }

            charStk.pop();
            chk = true;
            
        }

        
    }
    
    while (!intStk.empty()) {
        cout << intStk.top();
        intStk.pop();

    }
    
}

[ 두번째 시도 ] 

 

- 값들이 정답보다 훨씬 크게 나오게 되었다.

- 생각을 해보니, 뒤에 있는 3*3에는 *2가 적용되지 않았다.

- 그래서 적용되는 배수를 따른 변수에 저장하고 계산하면 된다.

 

#include <iostream>
#include <stack>
#include <queue>

#include <vector>

using namespace std;

stack<char> s; // 괄호 넣는 스택
int res=1; // 연산하는 변수

string str;
bool chk = false;

bool check(char curChar) {
    if (s.empty())return true;
    if (curChar == ')' && s.top() == '(')return false;
    if (curChar == ']' && s.top() == '[')return false;
    return true;
}

int main()
{
    cin >> str;

    for (int i = 0; i < str.length(); i++) {
        int curChar = str[i];

        if (curChar == '(') {
            res *= 2;
            s.push(curChar);
        }

        else if (curChar == '[') {
            res *= 3;
            s.push(curChar);
        }

        else if (curChar == ')') {
            if (!check(curChar)) {
                s.pop();

                if (i + 1 >= str.length() || (str[i + 1] == '(' || str[i + 1] == '[')) {
                    res /= 2;
                    res += 2;
                }
            }
            else {
                cout << 0;
                return 0;
            }
        }
        
        else if (curChar == ']') {
            if (!check(curChar)) {
                s.pop();

                if (i + 1 >= str.length() || (str[i + 1] == '(' || str[i + 1] == '[')) {
                    res /= 3;
                    res += 3;
                }
            }
            else {
                cout << 0;
                return 0;
            }
        }
        cout << res << endl;
    }
    
    
    //cout << res;
}

 

[ 세번째 시도 ]

- 처음부터 구현을 잘못하였다.

- 다른 분들을 참고하기로 하였다. 분배법칙을 사용하면 풀리다는 것을 알게됨.

- 이 힌트를 이용해서 어떻게 풀면 될지 생각함

-