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

문제

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

1918번: 후위 표기식

풀이 방법

일반적으로 사용하는 중위 표기식을 컴퓨터가 계산하기 쉬운 후위 표기식으로 바꿔주는 문제다.

중위 표기식을 왼쪽부터 오른쪽 끝까지 훑으며 다음을 연산한다.

1. 피연산자면 결과 문자열에 더한다.
2. (이면 스택에 push한다.
3. *와 /이면 스택이 비어있거나 스택의 top이 우선순위가 낮은 기호가 나올 때까지 pop하며 결과 문자열에 더한다.
4. +와 -이면 스택이 비어있거나 스택의 top이 (가 나올 때까지 pop하며 결과 문자열에 더한다. 연산 우선순위가 제일 낮기 때문이다.
5. )이면 스택의 top이 (가 나올 때까지 pop하며 결과 문자열에 더한다. 이때 스택의 top인 (도 마저 pop해준다.

이 과정이 끝난 뒤에도 스택이 비어있지 않으면 남은 연산자들을 pop하며 결과 문자열에 더한다.

최종적으로 결과 문자열을 출력한다.

코드

#include <cstdio>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
int main()
{
    char s[101];
    scanf("%s", &s);
    stack<char> op;
    string str(s);
    string result = ""; // 결과 문자열
    for(int i=0; i<str.size(); i++)
    {
        if(isalpha(str[i])) result += str[i]; // 1
        else
        {
            if(str[i] == '(') op.push('('); // 2
            else if(str[i] == '*' || str[i] == '/') // 3
            {
                while(!op.empty() && (op.top() == '*' || op.top() == '/'))
                {
                    result += op.top();
                    op.pop();
                }
                op.push(str[i]);
            }
            else if(str[i] == '+' || str[i] == '-') // 4
            {
                while(!op.empty() && op.top() != '(')
                {
                    result += op.top();
                    op.pop();
                }
                op.push(str[i]);
            }
            else if(str[i] == ')') // 5
            {
                while(!op.empty() && op.top() != '(')
                {
                    result += op.top();
                    op.pop();
                }
                op.pop();
            }
        }
    }
    while(!op.empty()) // 6
    {
        result += op.top();
        op.pop();
    }
    printf("%s", result.c_str()); // 7
    return 0;
}

고찰

 풀이 자체는 스택을 사용해서 푼다는 것을 알아도 경우에 따라 처리해주는 게 꽤 어렵다.

 

글 앞서 말했듯이 컴퓨터는 중위 표기식보다 후위 표기 식이 계산하기 더 쉽다. 왜 그럴까?

컴퓨터는 순차적으로 처리하기 때문에 괄호, 연산자, 피연산자가 뒤섞여있는 중위 표기식을 봤을 때, 어떤 것을 먼저 계산해야 할지 알기 어렵기 때문이다.

반면 후위 표기식은 애초에 우선순위대로 되어있기 때문에, 순차적으로 계산하면 된다.

컴퓨터가 후위 표기식을 연산할 때는 다음과 같이 하면 된다.

1. 피연산자면 스택에 push한다.
2. 연산자면 스택에서 두 번 pop하여 두 데이터로 연산한 다음 결과를 스택에 다시 push한다. 이때 만약 연산이 a + b라고 하면 b가 스택의 top, a는 그 아래 데이터다.

계산이 엄청 간단해졌다!

후위표기식 계산과 관련된 문제는 다음과 같다.

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

1935번: 후위 표기식2