문제
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.
후위 표기식이란 ?
1 + 2 * 3 - D / E 이란 식이 있을 때 이 식을 중위 표기식으로 표현했다고 말한다.
이 식을 후위 표기식으로 바꾸면 1 2 3 * + D E / - 과 같다.
후위 표기식 -> 전위 표기식 과정
- 1 (2 * 3) + D E / -
- (1 + 2 * 3) D E / -
- (1 + 2 * 3) D / E -
- 1 + 2 * 3 - D / E
해결 방법
입력 받은 문자를 아스키 코드를 이용하여 정수로 처리하여 스택에 하나씩 집어 넣는다.
만약 문자일 경우 그냥 스택에 집어 넣고, 연산자일 경우에는 스택을 2번 pop하여 연산한다.
연산된 값은 다음 연산을 위해 다시 스택에 집어 넣어 저장한다.
내 코드
import sys
N = int(sys.stdin.readline())
post = sys.stdin.readline().rstrip()
num = []
for _ in range(N):
num.append(int(sys.stdin.readline()))
stack = []
for i in range(len(post)):
if post[i] == "+":
stack.append(num[stack.pop(-2)] + num[stack.pop()])
elif post[i] == "-":
stack.append(num[stack.pop(-2)] - num[stack.pop()])
elif post[i] == "*":
stack.append(num[stack.pop(-2)] * num[stack.pop()])
elif post[i] == "/":
stack.append(num[stack.pop(-2)] / num[stack.pop()])
else:
stack.append(num[ord(post[i]) - 65])
print("%.2f" %stack[0])
이 코드는 연산을 할 때마다 스택에서 pop한 숫자로 인덱스를 참조하기 때문에 만약 len(num)을 넘어가는 값이 스택에 저장되어 있을 경우 다음 연산 시에 인덱스 번호로 참조가 불가능해진다.
처음에는 연산된 결과를 스택에 다시 저장하는 방법이 틀린 줄 알았다.
근데 그냥 인덱스 번호로 pop을 하지 말고 pop을 두 번 하면 되는 거였다.
수정한 코드
import sys
N = int(sys.stdin.readline())
post = sys.stdin.readline().rstrip()
num = []
for _ in range(N):
num.append(int(sys.stdin.readline()))
stack = []
for i in range(len(post)):
if "A" <= post[i] <= "Z":
stack.append(num[ord(post[i]) - 65])
else:
val1 = stack.pop()
val2 = stack.pop()
if post[i] == "+":
stack.append(val2 + val1)
elif post[i] == "-":
stack.append(val2 - val1)
elif post[i] == "*":
stack.append(val2 * val1)
elif post[i] == "/":
stack.append(val2 / val1)
print("%.2f" %stack[0])
따로 저렇게 pop하는 부분을 따로 분리한 이유는 - 혹은 / 연산을 할 때 앞에 있는 숫자에서 뒤에 있는 숫자로 연산을 해야 하기 때문이다.
반응형
'Problem Solve > 백준' 카테고리의 다른 글
[Python] 백준 10809번 - 알파벳 찾기 (0) | 2024.03.25 |
---|---|
[Python] 백준 10808번 - 알파벳 개수 (0) | 2024.03.22 |
[Python] 백준 17299번 - 오등큰수 (1) | 2024.03.12 |
[Python] 백준 - 17298번 오큰수 (0) | 2024.03.12 |
[Python] 백준 10799번 - 쇠막대기 (0) | 2024.03.11 |