프로그래밍을 배우다보면 1+2 같이 두 숫자를 더하는 계산기를 한번쯤 만들어보게 됩니다. 그런데 파이썬Python 같은 많은 프로그래밍 언어는 다음과 같은 더 복잡한 식을 처리합니다.

1*(2+3)/4 # == 1.25

즉 몇 개의 숫자든 처리할 수 있고, 괄호로 연산의 우선 순위도 정할 수 있습니다.

그렇다면 이런 건 어떻게 계산하는 것일까요? 숫자를 여러 개로 했을 뿐인데, 두 숫자인 경우보다 훨씬 어려운 문제가 되는데요. 여기서는 스택Stack 하나만을 이용해 계산기를 만들어 보겠습니다.

연산자를 뒤에 쓰기

식이 1*(2+3)이라면 덧셈을 먼저 하듯이, 괄호는 우선순위를 정합니다. 그런데 이 괄호가 정말 필요할까요?

2+3 대신 23+을 쓰는 식으로, 연산자를 뒤에 놓아볼 수 있습니다. 예를 들어, 1*(2+3)을 다음과 같이 바꿀 수 있습니다.

\begin{align*} & \texttt{1*(2+3)} &&\text{\small (infix)} \\ \rightarrow{} & \texttt{1*\fbox{(23+)}} &&{} \\ \rightarrow{} & \texttt{\fbox{1(23+)*}} &&{} \text{\small (postfix)}\\ \end{align*}

따라서 1*(2+3)은 1(23+)*이 됩니다. 그리고 괄호는 사실 필요가 없습니다. 즉 123+*라고 써도, 덧셈이 2와 3을 위한 것이라는 사실은 변하지 않습니다.

후위 표기식postfix expression이라고 불리는 이 표기법은 스택으로 계산하기가 쉬워지는데요. 곧 구현으로 볼 것 입니다. 한편 1+2 처럼 연산자가 가운데 있는 식을 중위 표기식infix expression이라고 부릅니다.

계산 순서와 똑같은 등장 순서

후위 표기식에서는 연산자들이 계산할 순서대로 나타납니다. 예를 들어 1*(2+3)은 곱셈이 먼저 나타나지만, 실제론 덧셈을 먼저 합니다. 그런데 후위 표기식으로 고친 123+*은 그 덧셈이 먼저 나타납니다.

따라서 후위 표기식은 연산자를 만날때마다 계산하면 됩니다. 그래서 괄호가 따로 필요하지 않고, 괄호에 있던 내용이 뭐였는지도 기억할 필요가 없습니다.

계산기 프로그램 디자인

여기서 만들 계산기는 후위 표기식을 계산할 것입니다. 그런데 사람은 1+2 같은 식, 즉 중위 표기식을 쓰는 것이 익숙할 텐데요. 입력은 그런 식을 받도록 만들 것입니다. 다시 말해 아래 처럼 실행하는 계산기가 목표입니다.

input:  1*(2+3)
output: 5

따라서 입력을 후위 표기식으로 바꾸는 작업도 필요하게 됩니다. 그리고 이 모든 작업은 스택만 가지고 구현할 것입니다.

정리하면 이 프로그램은 입력을 후위 표기식으로 변환하는 입력 처리 부분과, 실제로 계산을 해내는 계산 부분으로 나뉘는데요. 수도코드로 정리하면 이렇게 됩니다.

중위 표기식 계산 (중위 표기식) // 중위 표기식을 계산해 리턴

후위 표기식 $\leftarrow$ 후위 표기식으로 변환(중위 표기식)

계산 값 $\leftarrow$ 후위 표기식 계산(후위 표기식)

리턴 계산 값

이제 후위 표기식을 계산하는 두 번째 함수부터 만들어봅시다.

후위 표기식 계산하기

12+를 어떻게 계산할 수 있을까요? 앞의 두 숫자를 읽고, +를 마주쳤을 때 더하면 될 텐데요. 이렇게 숫자를 읽을 때마다 스택에 넣고, 연산자를 만났을 때 숫자를 두 개 꺼내서 계산해봅시다. 계산한 결과는 다시 스택에 넣고요.

이런 식으로 진행하면, 스택에는 하나의 숫자만 남습니다. 이것이 계산 결과가 됩니다.

예를 들어 12+로 확인해볼 수 있습니다.

Calculating postfix expression 12+ with stack — 그림 1. 숫자를 스택에 넣고, 더하기 기호를 만났을 때 꺼내서 덧셈 결과인 3을 넣습니다. 그러면 마지막으로 남은 3이 결과가 됩니다.

여태까지 숫자number와 연산자operator를 구분해서 불렀는데요. 이제부터 둘 다 토큰token이라고 부르기로 합시다. 그러면 계산기는 토큰을 읽으면서 스택을 조작하는 기계에 불과하게 됩니다.

여기까지의 아이디어를 수도코드로 정리하면 이렇게 됩니다.

후위 표기식 계산 (후위 표기식)

$\textit{stack} \leftarrow$ 스택

다음을 후위 표기식의 토큰마다 반복

만약 토큰이 숫자이면

$\textit{stack}$ .push(토큰)

아니면 // 토큰이 연산자이면

숫자2 $\leftarrow$ $\textit{stack}$ .pop()

숫자1 $\leftarrow$ $\textit{stack}$ .pop()

// 예를 들어, applyOperator(+, 1, 2)는 3을 리턴

결과 $\leftarrow$ applyOperator(토큰, 숫자1, 숫자2)

$\textit{stack}$ .push(결과)

리턴

\textit{stack}

.pop()

여기서 applyOperator() 함수는 숫자와 연산자를 받아 계산한 결과를 돌려줍니다.

구현 예시: 파이썬

예를 들어 파이썬으로 다음과 같이 만들 수 있습니다. Stack 클래스에 push()와 pop() 메소드가 있다고 합시다.

def evaluatePostfix(postfix):
    stack = Stack()

    for token in postfix:
        if token.isdigit():
            stack.push(int(token))
        elif token in "+-*/":
            num2 = stack.pop()
            num1 = stack.pop()

            evaluated = applyOperator(token, num1, num2)
            stack.push(evaluated)

    return stack.pop()

applyOperator() 함수는 사칙연산을 돕는 보조 함수입니다. 이 함수가 연산자 토큰에 의미를 붙입니다.

def applyOperator(operator, num1, num2):
  if operator == '+':
    return num1 + num2
  if operator == '-':
    return num1 - num2
  if operator == '*':
    return num1 * num2
  if operator == '/':
    return num1 / num2

이제 반이 끝났습니다.

입력 변환하기

앞서 언급했듯이, 입력을 중위 표기식으로 받기로 했습니다. 이것을 후위 표기식으로 바꿔야 하는데요. 예를 들어 1+2는 12+로 고쳐야 합니다.

자세히 보면 후위 표기식으로 바꿀 때, 숫자는 순서가 바뀌지 않는다는 사실을 알 수 있습니다. 그러므로 변환 과정에서는 숫자는 입력받은 대로 출력에 내보내면 됩니다. (다행히 할 일이 줄었네요.) 그러면 순서가 바뀌는 것은 연산자 뿐입니다.

여기에 스택을 써봅시다. 숫자는 읽자마자 출력으로 내보내고요. 연산자는 스택에 넣어놨다가, 식을 다 읽었을 때 내보냅시다.

이대로 하면, 예시로 든 1+2는 원하는 결과인 12+를 얻게 됩니다.

Converting to postfix expression with stack — 그림 2. 연산자를 읽으면 스택에 넣어두고, 식을 다 읽었을 때 꺼냅니다.

그렇지만 연산자가 더 많아지면 어떻게 할까요?

연산자들끼리 우선 순위가 다를 수 있습니다. 곱셈을 덧셈보다 먼저 하기 때문에, 곱셈 기호 *가 우선순위가 더 높다고 합시다. 나눗셈과 뺄셈도 마찬가지 입니다.

이제 스택에 연산자를 두 개 넣는다고 해봅시다. 그러면 경우는 세 가지 뿐인데요. 나중에 오는 연산자의 우선순위가 더 높거나, 더 낮거나, 또는 둘 다 같은 경우입니다.

둘 다 우선순위가 같다면

사실 거짓말입니다.

정확히 말하면 우선순위가 같은 경우는 없습니다. 왜냐면 먼저 나타난 연산을 먼저 하니까요. 1+2-3을 봅시다. 왼쪽 연산자인 덧셈 기호 +가 암묵적으로 더 높은 우선순위를 가집니다.

1+2 부분은 앞서 설명한 대로 ‘그림 2’처럼 진행합니다. 즉 스택에 덧셈 기호 +를 넣습니다. 그러면 그 다음 뺄셈 기호 -를 마주쳤을 때, 이미 들어있던 +를 꺼내서 출력으로 내보내야 합니다. 왜냐면 덧셈을 먼저 해야 하기 때문입니다. 이후 -를 꺼내므로, 변환한 후위 표기식에서 뺄셈은 나중에 나타나게 됩니다.

Handling operators having the same priority — 그림 3. 우선순위가 ‘같은’ 연산자 처리하기. 덧셈 부분은 ‘그림 2’ 처럼 진행합니다. 뺄셈 기호를 만나면 덧셈 기호를 꺼냅니다.

이처럼 덧셈 기호 +와 뺄셈 기호 -는 먼저 온 기호를 더 우선해야 합니다. 마찬가지로 곱셈과 나눗셈 기호도 그렇고요.

앞서 세 가지 경우로 나눴지만, 지켜야할 원칙은 하나뿐입니다. 먼저 계산할 연산을 먼저 꺼내는 것입니다.

나머지 케이스

나머지 두 경우를 생각해보세요. 1*2+3인 경우는 어떨까요? 반대로 1+2*3인 경우는 어떨까요? 설명이 지루하기 때문에 직접 해보는 부분으로 남겨두겠습니다.

두 번째 경우는 아래 그림처럼 구현할 수 있습니다. 덧셈 기호는 꺼내지 않고 그 위에 곱셈 기호를 둡니다. 그래야 다 읽고나서 전부 꺼낼 때 곱셈 기호가 먼저 나오니까요.

Answer to the second exercise — 그림 4. 우선순위가 다른 경우 처리하기. 덧셈 부분은 ‘그림 2’ 처럼 진행합니다. 나중에 곱셈 기호를 먼저 꺼내기 위해, 덧셈 기호 위에 둡니다. 즉 항상 ‘급한’ 기호를 먼저 꺼냅니다.

괄호를 만났을 때

숨겨진 케이스가 마지막으로 하나 더 있었습니다. 괄호 기호를 처리해야 하는데요. 다행인 점은, 괄호 안은 기존에 하던 그대로 하면 된다는 것입니다.

괄호란 우선순위가 더 높다는 것, 즉 그 부분부터 처리해야 한다는 것을 의미합니다. 스택에는 가장 최근의 내용이 가장 위에 있기 때문에, 여태 했던 방법에서 바꿀 부분은 없게 됩니다.

그러면 괄호 안의 내용은 신경 쓰지 않고, 괄호 기호만 생각해봅시다. 여는 괄호를 만나면 그대로 스택에 넣고요. 닫는 것을 만나면 여는 괄호까지 꺼내봅시다. 대신 후위 표기식에서 괄호는 없어야 하므로, 모든 괄호는 스택에서 꺼낼 때 버립니다.

예를 들어 1*(2+3)를 봅시다. 닫는 괄호를 만나면, 덧셈 기호만 먼저 꺼내 숫자 옆에 붙이게 됩니다.

Handling parentheses — 그림 5. 괄호를 만난 경우 처리하기. 숫자 3까지는, 여는 괄호는 스택에 넣으며 기존 방법대로 처리합니다. 닫는 괄호를 읽었을 때, 여는 괄호를 꺼낼 때까지 기존 방법대로 처리합니다. 그러면 괄호 부분을 스택에서 먼저 꺼내게 되고, 이는 후위 표기식 상으로 먼저 나타나게 되어 먼저 계산됩니다.

이러면 괄호 안의 식이 후위 표기식에 먼저 나타납니다. 이는 적절하게 바꿨다는 뜻입니다. 후위 표기식은 연산자 등장 순서가 계산 순서대로 나타나니까요.

이 내용을 수도코드로 정리하면 이렇게 됩니다.

후위 표기식으로 변환 (중위 표기식)

$\textit{stack} \leftarrow$ 스택

$\textit{postfix} \leftarrow$ 스트링

다음을 중위 표기식의 토큰마다 반복

만약 토큰이 숫자이면

$\textit{postfix}$ .append(토큰)

아니면 만약 토큰이 연산자이면

// 토큰보다 우선순위가 높지 않은 것들을 스택에서 꺼냄

다음을 토큰의 우선순위 > $\textit{stack}$ .peek()의 우선순위인 동안 반복

$\textit{postfix}$ .append( $\text{stack}$ .pop())

$\textit{stack}$ .push(토큰)

아니면 만약 토큰이 ‘(’이면

$\textit{stack}$ .push(토큰)

아니면 만약 토큰이 ‘)’이면

다음을 스택 맨 위가 ‘(’일 때까지 반복

$\textit{postfix}$ .append(토큰)

다음을 스택이 빌 때까지 반복

$\textit{postfix}$ .append( $\text{stack}$ .pop())

리턴 $\textit{postfix}$

구현 예시: 파이썬

파이썬으로 다음과 같이 구현할 수 있습니다. Stack 클래스에 추가적으로 peek()과 isEmpty() 메소드가 있다고 합시다. 여기서 peek()은 스택에서 가장 위에 있는 것을 꺼내지 않고 리턴합니다.

def convertInfixToPostfix(infix):
    stack = Stack()
    postfix = ""

    for token in infix:
        if token.isdigit():
            postfix += token
        elif token in "+-*/":
            # pop all operators with higher precedence
            while not stack.isEmpty():
                if getPrecedenceOf(stack.peek()) < getPrecedenceOf(token):
                    break
                postfix += stack.pop()

            stack.push(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            # pop until an opening parenthesis appears
            while not stack.isEmpty():
                t = stack.pop()
                if t == '(':
                    break
                postfix += t

    while not stack.isEmpty():
        postfix += stack.pop()
    return postfix

연산자의 우선순위를 비교할 때 getPrecedenceOf() 함수가 보조적으로 필요한데요.

def getPrecedenceOf(token):
    if token in '*/':
        return 2
    if token in '+-':
        return 1
    if token in '(':
        return 0
    raise Exception(f"invalid token '{token}'")

여기서 값보다는 상대적인 차이에 의미가 있습니다. 이 함수 덕분에 연산 기호의 우선순위가 정해집니다.

여는 괄호의 우선순위는 가장 낮게 두었는데요. 여는 괄호는 다른 연산자를 만날 때 꺼내면 안되기 때문입니다.

계산기 완성하기

여기까지 만든 함수를 연결해 계산기를 완성합시다. 처음에 디자인했던 계산기 수도코드의 구현이기도 합니다.

def evaluateInfix(infix):
    postfix = convertInfixToPostfix(infix)
    evaluated = evaluatePostfix(postfix)
    return evaluated

이제 다음과 같이 식을 계산할 수 있습니다.

evaluateInfix("(1+2)*3") # == 9

괄호가 여러번 쓰인 복잡한 식도 얼마든지 가능합니다.

evaluateInfix("(1-(2*3+4)+5*6)-7/(8-9)") # == 28

여기까지의 코드는 지스트Gist에서 볼 수 있습니다.

마치며

여기까지 간단한 계산기를 만들어 보았습니다. 스택을 이용해 입력받은 중위 표기식을 후위 표기식으로 바꾸고, 다시 스택을 이용해 이를 계산할 수 있었습니다. 사실 이것은 다익스트라Edsger Dijkstra의 션팅 야드 알고리즘shunting yard algorithm을 구현한 것입니다.

시간 복잡도

후위 표기식으로 바꿀 때, 각 입력 문자를 기껏해야 두 번, 즉 스택에 넣고 뺄 때 방문합니다. 값을 계산할 때도 마찬가지입니다. 따라서 시간 복잡도는 입력 문자의 개수 $n$ 에 대해 $O(n)$ 이 됩니다.

생략된 토큰화 과정

사실 이 계산기에는 한 자리 수의 숫자밖에 받을 수 없다는 단점이 있습니다. 왜 그럴 수 밖에 없었을까요? 은연중에 숫자와 연산자를 토큰화tokenize하고 있었기 때문입니다.

그러면 어떻게 그럴 수 있었을까요? 문자 하나하나가 그 자체로 의미가 온전했기 때문에 따로 처리가 필요없었던 것입니다. 다시 말해 한 자리의 숫자만 처리하기 때문에, 문자를 읽을 때마다 바로 하나의 숫자로 결정할 수 있었습니다.

만약 12+34를 처리해야 했다면, 1이 아닌 12를 하나의 숫자로 결정하기 위해 문자를 더 읽어야 했을 것입니다. 여기서는 간단한 구현을 위해 이러한 토큰화를 생략하는 대신, 한 자리의 숫자만 처리하는 계산기로 만들었습니다.