[BOJ 1918] 후위 표기식 (C++)

후위 표기식 (Gold 3)

문제

전체 문제 보기

1918번: 후위 표기식

접근법

후위 표기식 문제는 스택의 대표적인 문제 중 하나이다. 중위 순위식으로 들어온 연산자들을 특정 규칙에 맞게 stack에 push 및 pop을 하여서 풀 수 있다. stack을 우선 순위가 낮은 연산자가 가장 아래에 가도록 유지한다면 우선순위가 가장 낮은 연산자가 가장 늦게 pop 될 수 있기 때문이다. 그래서 아래와 같은 방법으로 중위 표기식을 후위 표기식으로 바꿀 수 있다.

• 모든 문자에 대해서 반복한다.
  • 피연산자가 들어올 경우: 그대로 출력한다.
  • (가 들어올 경우: stack에 push 한다.
  • )가 들어올 경우: (가 나올때까지 stack에 있는 모든 연산자를 출력 후 pop 한다. 그리고 (를 pop한다.
  • 연산자가 들어올 경우: 자신보다 우선순위가 낮은 연산자가 나올 때까지 statck에 있는 모든 연산자를 출력 후 pop 한다. 그리고 자신을 push 한다.
• 반복문 종료 후 stack에 남은 연산자를 모두 출력 후 pop 한다.

전체 구현

#include <stdio.h>
#include <stack>

#define endl '\n'
using namespace std;

int priority(char ch)
{
    if (ch == '*' || ch == '/') return 2;
    else if (ch == '+' || ch == '-') return 1;
    else if (ch == '(') return 0;

}

int main() {

    stack<char>s;

    char ch;

    while ((ch = getchar()) != '\n')
    {
        switch (ch)
        {
        case '(':
            s.push(ch);
            break;

        case ')':
            while (s.top() != '(')
            {
                printf("%c", s.top());
                s.pop();              
            }
            s.pop();
            break;
        case '+':
        case '-':
        case '*':
        case '/':
            while (!s.empty() && priority(s.top()) >= priority(ch))
            {
                printf("%c", s.top());
                s.pop();
            }
            s.push(ch);
            break;

        default:
            printf("%c", ch);
            break;
        }
    }
    while (!s.empty())
    {
        printf("%c", s.top());
        s.pop();
    }

    return 0;
}

성능

시간 복잡도는 수식에 사용된 문자 하나하나에 대해 반복문을 수행하기 때문에 전체 수식 길이\(len\)에 대해 선형적으로 증가하는 \(O(n)\) 이다.