후위 표기식[백준 1918] - python

 

꽤나 애를 먹었었던 문제

정답 코드 먼저 살펴보자

n = list(input())

operator = {'(': 1, '+': 2, '-': 2, '*': 3, '/': 3}
result = ""
stack = []

for i in n :
  if i == '(' :
    stack.append(i)
  elif i == ')' :
    top = stack.pop()
    while stack and top != '(' :
      result += top
      top = stack.pop()

  elif i in operator :
    while stack and operator[stack[len(stack) - 1]] >= operator[i] :
      top = stack.pop()
      if i != '(' :
        result += top
    stack.append(i)
  else :
    result += i

while len(stack) != 0 :
  result += stack.pop()

print(result)

 

스택을 이용 해야하는데 연산자들간의 우선순위 설정이 주요했다.

계속 틀렸던 이유는 우선순위 설정을 해주지 않았었다. 

3 * 4 + 3 의 경우 34*3+ 인데 해주지 않아서 343*+가 되었었다.

 

)를 만나게 되면 (를 만나기 전까지 연산자를 빼주자

*를 비교해야 하는 상황에 비교해야 하는 연산자가 *라면 하나만 빼주어야 한다. 우선순위가 낮은 +,- 애들은 계속 빼주어야 한다.

 

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

1918번: 후위 표기식