[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

1. http://steadyandslow.tistory.com/110 [본문으로]
2. http://www.yes24.com/24/goods/18003 [본문으로]
3. http://steadyandslow.tistory.com/110 [본문으로]
4. http://www.yes24.com/24/goods/18003 [본문으로]
5. http://www.yes24.com/24/goods/18003 [본문으로]