[1918] 후위 표기식

문제

주어진 중위표기식인 식을 후위표기식으로 변환해 출력해주면 된다.

arr = input()
priority = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0} #연산자에 우선순위를 지정
stack = list()
ans = ''


for i in arr:
    if i in ['+', '-', '*', '/', '(', ')']: #연산자일 때
        if i == '(':
            stack.append(i)
        elif i == ')':
            while stack[-1] != '(':
                ans += stack.pop()
            stack.pop()
        elif not stack:
            stack.append(i)
        elif priority[stack[-1]] >= priority[i]:
            while stack and priority[stack[-1]] >= priority[i]:
                ans += stack.pop()
            stack.append(i)
        else:
            stack.append(i)
    else:
        ans += i

j = len(stack)
while j > 0:
    ans += stack.pop()
    j -= 1

print(ans)

설명

  • 문자면 ans에 저장하고 연산자이면 다음 조건에 맞춰 실행된다.
  • priority에 주어진 우선순위보다 스택의 가장 최상단의 연산자의 우선순위가 낮으면 스택에 저장한다.
  • 스택의 최상단의 연산자 우선순위보다 i의 연산자 우선순위가 더 같거나 작으면 i보다 우선순위가 낮은 연산자가 나타날 때까지 pop
  • 여는괄호가 나타나면 일단 stack에 저장하고 닫는 괄호가 나타나면 스택의 최상단이 여는괄호일때까지 pop
  • 반복문이 종료되면 스택에 남은 것들을 모두 출력

좋은 웹페이지 즐겨찾기