[03-11] Stack을 이용한 CALC(1/2) - 중위 표기법을 후위 표기법으로

1. 개요 & 알고리즘

일반적으로 사용하는 중위 표기법(Infix notation)으로 표현된 수식을 입력으로 받아서 후위 표기법(Postfix notation)으로 바꾸고, 스택을 이용해서 값을 연산하여 화면에 출력하는 간단한 유틸리티인 CALC를 작성해 봅니다.("C로 배우는 알고리즘"^[각주:1])

후위 표기법으로의 변환은 책만 읽어서는 쉽게 이해되지 않습니다만, 인터넷에는 그림과 더불어 알기 쉽게 설명한 페이지^[각주:2]들이 많으니, 이를 참고하고 따로 설명은 하지 않겠습니다.

후위 표기법을 이용하면 괄호를 사용하지 않아도 되며, 스택의 push, pop 동작으로 수식을 evaluation할 수 있습니다.

이번 페이지에서는 스택을 이용해서 중위 표기법을 후위 표기법으로 변환하도록 하겠습니다. 우선 '(' 연산자는 제알 낮은 우선순위인 0을 주고, +와 - 연산자느 1의 우선순위를 *와 /는 2의 우선순위를 주겠습니다.

알고리즘은 다음과 같습니다.("C로 배우는 알고리즘"^[각주:3])

1. '('를 만나면 스택에 push한다.

2. ')'를 만나면 스택에서 '('가 나올 때까지 pop하여 출력하고 '('는 pop하여 버린다.

3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 push한다.

4. 피연산자는 그냥 출력한다.

5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 pop하여 출력한다.

2. 동작 코드

 기본적인 동작 코드는 다음과 같습니다.

def do_postfix(self, source):
    dst = []
    stack = []
    for i in source:
        if i == '(':
            stack.append(i)
        elif i == ')':
            while stack[-1] != '(':
                t = stack.pop()
                dst.append(t)
            stack.pop()
        elif self.is_operator(i):
            while len(stack) != 0 and self.precedence(stack[-1]) >= self.precedence(i):
                dst.append(stack.pop())
            stack.append(i)
        elif '0' <= i <= '9':
            dst.append(i)

    while len(stack) != 0:
        t = stack.pop()
        dst.append(t)

    return(dst)

3. 실행 코드

사용자로부터 중위 표기법으로 수식을 입력 받아서, 후위 표기법으로 출력하는 실행 코드입니다.

#main() function
if __name__ == "__main__":
    source = input("Please input -> ")
    postfix = Postfix()
    contents = postfix.do_postfix(source)
    print(contents)

4. Tips

1. Python에서 List를 Stack으로 사용하는 경우, 최 상위 element는 List의 맨 마지막 element에 해당하므로 따로 함수를 구현하지 않고, [-1]번째 element를 사용하는 것으로 대신할 수 있습니다. 아래 코드를 참고해 주십시오.

while stack[-1] != '(':

2. 또한 Stack이 비었는지 여부를 확인하기 위해서 따로 함수를 구현하지 않고, List의 크기를 len() 함수를 이용해서 확인하면 됩니다. 아래 코드를 참고해 주십시오.

while len(stack) != 0:

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_11.py

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://yahma.tistory.com/5?category=640326 [본문으로]
3. http://www.yes24.com/24/goods/18003 [본문으로]