[Python] 1918 후위 표기식

👉 1918 후위 표기식

[정답 코드]

stack = []
ans = ''
mid = list(input().rstrip())
for i in range(len(mid)):
    if mid[i] == '(':
        stack.append(mid[i])
    elif mid[i] == ')':
        item = stack.pop()
        while item != '(':
            ans += item
            item = stack.pop()
    elif mid[i] == '+' or mid[i] == '-':
        if not stack:
            stack.append(mid[i])
        else:
            while stack and stack[len(stack) - 1] != '(':
                ans += stack.pop()
            stack.append(mid[i])
    elif mid[i] == '*' or mid[i] == '/':
        if not stack:
            stack.append(mid[i])
        else:
            top = stack[len(stack) - 1]
            if top == '*' or top == '/':
                ans += stack.pop()
            stack.append(mid[i])
    else:
        ans += mid[i]
while stack:
    ans += stack.pop()
print(ans)

[풀이]

• 피연산자는 바로 출력한다.
• 여는 괄호가 나오면 조건 없이 stack에 append한다.
• 닫는 괄호가 나오면 여는 괄호가 나올때까지 stack에서 pop하여 출력한다.
• 연산자가 나오면 해당 연산자보다 우선순위가 낮은 연산자를 만날 때(peek)까지 stack에서 pop하여 출력한 후, 해당 연산자를 stack에 append한다. [+,- < *, - < (]
  같은 연산자들끼리에선 먼저 들어온 연산자가 우선순위가 높다.
• 마지막까지 완료한 후 stack에 남아있는 연산자들을 모두 pop하여 출력해준다.

[오류 해결]
✔ 4번 과정에서 오류가 있었다.
우선순위가 낮은 연산자를 만날 때(peek)까지 계속 pop해주어야 하는데, 이 과정을 한번만 하게 했다.
elif mid[i] == '+' or mid[i] == '-': -> else: 이전 코드

else:
    top = stack[len(stack) - 1]
    if top == '*' or top == '/' or top == '+' or top == '-':
        ans += stack.pop()
    ''' 오류 해결을 위해 추가한 부분
    if stack:
        top = stack[len(stack) - 1]
        if top == '+' or top == '-':
            ans += stack.pop()
    '''
    stack.append(mid[i])

반례 : A+B*C+D*E+G
정답 : ABC*+DE*+G+
오답 : ABC*DE*G+++

[적용 자료구조 및 알고리즘]

• Stack

더 자세한 설명 및 이해를 위해 전위, 중위, 후위 표기식 를 참고해보자