[C++] 백준/Gold/1918. 후위 표기식

문제: 후위 표기식(백준 1918번)

문제 분석

이 문제는 주어진 중위 표기식을 스택을 사용하여 후위 표기식으로 변환하는 문제다.
후위 표기식은 연산자를 나중에 쓰는 표기법으로, 계산 순서를 명확히 나타낼 수 있다는 장점이 있다.

후위 표기식

• 중위 표기식은 연산자가 피연산자 사이에 위치한다.
  예: A + B
• 후위 표기식은 연산자가 피연산자 뒤에 위치한다.
  예: AB+

후위 표기식의 특징은 괄호 없이도 연산 우선순위를 명확히 알 수 있다는 점이다.
예를 들어, A + B * C를 후위 표기식으로 바꾸면 ABC*+가 된다.

알고리즘

1. 피연산자는 바로 출력한다.
   (문자열에서 알파벳이 나오면 바로 cout으로 출력)
2. 연산자는 스택에 넣는다.
   단, 스택에 있는 연산자와 우선순위를 비교해,
   스택의 연산자가 현재 연산자보다 우선순위가 높거나 같으면 꺼내서 출력한 뒤, 현재 연산자를 스택에 넣는다.
3. 여는 괄호 '('는 스택에 넣는다.
4. 닫는 괄호 ')'가 나오면, 여는 괄호가 나올 때까지 스택에서 연산자를 꺼내 출력한다.
5. 문자열 처리가 끝난 후에도 스택에 남아 있는 연산자를 모두 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    stack<char> oper;
    unordered_map<char, int> priority = { {'+', 0}, {'-', 0}, {'*', 1}, {'/', 1} };

    for (int i = 0; i < s.size(); i++) {
        char ch = s[i];
        if (ch >= 'A' && ch <= 'Z') { // 피연산자
            cout << ch;
        }
        else if (ch == '(') { // 여는 괄호
            oper.push(ch);
        }
        else if (ch == ')') { // 닫는 괄호
            while (!oper.empty() && oper.top() != '(') {
                cout << oper.top();
                oper.pop();
            }
            oper.pop(); // 여는 괄호 제거
        }
        else { // 연산자
            while (!oper.empty() && oper.top() != '(' && priority[oper.top()] >= priority[ch]) {
                cout << oper.top();
                oper.pop();
            }
            oper.push(ch);
        }
    }

    // 스택에 남아 있는 연산자 출력
    while (!oper.empty()) {
        cout << oper.top();
        oper.pop();
    }
}