백준 1918 후위 표기식 혼내주기

 

처음에 (operand operator operand)마다 계산해서 다시 스택에 넣는, 그래서 최종적으로 남아있는 스택의 원소가 답이 되는 방식으로 구현을 했는데, 괄호안에 식이 여러개 있는 경우를 처리하지 못해서 포기하고 방법을 좀 찾아봤다...

operand들은 바로 결과에 넣고, operator들만 스택에 넣고 우선순위에 맞춰 스택을 비워주면 된다.
분명히 DS시간에 배웠던 기억이 어렴풋이 나는데 못풀어서 더 괴롭다...

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    string exp, ans;
    cin >> exp;
    stack<char> s;

    for(auto c : exp){
        if('A' <= c && c <= 'Z') ans.push_back(c);
        else{
            if(c == '+' || c == '-'){
                while(!s.empty() && s.top() != '('){
                    ans.push_back(s.top());
                    s.pop();
                }
                s.push(c);
            }
            else if(c == '*' || c == '/'){
                while(!s.empty() && (s.top() == '*' || s.top() == '/')){
                    ans.push_back(s.top());
                    s.pop();
                }
                s.push(c);
            }
            else if(c == '(') s.push(c);
            else{   // c == ')'
                while(!s.empty() && s.top() != '('){
                    ans.push_back(s.top());
                    s.pop();
                }
                s.pop();
            }
        }
    }

    while(!s.empty()){
        ans.push_back(s.top());
        s.pop();
    }

    cout << ans;


}