스택 수식의 계산

수식 표기법

수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix) 3가지가 있다.

보통 사람은 중위 표기법을 사용하지만 컴파일러는 후위 표기법을 사용한다. 후위 수식은 괄호가 없이도 우선순위가 반영되어 있기 때문이다.

후위 수식으로의 변환

프로그래머는 수식을 중위 표기법으로 입력하므로 계산을 위해선 후위 표기법으로 바꾸어주는 작업이 필요하다.

소스코드

from stack import Stack

def switch(i):
    # 여는 괄호를 1, 닫는 괄호를 2, 연산자는 3과 4 (숫자가 높을수록 우선순위가 높음)
    return {'(': '1', '{': '1', '[': '1',
            ')': '2', '}': '2', ']': '2',
            '+': '3', '-': '3', '*': '4', '/': '4'}.get(i, '-1')

def FourOperation(i):
    return {'+': '1', '-': '2', '*': '3', '/': '4'}.get(i, '-1')

def InfixToPostfix(expr):
    s = Stack() # 괄호와 연산자를 담을 스택
    post = [] # 변경된 수식을 담을 리스트

    # 값을 하나씩 가져옴
    for i in expr:
        ch = switch(i)
        # 여는 괄호일 경우 스택에 추가
        if ch == '1':
            s.push(i)
        # 닫는 괄호일 경우 여는 괄호를 만날 때 까지 pop 하여 리스트에 저장 
        elif ch == '2':
            while True:
                ch = s.pop()
                if switch(ch) == '1':
                    break
                else:
                    post.append(ch)
        # 연산자일 경우 스택의 맨 위 요소가 추가하려는 연산자보다 우선순위가 높거나 같으면 pop 하여 리스트에 저장 후 스택에 삽입
        elif ch == '3' or ch == '4':
            if switch(s.peek()) >= ch:
                post.append(s.pop())
                s.push(i)
            else:
                s.push(i)
        # 숫자일 경우 리스트에 추가
        else:
            post.append(i)

    # stack 에 남아있는 연산자 순서대로 리스트에 추가
    while not s.is_empty():
        post.append(s.pop())

    return post

if __name__ == "__main__":
    # 중위 수식이 주어짐
    print("(1*2+3)/4")

    # 후위 수식으로 변경
    result = InfixToPostfix("(1*2+3)/4")

    # 후위 수식으로 나타내어진 중위 수식
    for i in result:
        print(i, end="")

출력

(1*2+3)/4
12*3+4/

후위 표기식의 계산

후위 표기식으로 변경된 수식은 읽으면서 바로 계산을 할 수 있기 때문에 연산이 간단하다.

소스코드

# 위 코드에 이어
# ···

    # 후위 수식의 계산
    s = Stack()

    # 값을 하나씩 가져옴
    for i in result:
        ch = switch(i)
        # 연산자일 경우
        if ch == '3' or ch == '4':
            op = FourOperation(i)
            term2 = int(s.pop())
            term1 = int(s.pop())
            if op == '1': # 덧셈
                s.push(term1 + term2)
            elif op == '2': # 뺄셈
                s.push(term1 - term2)
            elif op == '3': # 곱셈
                s.push(term1 * term2)
            elif op == '4': # 나눗셈
                s.push(term1 / term2)
        # 숫자일 경우
        else:
            s.push(i)

    # 계산 결과
    print(s.pop())

출력

1.25