프로그래밍

www.acmicpc.net/problem/1918

[난이도] Gold4

[유형] 스택 (중위표기법 -> 후위표기법)

[풀이] 스택 (중위표기법 -> 후위표기법)

연산자 우선순위와 Stack을 이용. 연산자의 우선순위는 ( < -,+ < /,* : )는 Stack에 들어가지 않으므로 정의하지 않는다. 문자열을 순회하면서

1. 피연산자면 바로 출력

2. '('이면 스택에 push

3. ')'이면 여는 괄호가 나올때까지 스택의 원소를 팝하면서 출력

4. Stack이 비어있거나 Stack의 top보다 우선순위가 낮아질때까지 Stack의 top을 pop하면서 출력 후 push ('('인 경우 2에서 예외로 무조건 push)

4번에서 while문을 통해 반복해주는 것이 중요.

#include <stack>
#include <iostream>
#include <cctype>
#include <string>
using namespace std;
string a,ret;
int p(char c){
    if(c=='(') return 0;
    if(c=='+'||c=='-') return 1;
    return 2;
}
int main(){
    cin >> a;
    stack<char> s; 
    for(char c : a){
        if(isalpha(c)) ret+=c;
        else if(c=='(') s.push(c);
        else if(c==')'){
            while(1){
                char op = s.top(); s.pop();
                if(op=='(') break;
                ret+=op;
            }
        }
        else{
            while(!s.empty() && p(s.top()) >= p(c)) {
                ret+=s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while(!s.empty()) {
        ret+=s.top();
        s.pop();
    }
    cout << ret;
} 

github.com/has2/Problem-Solving/commit/f60ec108a19e4d6d59156a99880d7e222b1a3f26