[03-12] Stack을 이용한 CALC(2/2) - 계산
1. 개요 & 알고리즘
앞선 포스팅1에서 Stack을 이용해서 중위 표기법(Infix notation)으로 표현된 수식을 입력으로 받아서 후위 표기법(Postfix notation)으로 변경했습니다. 이번 포스팅에서는 후위 표기법으로 표시된 수식을 Stack을 이용해서 계산합니다. ("C로 배우는 알고리즘"2)
알고리즘은 다음과 같습니다.
1. 숫자를 만나면 숫자는 Stack에 push한다.
2. 연산자를 만나면 Stack에서 pop을 두 번하여 그 두 데이터를 가지고 연산한 다음 그 결과를 Stack에 다시 push한다.
답은 마지막으로 Stack에 남아있는 값이 됩니다.
2. 동작 코드
10 이상의 숫자를 입력 받아서 연산을 할 수도 있습니다. 이에 앞선 포스팅3과 달리 이 부분을 보완했습니다. ("C로 배우는 알고리즘"4에는 이미 있는 내용이었습니다.) 입력된 값에서 숫자가 연속되는 경우 (아래 코드에서는 is_num이 1인 경우)를 처리하기 위한 코드입니다. 숫자의 구분은 space로 합니다.
def do_postfix(self, source):
dst = []
stack = []
is_num = 0
for i in source:
# To handle not only single digit but also more than 10
if '0' <= i <= '9':
if is_num == 1:
dst[-1] = i
else:
dst.append(i)
dst.append(' ')
is_num = 1
continue
is_num = 0# 이하 생략
후위 표기법으로 Stack에 저장된 값을 읽어서 계산하는 루틴입니다. 숫자가 연속되는 경우 앞의 숫자에 10을 곱한 후 현재 숫자를 더하는 계산을 수행합니다. "C로 배우는 알고리즘"5에 적혀 있듯이 "눈여겨 볼만한 기법"입니다.
def do_calc(self, src):
stack = []
i = 0
while i < len(src):
ch = src[i]
if '0' <= ch <= '9':
t = 0
while True:
t = t * 10 + int(ch)
if '0' <= src[i+1] <= '9':
i += 1
ch = src[i]
else:
break
stack.append(t)
elif ch == '+':
t = stack.pop() + stack.pop()
stack.append(t)
elif ch == '*':
t = stack.pop() * stack.pop()
stack.append(t)
elif ch == '-':
t = stack.pop()
t = stack.pop() - t
stack.append(t)
elif ch == '/':
t = stack.pop()
t = stack.pop() / t
stack.append(t)
i += 1
# Return results which is in stack
return (stack.pop())
3. 실행 코드
실행 루틴은 다음과 같습니다.
# main() function
if __name__ == "__main__":
source = input("Please input -> ")
postfix = Postfix()
# Change infix notation to postfix notation
contents = postfix.do_postfix(source)
# Evaluate expression
results = postfix.do_calc(contents)
# Print results
print(results)
4. 코드
"C로 배우는 알고리즘" 리스트 3-11 : CALC.C에 해당합니다.
https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_12.py