후위식 변환

중위식과 후위식

B * C와 같은 수식을 쓸 때, 수식의 형태는 여러분에게 정보를 전달하여 이를 정확하게 해석할 수 있게 한다. 앞의 식에서는 B가 C에 곱해진다는 것을 두 변수 사이에 있는 연산자를 보고 알 수 있다. 이러한 수식 표현 방식을 중위법(infix)이라 하는데 이는 연산자의 위치가 피연산자의 위치 사이에 온다는 의미이다.

A + B * C의 경우에는 아시다시피 연산자의 우선순위가 있다. 더하기 빼기보다는 곱하기 나누기가 연산의 우선순위가 높기 때문에 B와 C가 먼저 곱해지고 그 다음에 A와 더해지게 된다. 하지만 이것은 연산자의 우선순위를 모르는 사람에게는 모호한 표현일 수 밖에 없다. 하지만 많은 사람들은 이러한 표현을 아주 오랜 기간 동안 사용해왔기 때문에 특별히 문제가 되지는 않는다. (네이버 지식인 같은 데를 보면 꼭 그렇지만은 않지만…) 아무튼 연산자는 우선순위를 가지고 높은 우선순위의 연산자는 낮은 우선순위의 연산자보다 먼저 계산된다. 이 때 우선순위를 바꿀 수 있는 방법은 먼저 계산해야 할 부분을 괄호로 싸는 것이다. 그리고 같은 우선순위의 연산자들이 만나면 왼쪽에 있는 것부터 먼저 계산된다.

문제는 컴퓨터에게 이런 모호한 우선순위 규칙을 가지고 계산하는 방식은 매우 거추장스럽다는 점이다. (실제로 계산기처럼 수식을 입력받아서 계산하는 프로그램을 짜보면 안다) 따라서 가장 확실하게 연산의 우선순위를 매겨주는 방법은 무조건 괄호로 감싸는 것이다. 예를 들어 A + B * C + D(((A + (B * C)) + D)와 같이 쓰는 것이다.

그외에도 연산자의 우선순위에 상관없이 계산할 수 있는 방식이 있는데 그것은 후위법과 전위법이다. 전위법은 연산자를 먼저쓰고 그 뒤에 피연산자 두 개를 쓴다. 우휘법은 피 연산자 두 개를 쓰고 그 뒤에 연산자를 쓴다.

예를 들어 A + B * C는 전위법으로 표기하면 + A * B C가 된다. 반대로 후위법으로 표기하면 A B C * +가 된다. 곱하기가 B와 C 바로 다음에 나오기 때문에 괄호나 우선순위같은 거 몰라도 바로 계산할 수 있다는 장점이 있다. (물론 사람이 이 식을 읽어서 계산하기란 좀 쉽지 않다. 물론 익숙해지면 또 말이 다르지만…)

이번에는 (A + B) * C를 생각해보자. 후위식에서 이 식은 A B + C *로 쓴다. A와 B 바로 다음에 더하기가 오기 때문에 이를 먼저 계산하게 된다. 즉 후위식 표기법은 중위식과 달리 괄호역시 필요로하지 않는다. 다만 피연산자와 연산자의 위치로만 먼저 계산해야 할 부분이 정해지게 된다.

중위식을 후위식으로 바꾸는 방법은 스택을 하나 사용하면 쉽게 할 수 있다. 이 알고리듬은 위대한 수학자 다익스트라가 개발했다고 알려져있는데, 다익스트라 알고리듬은 연결된 지점들 간의 최단거리를 구하는 알고리듬이고, 이거랑은 상관없다. 암튼 다음 로직을 따르면 된다.

  1. 수식을 각 토큰별로 구분하여 읽어들인다.
  2. 토큰이 피 연산자이면 출력 리스트에 넣는다. (출력리스트는 일종의 큐)
  3. 토큰이 왼쪽 괄호이면 스택에 푸시한다.
  4. 토큰이 연산자이면, 스택에서 꺼낸 연산자가 자신과 같거나 높은 우선순위라면 리스트에 이어 붙여준다.
  5. 토큰이 오른쪽 괄호이면 왼쪽 괄호가 나올 때까지 스택에서 팝하여 순서대로 리스트에 넣는다. 왼쪽 괄호 자체는 버린다.
  6. 더 이상 읽을 토큰이 없다면, 스택에서 연산자를 팝하여 붙인다. 이 때도 나온 연산자 중 왼쪽 괄호는 그냥 버리면 된다.

아래는 구현예제. 간단한 스택 클래스를 추가했는데, 리스트에 이미 pop 메소드가 있기 때문에 리스트만으로도 구현해도 될 듯 하다. 입력은 모든 연산자와 피연산자는 공백으로 띄어져 있다고 가정한다.

class EmptyStackException(Exception):
    pass


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

    def push(self, item):
        self._list.append(item)

    @property
    def isEmpty(self):
        return self._list == []

    def pop(self):
        if self.isEmpty:

            raise EmptyStackException("Stack is Empty!")
        else:
            return self._list.pop()

    def peek(self):
        if self.isEmpty:
            raise EmptyStackException("Stack is Empty")
        else:
            return self._list[-1]


def convertToPostFix(expStr):
    tokens = expStr.split(' ')
    ops = ["+", "-", "*", "/", "(", ")"]
    precs = {
        "*": 2,
        "/": 2,
        "+": 1,
        "-": 1,
        "(": 0
    }
    opStack = Stack()
    output = []
    for item in tokens:
        if item not in ops:
            output.append(item)
        elif item == "(":
            opStack.push(item)
        elif item == ")":
            while opStack.peek() is not "(":
                output.append(opStack.pop())
            opStack.pop()
        else:
            done = False
            while not opStack.isEmpty and not done:
                if precs[opStack.peek()] >= precs[item]:
                    output.append(opStack.pop())
                else:
                    done = True
            opStack.push(item)
    while not opStack.isEmpty:
        output.append(opStack.pop())

    return " ".join(output)


print(convertToPostFix("A + B * C"))
print(convertToPostFix("( A + B ) * ( C + D )"))