후위 표기식

백준 1918번: 후위 표기식

아이디어

1. 각 연산자별로 우선순위 정의 (괄호->곱하기 나누기->더하기 빼기)
2. 피연산자는 바로 출력한다.
3. 여는 괄호를 만나면 스택에 push한다.
4. 닫는 괄호를 만나면 짝을 이루는 여는 괄호를 만날 때까지 스택에 쌓여있는 연산자를 pop해서 출력한다.
5. 스택의 최상단에 위치한 연산자와 현재 연산자의 우선순위가 같다면 스택의 최상단에 위치한 연산자를 pop해서 출력하고 현재 연산자를 push한다.
6. 스택의 최상단에 위치한 연산자보다 현재 연산자의 우선순위가 낮다면 (곱셈 이후에 덧셈) 여는 괄호를 만나기 전까지 쌓여있는 연산자를 pop해서 출력하고, 현재 연산자를 push한다.

코드

import sys
input = sys.stdin.readline

infix = input().rstrip() + ')'
dic = {'(': 0, '*': 1, '/': 1, '+': 2, '-': 2}
stack = ['(']

i = 0
while stack:
    if infix[i].isalpha():
        print(infix[i], end='')
    elif infix[i] == '(':
        stack.append('(')
    elif infix[i] == ')':
        while stack and stack[-1] != '(':
            print(stack.pop(), end='')
        stack.pop()
    else:  # + - * /
        if dic[infix[i]] == dic[stack[-1]]:
            print(stack.pop(), end='')
        elif dic[infix[i]] > dic[stack[-1]]:
            while stack[-1] != '(':
                print(stack.pop(), end='')
        stack.append(infix[i])
    i += 1

여담

작년 초에 자료구조 공부할 때 C로 만들었던 기억이 있다. 추억이 새록새록..