백준 1918 - 후위표기식

문제

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

1918번: 후위표기식

 

풀이

중위 표기식을 후위 표기식으로 바꾸는 문제이다. 스택을 이용하는 대표적인 문제이다. 식에 존재하는 연산자는 + - * / 인데 * / 가 + - 보다 우선순위가 높다. 그리고 같은 우선순위라면 먼저 나오는게 더 우선순위가 높게 된다. 이 점을 이용하여 알고리즘을 만든다. 

 

1. 중위표기식에 하나씩 접근하면서 피연산자를 만나면 바로 출력한다.

2. 연산자를 만나면 스택에 추가한다. 스택에 추가할 때 스택의 top이 넣을 연산자보다 우선순위가 높으면 스택을 pop 해주고 push 해준다.

3. ')'를 만나면 '(' 전까지 있는 모든 연산자를 스택에서 pop 한다.

4. 중위표기식을 모두 검사한 후에 스택에 남아있는 연산자를 pop 한다.

 

코드

 

 

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
stack<char> s;
string inorder;
 
// 연산자의 우선순위
int getPriority(char ch)
{
    switch (ch)
    {
    case '*': case '/':
        return 2;
    case '+': case '-':
        return 1;
    case '(': case ')':
        return 0;
    default:
        return -1;
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> inorder;
 
    for (int i = 0; i < inorder.size(); i++)
    {
        char ch = inorder[i];
 
        // 연산자가 아니면 바로 출력
        if (ch >= 'A' && ch <= 'Z') cout << ch;
        else    // 연산자일 경우
        {
            // 스택에 연산자가 없거나 '(' 는 바로 넣어준다.
            if (s.empty() || ch == '(') s.push(ch);
            else
            {
                // 자기 보다 높은 우선순위 위에 push 할 수 없으므로 높은 우선순위를 pop한다.
                while (getPriority(ch) <= getPriority(s.top()))
                {
                    // ')'일 경우 '('까지만 실행해야한다. 중위 표기에서 ()사이에 연산자들만 pop함
                    if (s.top() == '(')
                    {
                        s.pop();
                        break;
                    }
                    // 높은 우선순위에 연산자들 출력
                    cout << s.top();
                    s.pop();
                    if (s.empty()) break;
                }
                // ')' 일 경우 '(' 사이에 있는 연산자들을 출력하고 없어져야한다.
                if (ch != ')') s.push(ch);
            }
        }
    }
 
    // 스택에 남아있는 연산자들 출력
    while (!s.empty())
    {
        cout << s.top();
        s.pop();
    }
 
    return 0;
}