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

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

1918번: 후위 표기식

풀이

후위 표기식 문제이다. 기본적으로 후위표기식의 순서는 다음과 같다.

• 전체 식 중 괄호 안에 있는 연산
• 전체 식의 사칙연산 중에서 곱셈 또는 나눗셈이 들어간 연산
• 이후 더하기 빼기 연산

이후, 전역으로 선언해놓은 스택에는 연산자만 입력해준다.

입력한 문자열 ( 연산식 )의 길이만큼 한글자씩 탐색한다.

 

그렇다면 후위표기의 알고리즘은 아래와 같다.

• 알파벳인지, 연산자인지 우선 확인
• 여는 괄호 ' ( ' 일 경우 모든 연산자의 시작점이기에 스택에 넣어준다.
• 곱셈 ' * ' 또는 나눗셈 ' / ' 일 경우 해당 스택의 top 연산자인 곱셈,나눗셈 연산자를 출력해주고, 현재 연산자를 push 해준다.
• 더하기 ' + ' 또는 빼기 ' - ' 일 경우 해당 스택의 top 연산자가 여는괄호가 아닐 경우까지 출력 해주고, 해당 연산자를 push 해준다.
• 닫는괄호 ' ) ' 가 나올 시 여는괄호가 나올때 까지 출력해준다.

아래 코드에서 확인해보자

 

Code

#include <iostream>
#include <stack>
using namespace std;

string str;
stack<char> _stack;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> str;
    int len = str.length();

    for (char ch : str)
    {
        if (ch >= 'A' && ch <= 'Z')
        {
            cout << ch;
        }

        else
        {
            if (ch == '(')
            {
                _stack.push(ch);
            }

            else if (ch == '*' || ch == '/')
            {
                while (!_stack.empty() && (_stack.top() == '*' || _stack.top() == '/'))
                {
                    cout << _stack.top();
                    _stack.pop();
                }
                _stack.push(ch);
            }

            else if (ch == '+' || ch == '-')
            {
                while (!_stack.empty() && _stack.top() != '(')
                {
                    cout << _stack.top();
                    _stack.pop();
                }
                _stack.push(ch);
            }

            else if (ch == ')')
            {
                while (!_stack.empty() && _stack.top() != '(')
                {
                    cout << _stack.top();
                    _stack.pop();
                }
                _stack.pop();
            }
        }
    }

    while (!_stack.empty())
    {
        cout << _stack.top();
        _stack.pop();
    }
}