문제
문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.
예를 들어
“3+(4+5)*6+7”
라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다.
"345+6*+7+"
변환된 식을 계산하면 64를 얻을 수 있다.
문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다.
이 때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다.
피연산자인 숫자는 0 ~ 9의 정수만 주어진다.
[입력]
각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 길이가 주어진다. 그 다음 줄에 바로 테스트 케이스가 주어진다.
총 10개의 테스트 케이스가 주어진다.
[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 답을 출력한다.
★ 시작하기 전에
계산기 문제! 중위 표기법을 후위 표기법으로 바꾼 뒤, 다시 순차적으로 stack을 활용하여 계산하는 방법.
why? 왜 이렇게 풀지? 라고 생각했는데... 컴퓨터가 계산하는 방법이라고 한다.
단계별로 풀어보았다.
1. 기존 계산식 -> 후위 표기법 바꾸기 (연산자를 stack에 넣는다)
2. 후위 표기법을 계산하기 (값을 stack에 넣는다)
T = 10
calc = ['+', '*', '(', ')']
inorder = {'+': 1, '*':2, '(': 0}
outorder = {'+': 1, '*':2, '(': 3}
# 중위 표기법을 후위 표기법으로 바꾸기 (while문을 사용하는 방법 두려워말자)
def change(words):
s = []
top = -1
result = ''
for i in range(len(words)):
if words[i] in calc:
if s:
if words[i] == ')':
while s[top] != '(':
result += s.pop()
top -= 1
s.pop()
top -= 1
else:
while s and outorder[words[i]] <= inorder[s[top]]:
now = s.pop()
result += now
top -= 1
s.append(words[i])
top += 1
else:
s.append(words[i])
top += 1
else:
result += words[i]
while s:
result += s.pop()
return result
# 후위 표기법을 계산하기
def calculation(words):
s = []
top = -1
for i in range(len(words)):
if words[i] in calc:
if words[i] == '+':
a, b = int(s.pop()), int(s.pop())
s.append(b+a)
top -= 1
elif words[i] == '*':
a, b = int(s.pop()), int(s.pop())
s.append(b * a)
top -= 1
else:
s.append(words[i])
top += 1
return s[0]
for tc in range(1,T+1):
n = int(input())
words = input()
changes = change(words)
print('#{} {}'.format(tc, calculation(changes)))
while문 사용에 너무 걱정하지 말자.
===>>> 범위가 정해져 있지 않을 때 과감하게 사용하도록 하자.
계산기 알고리즘에 대해 잊지 않도록 하자!
'SWEA_알고리즘' 카테고리의 다른 글
[SWEA] 11611. 배열 최소 합 - Python (0) | 2021.03.02 |
---|---|
[SWEA] 4047. 영준이의 카드 카운팅 - Python (0) | 2021.02.23 |
[SWEA] 4837. 부분집합의합 - Python (0) | 2021.02.16 |