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

예를 들어, 계산기라면 아래와 같은 식은 당연히 계산할 수 있을 것이라고 보통 생각할 것입니다.

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

즉, 몇 개의 숫자든 괄호든 처리할 수 있을 것으로 말입니다.

그런데 위와 같은 식을 처리하는 프로그램을 아무 지식 없이 막상 만들어보려고 한다면, 생각보다 훨씬 어려운 문제라는 것을 깨닫게 됩니다. (한번 해보세요.)

그렇다면 이런 건 어떻게 계산하는 것일까요? 여기서는 스택stack이라고 하는 데이터 구조data structure 하나만을 이용해 계산기를 만들어 보겠습니다. 앞으로 소개하는 내용을 통해, 스택에 글자를 넣고 뺀다는 개념만으로 모든 계산 식을 하나의 알고리즘으로 간단히 처리할 수 있다는 것을 알 수 있게 됩니다.

연산자를 뒤에 쓰기

학교에서 배운 수학대로라면, 계산식 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(23+)*이 됩니다.

왜 갑자기 이런 이상한 표현을 쓰는지 의문이 들 수도 있습니다. 하지만 연산자를 뒤에 쓰는 표현 방법을 쓴다면, 괄호가 필요 없다는 걸 알 수 있습니다.

즉 1(23+)*에서 괄호를 빼고 123+*라고 써도 의미가 전혀 애매해지지 않습니다. 덧셈이 2와 3을 위한 것이라는 사실은 변하지 않기 때문입니다.

이러한 계산식은 연산자를 뒤에 쓴다고 해서 후위 표기식postfix expression이라고 부르고, 곧 계산기를 실제 구현할 때 볼 것처럼 스택으로 계산하기가 매우 쉬워집니다. 한편 1+2 처럼 보통 우리가 쓰는 방식은, 연산자를 가운데 둔다고 해서 중위 표기식infix expression이라고 부릅니다.

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

여기서 후위 표기식이 왜 컴퓨터가 계산하기 쉬워지는지 살짝만 짚고 넘어가보겠습니다. 후위 표기식에서는 연산자가 계산할 순서대로 나타나기 때문입니다.

예를 들어 1*(2+3)은 왼쪽부터 읽었을 때 곱셈이 먼저 나타나지만, 연산 과정에서는 덧셈을 먼저 합니다. 반면, 후위 표기식으로 고친 123+*은 왼쪽부터 읽었을 때 덧셈이 먼저 나타납니다.

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

계산기 프로그램 디자인

여기서 만들 계산기는 후위 표기식을 계산할 것입니다. 그런데 일반적으로 사람은 1+2 같은 식, 즉 중위 표기식이 익숙할 텐데요. 따라서 입력은 그런 식을 받도록 만들 것입니다.

다시 말해, 아래 처럼 실행하는 계산기가 목표입니다.

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

그러므로 입력을 후위 표기식으로 바꾸는 작업도 필요하게 됩니다. 갑자기 해야할 일이 늘어난 것 같지만, 재밌게도 이 작업 또한 스택만으로 처리할 수 있습니다.

정리하면 이 계산기 프로그램은 입력을 후위 표기식으로 바꾸는 부분과, 실제로 계산을 하는 부분으로 나뉩니다. 수도코드로 정리하면 이렇게 됩니다.

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

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

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

리턴 계산 결과

계획을 세웠으니 후위 표기식을 계산하는 두 번째 함수부터 만들어봅시다.

후위 표기식 계산하기

가장 간단한 문제부터 공략해봅시다. 12+는 어떻게 계산할 수 있을까요?

답은 간단합니다. 앞의 두 숫자를 읽고, +를 마주쳤을 때 더하면 되는 것입니다.

숫자를 읽을 때마다 스택에 넣고, 연산자를 만나면 숫자를 두 개 꺼내서 계산해봅시다. 계산한 결과는 다시 스택에 넣습니다.

이런 식으로 진행하면, 마지막에 스택에 하나의 숫자만 남게 되고, 이것이 최종적인 계산 결과가 됩니다. 정말로 그런지 다음과 같은 그림으로 확인해볼 수 있습니다.

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

여태까지 1, 2와 같은 숫자와 +와 같은 연산자를 구분해서 불렀는데요. 이제부터 둘 다 토큰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() 함수는 숫자와 연산자를 받아 계산한 결과를 돌려줍니다.

파이썬 구현 예시

위 수도코드를 통해 파이썬을 예로 들어 구현해보겠습니다.

먼저, 앞으로 쓸 스택을 위해 클래스를 간단히 준비해봅시다. 내부적으로는 배열을 사용하며, 외부적으로는 배열의 마지막 위치에서 데이터를 넣고 뺄 수 있도록 push()와 pop() 인터페이스만 남겨놓습니다.

class Stack():
    def __init__(self):
        self._array = []

    def push(self, data):
        self._array.append(data)

    def pop(self):
        return self._array.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}$

여기서 스택의 peek() 메소드는, pop()처럼 값을 가져오되 꺼내지는 않습니다. 즉 다음에 가져올 값을 미리 보는 것입니다.

파이썬 구현 예시

앞서 구현한 것에 이어서 계산기를 완성해봅시다.

스택 클래스에 추가적으로 peek()과 isEmpty() 메소드를 준비합니다. (직접 해보세요.) 그리고 변환 함수는 수도코드를 그대로 옮기는 수준으로 구현할 수 있습니다.

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$ 에 대해 $\Theta(n)$ 이 됩니다.

생략된 토큰화 과정

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

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

만약 12+34를 처리해야 했다면, 1을 읽었을 때 판단을 잠시 유보하고 12를 하나의 숫자로 결정하기 위해 문자를 더 읽어야 했을 것입니다. 여기서는 간단한 구현을 위해 이러한 토큰화를 생략하는 대신, 한 자리의 숫자만 처리하는 계산기로 만들었습니다. (하지만 계산 결과는 얼마든지 여러 자리일 수 있습니다.)