[백준] 1918번 (python 파이썬)

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

1918번: 후위 표기식

 

s = input()

prior = {"+": 0, "-": 0, "*": 1, "/": 1, "(": 2}
stack = []
result = ""

for c in s:
  if c.isalpha(): # 문자
    result += c
  else:        # 연산자
    if c == ")":
      while stack[-1] != "(":
        result += stack.pop()
      else:
        stack.pop()
    else:
      while stack and prior[c] <= prior[stack[-1]] and stack[-1] != "(":
        result += stack.pop()
      stack.append(c)
else:
  while stack:
    result += stack.pop()
      
print(result)

 

먼저 소괄호를 생각하지말고 단순 사칙연산식만 생각해본다.

A+B*C-D/E 는 ABC*+DE/-로 나타내진다.

값인 ABCDE는 순서 그대로 나온 반면, 연산자는 등장 순서가 바뀌었다.

연산자를 대상으로 스택 자료구조를 이용하는건 아닐까 의심해본다.

코드를 완성한후, 소괄호 개념을 추가해서 생각해본다.