백준 1918번: 후위 표기식

✔ 풀이를 위한 아이디어

• 자료구조 중 스택 (Stack)
• 후위 표기식의 개념적 이해
  
  

✔ 후위 표기식이란?

• 우리가 일반적으로 사용하는 중위 표기식 (infix) 과 다르게, 후위 표기식 (postfix) 은 연산자를 피연산자 뒤에 두는 방법

• 왼쪽부터 순서대로 계산할 수 있기 때문에, 컴퓨터가 연산할 때 적합함

* 아래의 규칙을 지켜서 표기해야 함
1. 피연산자는 그대로 출력한다.
2. 연산자는 stack이 비어있을 경우 stack에 바로 추가 (push) 한다.
3. 연산자는 stack의 top이 자신보다 우선순위가 낮을 경우에만 push 하며, 자신보다 우선순위가 높거나 같을 경우에는 계속해서 pop 한다.
4. 단, 여는 괄호는 닫는 괄호가 아니면 pop 하지 않으며, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop 해서 출력한다.
5. 마지막에 stack에 남아 있는 연산자들을 pop 해서 출력한다.

✔ 정답 코드

import sys

mathEx = list(sys.stdin.readline().strip())  # 입력 받은 문자열 (중위 표기식)
stack = []  # 연산자를 담을 stack
printString = ''  # 출력할 문자열 (후위 표기식)

for c in mathEx:  # 문자열을 list로 바꿔준 뒤, 하나씩 탐색
    if c >= 'A' and c <= 'Z':  # 규칙 1
        printString += c
    elif c == '(':
        stack.append(c)
    elif c == ')':
        while stack and stack[-1] != '(':
            printString += stack.pop()
        stack.pop()
    elif c == '+' or c == '-':
        while stack and stack[-1] != '(':
            printString += stack.pop()
        stack.append(c)
    elif c == '*' or c == '/':
        while stack and (stack[-1] == '*' or stack[-1] == '/'):
            printString += stack.pop()
        stack.append(c)

while stack:  # 규칙 5
    printString += stack.pop()

print(printString)

• 규칙 4 구현
  여는 괄호를 만나면 일단 stack에 추가해두었다가, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 계속해서 pop 하여 출력해준다.
  마지막에 한번 더 pop 해줌으로써 여는 괄호를 stack에서 제거한다.

elif c == '(':
    stack.append(c)
elif c == ')':
    while stack and stack[-1] != '(':
        printString += stack.pop()
    stack.pop()

• 규칙 2, 3 구현 - (1) 더하기나 빼기의 경우
  우선, stack이 비어있을 경우 while문을 건너뛰고 바로 stack에 연산자를 push 해준다.
  만약 비어있지 않을 경우, 문제에서 제시된 4가지 연산자 (+, -, *, /) 모두 더하기와 빼기보다 우선순위가 높거나 같으므로 계속해서 pop하면서 출력해준다.
  그러나, 여는 괄호 만큼은 닫는 괄호에 의한 것이 아니면 pop하지 않으므로 이를 조건문에 추가해준다. (다 허용하고 안되는걸 추가)

elif c == '+' or c == '-':
    while stack and stack[-1] != '(':
        printString += stack.pop()
    stack.append(c)

• 규칙 2, 3 구현 - (2) 곱하기나 나누기의 경우
  역시 stack이 비어있을 경우, while문을 건너뛰고 바로 stack에 연산자를 push 해준다.
  만약 비어있지 않을 경우, 곱하기나 나누기보다 우선순위가 높거나 같은 연산자는 역시 곱하기와 나누기 뿐이므로, 이 경우에만 stack에서 pop하면서 출력해준다. (되는 경우만 추가)

elif c == '*' or c == '/':
    while stack and (stack[-1] == '*' or stack[-1] == '/'):
        printString += stack.pop()
    stack.append(c)

• 처음에는 후위 표기식이 지켜야하는 규칙 자체를 이해 못했다보니, 아래와 같은 문제점들과 함께 틀렸었다.