[Gold 2] 1918 후위 표기식

https://www.acmicpc.net/problem/1918

 

이 문제는 스택을 사용하면 해결할 수 있다.

알고리즘은 아래와 같다.

1. 문자열을 순차적으로 탐색한다.

2. 여는 괄호를 만나면 스택에 push

3. 곱하기나 나누기를 만나면 스택의 top이 곱하기나 나누기일 경우 스택에서 빼서 문자열에 누적

4. 더하기나 빼기를 만나면 스택의 top을 빼서 문자열에 누적. 이때 여는 괄호를 만나면 스택에서 빼는 작업 종료

5. 닫는 괄호를 만나면 스택의 top을 빼서 문자열에 누적. 이때 여는 괄호를 만나면 스택에서 빼는 작업 종료

 

 

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

string infix;
string postfix;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>infix;
    vector<char> v;

    for(int i = 0;i<infix.length();i++){
        char c = infix[i];

        if(c == '('){
            v.push_back(c);
        }
        else if(c == '*' || c == '/'){
            while(!v.empty() && (v.back() == '*' || v.back() == '/')){
                
                postfix += v.back();
                v.pop_back();
            }
            v.push_back(c);
        }
        else if(c == '+' || c == '-'){
            while(!v.empty()){
                if(v.back() == '(')
                    break;
                postfix += v.back();
                v.pop_back();  
            }
            v.push_back(c);
        }
        else if(c == ')'){
            while(!v.empty()){
                if(v.back() == '(')
                    break;
                postfix += v.back();
                v.pop_back();  
            }
            v.pop_back();
        }
        else{
            postfix += c;
        }
    }
    while(!v.empty()){
        postfix += v.back();
        v.pop_back();
    }

    cout<<postfix;
}