BOJ 1918 · 후위표기식

알고리즘 분류 : 스택  

스택(Stack) 자료구조를 사용하는 전형적인 문제이다. 컴퓨터 과학 전공의 '자료 구조'를 수강하면, 스택을 배우면서 한 번쯤은 후위표기식을 구현해볼 것이다. 때문에 이 문제는 중위표기법을 후위표기법으로 바꾸는 방법을 알면 비교적 쉽게 해결할 수 있다.

• 중위표기법(infix)은 피연산자A - 연산자 - 피연산자B 순으로 표현한다. 예를 들면, A+B, A+B*C, (A+B)*(C-D) 이다.
• 후위표기법(postfix)은 피연산자A - 피연산자B - 연산자 순으로 표현한다. 예를 들어, AB+, ABC*+, AB+CD-* 이다.
• 후위표기법은 연산자 우선순위 순서대로 수식을 표현하기 때문에, 괄호 ( )가 필요 없다.
• 중위표기법에서 후위표기법으로 바꾸는 방법은 다음과 같다.
• 연산자를 저장할 스택 'op', 후위표기법을 저장할 배열 'a'가 있다고 하자.
• 문자열 s를 입력받고, 문자열을 앞에서부터 순서대로 한 글자씩 처리한다. 순서대로 읽는 하나의 문자를 'c'라고 하자.
• 1. 피연산자(A~Z)가 나오면, 배열 a에 저장한다.
• 2. 괄호 '('가 나오면, 스택에 push 한다.
• 3. 괄호 ')'가 나오면, 스택 top에서 괄호 '('가 나올 때까지 pop하고, pop한 연산자를 배열 a에 저장한다. 이 과정이 끝나면 pop을 한 번 더해서 괄호 '('를 제거한다.
• 4. 연산자 '*/+-'가 나오면, 스택에 들어있는 연산자와 우선순위를 비교해야 한다. 연산자의 우선순위는 */ → +- → ( 순서이다. 스택 top에 있는 연산자가 현재 연산자 c의 우선순위보다 크거나 같으면, 스택에서 pop하고, 이를 배열  a에 저장한다. 이 과정은 스택이 비거나, 연산자 우선순위가 낮은 것이 나올 때까지 진행한다. 반복 과정 종료 후, 연산자 c를 스택에 push 한다.
• 1~4 과정을 문자열 s의 길이만큼 반복한다. 반복 종료 후, 스택 op에 연산자가 남아있다면 모두 pop해서 배열 a에 저장한다.
• 후위표기식 변환을 마쳤으므로, 배열 a를 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

char s[101];
stack<char> op;

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

void solve() {
    for (int i=0; i<(int)strlen(s); i++) {
        char &c = s[i];
        if ('A' <= c && c <= 'Z') printf("%c", c);
        else if (c == '(') op.push(c);
        else if (c == ')') {
            while (op.top() != '(') {
                printf("%c", op.top());
                op.pop();
            }
            op.pop();
        } else {
            while (!op.empty() && (priority(c) <= priority(op.top()))) {
                printf("%c", op.top());
                op.pop();
            }
            op.push(c);
        }
    }
    while (!op.empty()) {
        printf("%c", op.top());
        op.pop();
    }
    printf("\n");
}

int main() {
    scanf("%s", s);
    solve();
    return 0;
}

---

Python 3 소스코드

from sys import stdin, stdout
input = stdin.readline
print = stdout.write

priority = {'*': 2, '/': 2, '+': 1, '-': 1, '(': 0}

def solve(s):
    op = []
    for c in s:
        if 'A' <= c <= 'Z':
            print(c)
        elif c == '(':
            op.append(c)
        elif c == ')':
            while op and op[-1] != '(':
                print(op.pop())
            op.pop()
        else:
            while op and priority[c] <= priority[op[-1]]:
                print(op.pop())
            op.append(c)
    while op:
        print(op.pop())
    print('\n')

solve(input().strip())

---

참고

• 백준 온라인 저지 : BOJ 1918
• 위키피디아 : 스택