백준 1918 문제
링크 : https://www.acmicpc.net/problem/1918
백준 1918 풀이
후위 표기식은 2단계로 이루어진다. 1단계는 중위 표기식을 후위 표기식으로 바꾸는 것이고, 2단계는 후위 표기식을 계산하는 것이다. 2단계는 이전 글에서 풀어 보았었는데, 이번 문제는 중위 표기식을 후위 표기식으로 바꾸는 1단계 과정 문제였다.
2단계보다는 좀 더 복잡하지만, 그래도 경우의 수를 차근 차근 나눠서 풀면 된다.
- 피연산자가 나올 때 : 그냥 출력할 후위 표기식에 더하면 된다.
- 연산자가 나올 때 : 우선순위에 따라 경우의 수를 나눠야 한다.
- 괄호 ( , ) : 여는 괄호가 나오면 무조건 스택에 넣어둔다. 왜냐하면 괄호가 들어왔다는 거는 다른 것보다 먼저 계산해야하기 때문이다. 즉 이미 스택에 쌓여있는 다른 연산자보다 괄호 이후 나오는 연산자들은 먼저 후위 표기식 문자열에 더해줘야한다. 그래서 여는 괄호가 나오면 걍 스택에 던져준다.
한편, 닫는 괄호가 나온다면, 이제는 연산자를 처리해야한다는 의미다. 그래서 stack에 쌓인 연산자들을 여는 괄호가 나올 때까지 pop해서 후위 표기식에 더해줘야 한다. - 더하기 빼기 + – : 얘네들은 * / 보다 우선 순위가 낮은 애들이다. 3 + 5 * 2 이런 식이 있을 때, 아무리 +가 먼저 나왔다고 해도, 결국 *가 먼저 계산되어야 한다. 그래서 후위 표기식으로 바꾸면 352*+ 이렇게 된다. 그러니까 + – 가 나오면, 스택에 쌓인 애들은 다 빼서 먼저 후위 표기식에 붙여주어야 한다.
다른 + – 도 먼저 계산되어야 하니 얘네들도 다 빼준다. 3 – 5 +2 가 35-2+ 이렇게 되어야지, 3-(5+2)의 후위표기식인 352+-가 되면 안되니깐 말이다. - 곱하기 나누기 * / : 얘네들은 만약 앞에 + – 가 있어도 상관없는 애들이다. 어차피 우선순위가 먼저니까. 하지만 다른 */ 가 스택에 쌓여 있으면 빼줘야 한다.
# 중위표기식 입력
word = input()
# 출력할 후위 표기식
postfix =''
# 스택
stack = list()
# 후위 표기식 전환
for token in word:
# 연산자일 때?
if token in '()+-*/':
# '(' 얘는 계산에서 가장 먼저 해야할 애라서, 무조건 스택에 넣어줌
if token == '(':
stack.append(token)
# ')' 얘는 이제 계산 마무리해야해서, 스택에 있는 연산 다 빼서 postfix에 붙여줌.
# '(' 얘 나올 때까지 빼주고 괄호는 걍 없애줌.
elif token == ')':
while stack[-1] != '(':
postfix += stack.pop()
# '('얘는 걍 없애줌
stack.pop()
# +와 -는 우선 순위 낮은 애들이라, 안에 곱하기 같은 게 있으면 그걸 빼줘야함. 즉 계산 시켜야함.
# */ 뿐 아니라 다른 + -도 먼저 빼서 계산 시켜야함.
# 즉 stack에 '(' 나오거나 빌때까지 빼줘야함.
# '('는 ')'나올 때까지는 둬야지.
elif token == '+' or token == '-':
# 스택이 비어있다면?
if not stack:
stack.append(token)
# 스택에 뭐가 들어있다면?
else:
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.append(token)
elif token == '*' or token =='/':
# 스택이 비어있다면?
if not stack:
stack.append(token)
# 스택에 뭐가 들어 있다면?
# +-는 들어 있어도 상관 없음
# */는 빨리 계산 되어야 하니까 빼줘야함.
else:
while stack and stack[-1] in '*/':
postfix += stack.pop()
stack.append(token)
# 피연산자 일때?
else:
postfix += token
# 스택에 남아있는 거 처리
while stack:
postfix += stack.pop()
# 출력
print(postfix)
No Responses