백준 1406 - 후위표기식

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

문제 해설

문제를 해결할 때 후위 표기식에 대한 명확한 이해와 연산자 우선순위에 대해 고려 해야 한다.

연산자를 별도의 stack에 쌓아가면서 후위 표기식을 만든다. stack에 연산자를 넣기 전에 연산자 비교를 통해 stack에 넣을 려는 연산자 우선순위 보다 stack에 있는 연산자의 우선순위가 작을 때까지 계속해서 stack에서 연산자를 꺼내 후위 표기식에 추가해준다.

연산자 우선순위

1. (가 제일 높은 우선순위다.
2. * 와 /가 그 다음 우선순위
3. + 와 -가 다음 우선순위를 갖고 있다.
4. )가 제일 낮은 우선순위다. (를 만날때까지 모든 연산자를 stack에서 꺼낸다.

소스 코드

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

string str;
string result;

int main(void) {
    cin >> str;

    stack<char> operation;

    for (int i = 0; i < str.length(); i++) {
        char cntChar = str[i];

        if (cntChar == '(') {
            operation.push(cntChar);
        } else if (cntChar == '*' || cntChar == '/') {
            while (!operation.empty() && (operation.top() == '*' || operation.top() == '/')) {
                result += operation.top();
                operation.pop();
            }

            operation.push(cntChar);
        } else if (cntChar == '+' || cntChar == '-') {
            while (!operation.empty() && (operation.top() != '(')) {
                result += operation.top();
                operation.pop();
            }

            operation.push(cntChar);
        } else if (cntChar == ')') {
            while (!operation.empty() && operation.top() != '(') {
                result += operation.top();
                operation.pop();
            }
            operation.pop();
        } else {
            result += cntChar;
        }
    }

    while (!operation.empty()) {
        result += operation.top();
        operation.pop();
    }

    cout << result << '\n';
    return 0;
}