(C++) - 백준(BOJ) 1918번 : 후위 표기식

www.acmicpc.net/problem/1918

1918번: 후위 표기식

stack으로 해결한 문제였습니다.

 

풀이방법

 1. 정답을 출력할 string 변수 ans, 연산자를 넣어줄 stack op 변수를 선언합니다.

 2. 입력받은 string 변수 str의 size만큼 loop를 돌며 다음을 수행합니다.

   2-1. str[i] == '('면 무조건 op에 push

   2-2. str[i] == ')'면 '('를 포함한 한블럭의 op를 pop()

   2-3. str[i] == '*' 또는 '/'면 자신보다 높은 우선순위의 연산자는 '*' 또는 '/'밖에 없으므로 해당 연산자들이 없을 때 까지 ans에 연산자를 추가해주고 pop해줍니다.

   2-4. str[i] == '+'또는 '-'면 나머지 연산자들은 모두 자신보다 우선순위가 높거나 같으므로 '('이 나올때까지 ans에 연산자를 추가해주고 pop해줍니다.

  2-3, 2-4의 경우 해당 과정을 완료했다면 str[i]를 push해줍니다.

 

 3. 스택에 남아있는 찌꺼기들을 모두 ans에 붙인 뒤 ans를 출력해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
string str, ans;
stack <char> op;
int main() {
    cin >> str;
    
    for (int i = 0; i < str.size(); i++) {
        if ('A' <= str[i] && str[i] <= 'Z') { ans += str[i]; continue; }

        if(str[i] == '(') { op.push(str[i]); continue; }

        if(str[i] == ')'){
            while(op.top()!='(') 
                ans += op.top(), op.pop(); 
            op.pop();
            continue;
        }
        if(str[i] == '*' || str[i] == '/'){
            while(!op.empty() && (op.top() == '*' || op.top() == '/'))
                ans += op.top(), op.pop();
        }
        else{
            while(!op.empty() && op.top() != '(')
                ans += op.top(), op.pop(); 
        }
        op.push(str[i]);
    }
 
    while (!op.empty()) 
        ans += op.top(), op.pop();
    cout << ans <<'\n';    
}

 

Test Case

질문게시판에 있는 test case들입니다.

 

A*B+C => AB*C+

(B+C)*A => BC+A*

A*(B+C) => ABC+*

A+B+C*D => AB+CD*+

A*D+B+C*E => AD*B+CE*+