백준 1918번, 후위 표기식(C, C++)

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

using namespace std;

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

    cin>>s;

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

    return 0;
}

 

A + (B * C) - (D/E) 를 후위 표기식으로 봤을 때  ABC*+DE/-로 나타낼 수 있습니다.

스택을 이용하여 후위표기식으로 바꿀 것인데,')'가 나오기 이전에 스택에 담아둔 피연산자들을 조건을 걸어 처리하려고합니다.스택의 탑에 '('가 있지않고 피연산자가 탑에 있으면 출력하고 pop합니다.마지막 '('의 처리는 따로 출력하지 않고 pop을 하므로 처리가 될 것이고요.

 

피연산자의 우선순위는 '*'와 '/'가 '+', '-'보다 큽니다.따라서 스택에서는 '+'와 '-'보다 '*'와 '/'가 위에 있어야하지요.