스택(Stack)을 활용한 수식 계산 (후위 표기법)

우리가 일상생활에서 사용하는 수식은 2 + 3 * 4와 같이 피연산자(숫자) 사이에 연산자가 위치하는 중위 표기법(Infix Notation)입니다. 사람은 괄호와 연산자의 우선순위를 직관적으로 파악하여 곱셈을 덧셈보다 먼저 계산하지만, 컴퓨터는 이를 순차적으로 처리하기에 구조적 어려움을 겪습니다. 이러한 문제를 해결하기 위해 컴파일러는 수식을 후위 표기법(Postfix Notation)으로 변환하고, 스택(Stack) 자료구조를 활용하여 효율적으로 연산합니다. 이 글에서는 스택이 어떻게 복잡한 수식의 괄호를 제거하고 연산 순서를 제어하는지, 그 기술적 원리와 구현 방법을 상세히 알아봅니다.

1. 후위 표기법(Postfix Notation)의 개념과 이점

후위 표기법, 또는 역폴란드 표기법(Reverse Polish Notation, RPN)은 연산자를 피연산자 뒤에 위치시키는 방식입니다. 예를 들어, 중위 표기법 A + B는 후위 표기법으로 A B +가 됩니다.

1-1. 컴퓨터가 후위 표기법을 선호하는 이유

중위 표기법은 ((2 + 3) * 5)처럼 연산 순서를 지정하기 위해 괄호를 사용해야 하며, 이는 구문 분석(Parsing) 비용을 증가시킵니다. 반면 후위 표기법은 다음과 같은 강력한 기술적 이점을 가집니다.

괄호의 제거: 연산자의 위치 자체가 연산 순서를 나타내므로 괄호가 전혀 필요 없습니다.
우선순위 무시: 수식을 앞에서 뒤로 읽으면서 등장하는 연산자를 즉시 실행하면 되므로, 별도의 우선순위 판단 로직이 간소화됩니다.
일관된 처리: 컴파일러가 수식을 파싱할 때 되돌아가기(Backtracking) 없이 한 번의 스캔(O(n))만으로 계산을 완료할 수 있습니다.

2. 스택을 활용한 수식 계산 알고리즘 (동작 원리)

후위 표기법으로 변환된 수식을 계산할 때, 스택(Stack)은 피연산자를 임시 저장하는 메모리 공간으로 활용됩니다. 후입선출(LIFO) 구조 덕분에 가장 최근에 들어온 숫자들을 바로 꺼내어 연산하기에 최적화되어 있습니다.

2-1. 상세 연산 프로세스

수식 3 4 2 * + (원래 수식: 3 + 4 * 2)를 계산한다고 가정해 봅시다. 알고리즘은 다음과 같은 순서로 진행됩니다.

수식을 왼쪽에서 오른쪽으로 스캔합니다.
피연산자(숫자)를 만나면 스택에 Push합니다.
연산자를 만나면 스택에서 두 개의 숫자를 Pop합니다.
- 먼저 나온 숫자가 우측 피연산자, 나중에 나온 숫자가 좌측 피연산자가 됩니다.
두 숫자를 연산한 결과값을 다시 스택에 Push합니다.
수식의 끝에 도달하면 스택에 남아있는 하나의 값이 최종 결과가 됩니다.

3. 파이썬(Python) 코드 구현 및 분석

다음은 후위 표기법으로 작성된 문자열 수식을 입력받아, 스택을 이용해 결과를 계산하는 파이썬 코드입니다. 나눗셈이나 뺄셈 시 Pop 순서에 주의해야 한다는 점이 구현의 핵심입니다.


class PostfixCalculator:
    def __init__(self):
        self.stack = []

    def calculate(self, expression):
        # 공백으로 구분된 토큰 분리
        tokens = expression.split()

        for token in tokens:
            if token.isdigit():  # 1. 피연산자(숫자)인 경우
                self.stack.append(int(token))
            else:  # 2. 연산자인 경우
                if len(self.stack) < 2:
                    raise ValueError("잘못된 수식입니다.")
                
                # 주의: 스택은 LIFO이므로 먼저 꺼낸 것이 '뒤쪽' 숫자임
                val2 = self.stack.pop()
                val1 = self.stack.pop()

                if token == '+':
                    self.stack.append(val1 + val2)
                elif token == '-':
                    self.stack.append(val1 - val2)
                elif token == '*':
                    self.stack.append(val1 * val2)
                elif token == '/':
                    # 0으로 나누기 방지 로직 필요 (생략)
                    self.stack.append(int(val1 / val2))
        
        return self.stack.pop()

# 사용 예시: (3 + 5) * 2 - 4  ->  3 5 + 2 * 4 -
calc = PostfixCalculator()
result = calc.calculate("3 5 + 2 * 4 -")
print(f"계산 결과: {result}")  # 출력: 12

3-2. 코드 구현 시 주의사항 (Pop 순서)

덧셈이나 곱셈은 교환 법칙이 성립하므로 순서가 중요하지 않지만, 뺄셈(-)과 나눗셈(/)은 순서가 결과에 치명적인 영향을 미칩니다. 스택에서 데이터를 꺼낼 때, 첫 번째 Pop한 값이 연산자의 오른쪽, 두 번째 Pop한 값이 연산자의 왼쪽에 위치해야 함을 반드시 기억해야 합니다.

[핵심 요약 : 스택과 수식 계산]
1. 역할: 스택은 후위 표기법 수식을 계산할 때 피연산자를 순서대로 저장하고 불러오는 임시 버퍼 역할을 수행합니다.
2. 효율성: 괄호 없이 수식을 한 번만 순회(Scan)하여 계산을 완료할 수 있어, 컴파일러의 구문 분석 성능을 극대화합니다.
3. 주의점: 뺄셈이나 나눗셈 연산 시, 스택의 LIFO 특성을 고려하여 피연산자의 순서를 정확히 지정해야 합니다.

kguidebook0001 님의 블로그