1224.계산기3

드디어 계산기 문제의 마지막 3번째이다.

이전과 똑같이만 이번에는 '(' 와 ')'가 등장해서 살짝 다른 계산이 필요했다.

괄호는 무조건 넣어주고 괄호의 짝이 맞아떨어지게되면 스택에 저장된 괄호의 모든 연산자를

pop해야한다는 것이 특징이었다. 생각보다 오랜시간이 걸리지 않은 문제였다.

물론 나보다 간단하게 푼사람도 많을 것이라고 생각한다.

하지만 스스로 생각하면서 뚝딱 풀어낸 것에 의의를 두어야겠다.

 

< Code 설명 >

#include <iostream>
#include <stack>
#include <queue>
#include <string.h>

using namespace std;

int main()
{
    int n;
    for(int k=1; k<=10; k++){
        cin >> n;
        string str;
        cin >> str;
        stack<char> s; // 피연산자들이 담길 stack
        queue<char> q; // 후위계산식이 담길 queue
        for(int i=0; i<n; i++){
            if(str[i]=='+'){   // 비교할 값이 '+'일 경우
                if(s.empty())  // stack이 비어있다면
                    s.push(str[i]); // 해당 연산자를 stack에 push
                else if(s.top()=='*'|| s.top()=='+'){ //'+'면서 최상위가 '*','+'
                    q.push(s.top()); // 우선순위에 따라 최상위값을 queue로 옮겨주고
                    s.pop();         // stack에서 제거
                    if(!s.empty() && s.top()=='+'){//비교후에도 스택최상위가 '+'면
                        for(int i=0; i<s.size(); i++){ // 스택크기만큼 비교해보자
                            if(s.top()=='+'){          // 최상위가 '+'라면
                                q.push(s.top());       // 역시 queue로 옮겨주고
                                s.pop();               // 스택에서 제거
                            }
                        }
                    }
                    s.push(str[i]);     // 해당작업이 끝났으면 비교값 push
                }
                else
                    s.push(str[i]);    // 스택 최상위가 괄호인 경우 바로 push
            }
            else if(str[i]=='*'){      // 비교 값이 '+'일 때
                if(s.empty())          // 연산자 스택이 비어있다면
                    s.push(str[i]);    // 스택에 push
                else if(s.top()=='+'){ // 비교 값이 '*"인데 스택 최상위가 '+'이면
                    s.push(str[i]);    // 우선순위에 상관 없으므로 바로 push
                }
                else if(s.top()=='*'){ // 만약 최상위가 '*'면 우선순위가 같으므로 빼야함
                    q.push(s.top());   // 그러므로 queue로 옮겨주고
                    s.pop();           // 스택에서 제거
                    if(!s.empty() && s.top()=='*'){//비교후에도 스택최상위가 '*'이면
                        for(int i=0; i<s.size(); i++){// 혹시모르니 다 비교해서
                            if(s.top()=='*')          // 스택 최상위가 '*'면 제거
                                s.pop();
                        }
                    }
                    s.push(str[i]);    // 그 뒤 비교값 스택에 push
                }
                else
                    s.push(str[i]);    // 스택 최상위가 괄호인 경우 바로 push
            }
            else if(str[i]=='(' || str[i]==')'){ // 비교값이 괄호인 경우
                s.push(str[i]);    // 괄호는 무조건 스택에 push
                if(str[i]==')'){   // 만약 닿는 괄호라면
                    while(s.top()!='('){ // 여튼괄호가 최상위가 될 때까지
                        if(s.top()=='(' || s.top()==')') //스택 최상위가 괄호라면
                            s.pop();                     // 스택에서 제거
                                                         // (괄호는 필요없으니까)
                        else{                   // 그게아니라면
                            q.push(s.top());    // 해당 연산자들을 queue로 옮김
                            s.pop();            // 옮긴 연산자는 모두 스택에서 제거
                        }
                    }
                    s.pop();                    // 이렇게되면 스택 최상위는 '('가
                                                // 남기 때문에 제거
                                                // ')'를 만나면 '('까지 제거하므로
                }
            }
            else{               // 비교값이 피연산자인 경우
                q.push(str[i]); // 바로 queue에 넣음
            }
            if(!s.empty() && i==n-1){ // 스택은 비어있지 않으면서 마지막 비교인 경우
                while(!s.empty()){    // 스택이 빌 때까지
                    q.push(s.top());  // 연산자를 queue로 옮긴다.
                    s.pop();          // 옮긴연산자는 스택에서 제거
                }
            }
        }
        stack<int>ans;
        int v=0;
        for(int i=0; i<n; i++){
            if(q.empty())
                break;
            if(q.front()=='+'){
                ans.pop();
                if(!ans.empty())
                    v+=ans.top();
                ans.pop();
                ans.push(v);
                q.pop();
            }
            else if(q.front()=='*'){
                ans.pop();
                if(!ans.empty())
                    v*=ans.top();
                ans.pop();
                ans.push(v);
                q.pop();
            }
            else {
                ans.push(q.front()-48);
                v=ans.top();
                q.pop();
            }
        }
        cout << "#" << k << " " << ans.top() << endl;
    }
    return 0;
}

 

반드시 알아야할 TIP!!

크게 '*' 일 때 '+' 일 때 괄호일 때 이렇게 세 가지로 비교하도록 했고

중요한점은 우선순위를 체크하는 것과 우선순위로인해 발생할 수 있는 상황들의 예외처리를 해주는 것이다.

예를 들어 '*'가 '+'보다 우선순위가 높기 때문에 스택의 최상위가 '*'인데 내가 비교하는 값이 '+'일 경우

스택에서 '*'를 빼주고 '+'를 넣어주면된다. 하지만 '*'를 뺏더니 또 '*'가 최상위거나 '+'가 최상위일 경우도 생각해서

예외처리를 진행해주어야한다는 것이다. 이런 예외들을 바로바로 잘 떠올릴 수록 정답에 빠르게 근접할 수 있다. 

피연산자를 후위계산법으로 바꿔주고 나서 연산자 스택에 값이 남아있는 경우 전부 pop을 진행해서 후위계산식에

붙여주는 것도 잘 생각해주어야한다. 이런건 암기가 아니라 역시 예외처리를 잘 신경쓰는 것이 관건이라고 생각한다.

 

 

# 이제는 문제를 풀 때 속도를 조금 더 빨리 올려보는 연습을 해야겠다.

# 살짝 감이왔고 Stack과 queue를 적절하게 사용할 수 있게 되었다.

# 역시 뭐든 처음이 어렵지 힘든 구간만 이겨내면 아주 조금씩이라도 성장하는게 보이는 것같다

-> 이걸로 위안 삼아야지...ㅠㅠ