[자료구조] 스택 : 후위표기법

스택을 활용하여 후위표기법을 구현할 수 있다. 후위표기법의 개념과 스택으로 후위표기법을 구현해보자.

---

후위표기법이란?

우리가 일반적으로 알고있는 5+3x2와 같은 수식은 중위 표기법으로 작성된 것이다. 이를 후위표기법으로 변환하면 532x+가 된다. 먼저 중위 표기법으로 작성된 수식을 후위 표기법으로 변환하는 방법과 후위 표기법으로 표현된 수식을 계산하는 방법을 알아보자.

 

후위 표기법으로 변환

5+3x2라는 수식을 보자. 

• 숫자가 나오면 바로 옮겨 적는다.
• "x" 또는 "÷"가 나오면 나온 순서대로 다른 곳에 기록해둔다.
• "+" 또는 "-"가 나오면 다른 곳에 기록해둔 "x"와 "÷"를 늦게 적은 순서대로 후위 표기식에 옮겨 적는다. 모두 옮겨 적었다면 "+" 또는 "-"를 다른 곳에 기록해둔다.
• 모두 적었을 때 다른 곳에 기록해둔 곳을 확인하여 남아있는 연산자가 있을 때 늦게 적은 순서대로 후위 표기식에 옮겨 적는다.

위의 조건대로 옮겨적는다면 중위 표기식에서 후위 표기식으로 변환하게 된다.

 

후위 표기식 계산

이제 후위 표기식 계산을 알아보자. 위에서 5+3x2를 후위 표기식으로 작성하면 532x+가 되는데 이를 계산해보자.

• 후위 표기식 순서대로 탐색을 한다.
• 숫자가 나왔을 때 순서대로 다른 곳에 기록해둔다.
• 연산자가 나온다면 기록해둔 곳에서 두 개의 수를 가져와 계산하고 계산 결과를 다시 다른 곳에 기록해둔다.

 

위 과정을 통해 후위 표기식을 계산할 수 있다.

---

코드로 구현하기

이제 중위 표기식을 후위 표기식으로 변환하고 계산하는 것을 코드로 구현해보자.

• 후위 표기식 변환과 계산을 위해 스택을 활용한다.
• 먼저 후위 표기식 변환을 진행한다.
• 숫자가 나오면 postfix라는 리스트에 추가한다.
• "+" 또는 "-"가 나오면 스택에 저장된 연산자를 모두 postfix에 pop하여 추가한다. 그리고 "+" 또는 "-"를 스택에 추가한다.
• "x" 또는 "÷"가 나오면 스택에 push한다.
• 위 과정을 통해 후위 표기식으로 변환할 수 있다.
• 이제 변환된 후위 표기식을 순차적으로 탐색한다.
• 숫자가 나오면 새로운 스택에 push한다.
• 연산자가 나오면 스택에서 두 개의 숫자를 pop하여 연산을 하고 결과를 다시 스택에 push한다.

 

위의 과정을 통해 스택을 활용하여 후위 표기식으로 변환하고 계산을 할 수 있다. 아래는 위의 과정을 코드로 구현한 것이다.

formula = '5+5*2/2'
stack = []
postfix = []
for f in formula:
    # 숫자가 나오면 바로 postfix에 저장
    if f.isdecimal():
        postfix.append(f)
    else:
        # 곱셈 또는 나눗셈일 때는 스택에 저장
        if f == '*' or f == '/':
            stack.append(f)
        # 덧셈 또는 뺄셈일 때는 스택의 연산자를 모두 postfix에 저장
        else:
            while stack:
                postfix.append(stack.pop())
            stack.append(f)

# 스택에 남아있는 연산자를 모두 postfix에 저장
while stack:
    postfix.append(stack.pop())

calculcation = []

for p in postfix:
    # 숫자가 나오면 int형으로 변환하여 저장
    if p.isdecimal():
        calculcation.append(int(p))
    # 연산자가 나오면 스택에서 순차적으로 두 개의 숫자를 pop
    # 연산 결과를 다시 calculcation에 저장
    else:
        if p == '+':
            a = calculcation.pop()
            b = calculcation.pop()
            calculcation.append(a + b)
        elif p == '-':
            a = calculcation.pop()
            b = calculcation.pop()
            calculcation.append(a - b)
        elif p == '*':
            a = calculcation.pop()
            b = calculcation.pop()
            calculcation.append(a * b)
        else:
            a = calculcation.pop()
            b = calculcation.pop()
            calculcation.append(a // b)

# 최종 결과
result = calculcation.pop()
print(result)