BOJ - 후위 표기식(1918)

실버? : stack 문제이다.

풀이

처음에 op과 ()를 담는걸 별도로 생각했다가 낭패를 보았다. 생각하다보니 이 두개가 엮인다는 것을 알았고, 쉽게 규칙을 파악해서 풀 수 있었다.

Code

import sys
 
input = sys.stdin.readline
 
string = input()
# string = "A*((B+C/D-E)*F)"
stack = []
ans = ""
 
 
def operationPriority(op):
    if op in "+-":
        return "+-*/"
    else:
        return "*/"
 
 
for c in string:
    # 만약 "("이면 stack에 넣는다.
    if c == "(":
        stack.append(c)
    # 만약 ")"이면 여는 괄호가 나올 때까지 stack을 뒤지며 중간과정을 ans에 추가한다.
    elif c == ")":
        while stack:
            if stack[-1] == "(":
                stack.pop()
                break
            ans += stack.pop()
    # 만약 알파벳이면 ans 에 추가한다.
    elif c.isalpha():
        ans += c
    # 만약 +-*/이면 각각의 우선 순위보다 같거나 높은 요소를 ans에 붙인다.
    # 그렇지 않은 요소가 발견되거나
    # +-*/가 아닌 경우 탈출한다.
    elif c in "+-*/":
        opPriority = operationPriority(c)
        while stack:
            if stack[-1] not in opPriority:
                break
            ans += stack.pop()
        stack.append(c)
while stack:
    ans += stack.pop()
 
print(ans)
 
 
# 앞에서 부터 순차적으로 본다
 
# 만약 "("이면 stack에 넣는다.
 
# 만약 ")"이면 여는 괄호가 나올 때까지 stack을 뒤지며 중간과정을 ans에 추가한다.
 
# 만약 알파벳이면 ans 에 추가한다.
 
# 만약 +-*/이면 각각의 우선 순위보다 같거나 높은 요소를 ans에 붙인다.
# 그렇지 않은 요소가 발견되거나
# +-*/가 아닌 경우 탈출한다.
 
# 다 봤으면 stack에 남은 원소를 뒤에다가 모두 붙인다.

Reference

• 백준(1918번) - 후위 표기식