BOJ1918: 후위 표기식

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (14/187)
  • 컴파일러 씩이나 전공해놓고, 후위 표기식에 대해서 제대로 알지도 못했다니 부끄럽게 짝이없다. 정리해보면 아래와 같다.
    • 일단 상수는 그냥 찍는다. 연산자는 스택에서 빼면서 찍는다.
    • 여는 괄호는 스택에 푸쉬.
    • 닫는 괄호과 나오면 스택에 있는걸 다 찍으면서 푸쉬.
    • 스택에 여는 괄호가 top이면 그냥 푸쉬.
    • 스택에 연산자가 top이면, 더 낮은 우선순위의 연산이 top에 올때까지 pop하면서 찍고나서 푸쉬
  • 계산기 만들때는 “중위, 후위, 계산” 순서로 진행하면 될듯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int pri[256];
stack<char> st;
string eq;

int main() {
  cin >> eq;
  pri['+'] = pri['-'] = 1;
  pri['*'] = pri['/'] = 2;
  st.push('(');
  eq += ')';

  for(char c : eq) {
    if(c >= 'A' && c <= 'Z') cout << c;
    else if(c == '(') st.push('(');
    else if(st.top() == '(') st.push(c);
    else if(c == ')') {
      while(st.size() && st.top() != '(') {
        if(st.top() != '(' && st.top() != ')') cout << st.top();
        st.pop();
      }
      st.pop();
    } else {
      while (pri[c] <= pri[st.top()]) {
        if(st.top() != '(' && st.top() != ')') cout << st.top();
        st.pop();
      }
      st.push(c);
    }
  }
}