Koala - 4기

[BOJ] 1918 후위표기식

코딩하는쉐프 2021. 7. 24. 19:53

스택 사용해야할 것 같다

A~Z는 그냥 바로 출력

* / 가 나오면 스택
스택이 비어있지 않고, top에 * /가 있는 경우 -> top을 출력하고 pop한다. 그 후 스택에 넣는다.

+ -가 나오면 스택에 넣는다.
!empty ->  스택이 빌 때까지 top 출력 후 pop 그 후 스택에 넣는다.
스택에 ( 이 있는 경우 -> ( 가 나올 때까지 출력하고 pop한다. 그 후 스택에 넣는다.

( 가 나오면 스택에 넣는다.

) 가 나오면 전까지 스택에 있는 값을 출력한다.

모든 과정이 끝났는데 스택에 값 존재하면 모두 출력

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){
    string line;
    stack<char> s;
    cin >> line;

    for(int i=0 ;i < line.length(); i++){
        if(line[i] == '*' || line[i] == '/'){
            if(!s.empty() && (s.top() == '*' || s.top() == '/')){
                cout << s.top();
                s.pop();
            }
            s.push(line[i]);
        }
        else if(line[i] == '+' || line[i] == '-'){
            if(s.empty()){
                s.push(line[i]);
            }
            else{
                while(!s.empty()){
                    if(s.top() == '('){
                        break;
                    }
                    cout << s.top();
                    s.pop();
                }
                s.push(line[i]);
            }
        }
        else if(line[i] == '('){
            s.push(line[i]);
        }
        else if(line[i] == ')'){
            while(s.top() != '('){
                cout << s.top();
                s.pop();
            }
            s.pop();
        }
        else{   // A ~ Z
            cout << line[i];
        }
    }
    while(!s.empty()){
        cout << s.top();
        s.pop();
    }
}