[자료구조/스택] 백준 1918 후위 표기식 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1918번: 후위 표기식

 

 

 

2. 문제 풀이

 중위 표기식으로 표현된 식을 '후위 표기식'으로 변환하는 문제입니다. 중위 표기식은 [피연산자 - 연산자 - 피연산자] 순으로 우리가 일상에서 사용하는 형식입니다.

 반면 후위표기식은 [피연산자 - 피연산자 - 연산자] 순으로 식을 나열합니다. 앞에 피연산자가 2개 이상 쌓이고, 연산자를 만나면 그제서야 계산하는 방식입니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

 피연산자를 쌓아두다가, 연산자를 만나면 계산하는 방식이므로 '스택'을 이용합니다.

 

 

입력: A+B*C-D/E

1) 출력 A
2) 출력 A  스택 +
3) 출력 AB  스택 +
4) 출력 AB  스택 +*
5) 출력 ABC  스택 +*
6) 출력 ABC*+  스택 -
7) 출력 ABC*+D 스택 -
8) 출력 ABC*+D 스택 -/
9) 출력 ABC*+DE 스택 -/
10) 스택 비우기 => 출력 ABC*+DE/-

출력: ABC*+DE/-​

 피연산자(알파벳)은 그대로 출력하고, 연산자는 스택에 보관합니다.

 +나 -가 들어오면 그 이전 연산자들을 모두 뱉어내고 스택에 저장하고, *나 /가 들어오면 그 이전에 곱셈 나눗셈이 있었을 때만 바로 출력합니다.

 

 

 

3. 코드

# 입력
s = input()

# 스택을 이용한 후위표기식
stack = []
res = ''
for i in s:
    # 피연산자이면 바로 추가
    if i.isalpha():
        res += i
    # 괄호 열면 스택에 추가
    elif i == '(':
        stack.append(i)
    # 곱셈이나 나눗셈이면 그 이전 곱셈/나눗셈 내보내기
    elif i == '*' or i == '/':
        while stack and (stack[-1] == '*' or stack[-1] == '/'):
            res += stack.pop()
        stack.append(i)
    # 덧셈이나 뺄셈이면 모두 내보내기
    elif i == '+' or i == '-':
        while stack and stack[-1] != '(':
            res += stack.pop()
        stack.append(i)

    # 시작 괄호가 나올 때까지 스택 비우기
    elif i == ')':
        while stack and stack[-1] != '(':
            res += stack.pop()
        stack.pop()  # ( 괄호 제거

# 스택 비우기
while stack:
    res += stack.pop()
print(res)