후위식 변환

중위식과 후위식

B * C와 같은 수식에서 그 형태는 보는 사람에게 정보를 전달하여 이를 정확하게 해석할 수 있게 한다. 이 식에서 계산 방법은 두 수 B, C 사이에 있는 연산자에 의해서 결정되며 여기서는 두 수를 곱하는 계산을 표현하고 있다.

연산자가 2개 이상 들어가는 수식의 계산은 어떻게 이루어질까? 여기에는 몇 가지 기본적인 규칙이 있다. 먼저 연산자는 우선순위를 갖는다. 곱하기와 나누기는 더하기와 빼기보다 높은 우선순위를 가진다. 따라서 하나의 수식에서 이들이 함께 사용된 경우, 곱하기와 나누기를 먼저 계산한 다음, 더하기와 빼기를 계산한다. 두 번째로 같은 우선순위를 갖는 연산자들 끼리는 왼쪽에서 오른쪽으로 계산한다.

이러한 우선순위에 의한 계산방법은 오래된 약속이며, 초등 교육과정에서 배우게 된다. 뭐 사람의 경우에도 그럼에도 불구하고 이런 계산 순서가 익숙치 않아서 어처구니 없는 주장을 펼치는 경우를 종종 볼 수 있는데…. 만약 계산하는 순서가 바뀌어야 하는 경우라면 어떨까? 예를 들어서 2 + 2 * 2 는 기본적으로 뒤의 2 * 2가 먼저 계산되고 2 + 4의 형태로 계산되므로 6이 답이다. 이것을 앞의 2+2를 먼저 계산하고 싶다면? 이 때에는 괄호를 이용해서 먼저 계산하는 부분을 묶는다. 즉 (2 + 2) * 2 로 수식을 쓰면 이 때에는 앞의 2 + 2를 먼저 계산해야 하므로 답은 8이 될 것이다. 사실 괄호는 수식을 먼저 계산하라고 하기 보다는 둘러싼 부분의 수식이 하나의 항임을 알려주는 것이다.

어쨌든 우리가 괄호를 사용해서 예쁘게 계산의 순서를 정해서 수식을 쓸 수 있지만, 문제는 컴퓨터에게 이런 규칙을 가지고 계산하는 방식은 매우 거추장스러워 보일 수 있다는 점이다. 사실 연산자가 우선순위를 가지고 어쩌고.. 하면서 계산의 순서를 정하는 방법은 복잡하다고 할 수 있는데, 그 원인은 바로 연산자를 값들의 사이에 쓰는 관습 때문이다.

수식을 쓰는 방법은 관습에 의한 약속인데, 이를 기계적으로 다른 문법을 적용하도록 하는 방법도 있다. 후위법 혹은 전위법이 이러한 문법이다. 전위법은 연산자를 먼저 쓰고 그 뒤에 피연산자를 두 개 쓴다. 후위법은 반대로 피연산자를 두 개 먼저쓰고 맨 뒤에 연산자를 쓴다.

전위법이나 후위법의 장점은 연산자, 피연산자1, 피연산자2 의 조합을 1개의 값으로 본다는 것이다. 따라서 하나의 계산을 수행하기 위한 수식을 표현하는 방법은 단 한가지만 존재하며, 식이 구성된 순서에만 의존하여 계산하므로 연산자의 우선순위를 고려할 필요가 없다는 것이다.

앞 선예에서 2 + 2 * 2 를 전위법으로 쓴다면 + 2 * 2 2 가 된다. + 를 먼저 계산하고 싶다면 * 2 + 2 2 로 써야한다. 여기서는 괄호가 들어갈 여지가 없고 계산순서에 의해 식의 모양이 결정된다.

전위식이나 후위식은 연산자의 위치가 다르고 계산해나가는 순서가 다를 뿐 원리는 동일하다. 연산 트리를 구성해서 연산하게 된다. 이 방식은 매우 간단한 재귀 알고리듬으로 기술할 수 있기 때문에 중위식을 후위식으로 변환할 수 있다면 계산기를 쉽게 작성할 수 있다.

후위식으로 변경하는 알고리듬

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

  1. 수식을 각 토큰별로 구분하여 큐에 들어있다고 가정한다. 토큰은 피연산자나 연산자 1개를 의미한다. 스택은 두 개가 필요하다. 하나는 출력 스택, 다른 하나는 임시 스택이다.
  2. 토큰 목록에서 앞에서부터 하나씩 토큰을 꺼내어 확인한다.
  3. 토큰이 피 연산자이면 출력 스택에 넣는다.
  4. 토큰이 왼쪽 괄호이면 무조건 임시 스택에 푸시한다.
  5. 토큰이 연산자이면, 임시 스택을 살펴본다. 스택이 비어있다면 연산자를 임시 스택에 푸시한다.
  6. 임시 스택의 맨 위의 연산자(가장 최근에 푸시한 연산자)의 우선순위가 현재 토큰과 같거나 높다면, 이를 꺼내어 출력 스택에 넣는다. 그리고 현재 큐에서 나온 연산자를 스택에 푸시한다.
  7. 현재 토큰이 오른쪽 괄호이면 왼쪽 괄호가 나올 때까지 임시 스택에서 꺼내어 출력 스택에 넣기를 반복한다. 왼쪽 괄호가 스택에서 나오면 버리고, 오른쪽 괄호도 버린다.
  8. 더 이상 읽을 토큰이 없다면, 임시 스택에서 연산자를 꺼내어 순서대로 출력스택에 넣는다.

위 과정을 거치면 출력 스택에는 후위식 표기로 바뀐 수식이 들어가게 된다. 후위식 표기는 뒤에서부터 계산하므로 이 식을 계산하기 위해서는 다시 스택에서부터 하나씩 꺼내어 계산하면 된다.

예를 들어 “2 – 3” 은 후위식으로 표기할 때 “2 3 -“가 된다. 이 수식을 계산하는 방법은 다음과 같다.

  1. 스택에서 토큰을 하나 꺼낸다.
  2. 꺼낸 토큰이 값이면 그 값으로 평가한다.
  3. 꺼낸 토큰이 연산자이면 스택에서 토큰을 꺼내 평가한다.
  4. 그리고 스택에서 토큰을 꺼내 또 평가한다.
  5. 3, 4의 결과값에 연산자를 적용한다.

아래는 후위식 변환코드이다. 인자로 받는 tokens는 중위식 표현의 연산자와 피연산자들로 이루어진 리스트이다.

def convert(tokens):
    # 연산자 정의 및 임시스택, 결과 스택
    operators = dict(zip('*/+-()', (2,2,1,1,4,0)))
    temp, result = [], []

    for token in tokens:
        # 연산자인 경우
        if token in operators:
            if token == '(':
               pass # 아무일도 하지 않음
            if token == ')': # 우측 괄호 처리
                while temp and temp[-1] != '(':
                    result.append(temp.pop())
                # 임시스택 내 왼쪽 괄호 제거
                # continue로 오른쪽 괄호를 스택에 넣지 않음
                temp.pop()
                continue
            # 우선순위가 낮은 연산자
            elif temp and operators[temp[-1]] > operators[token]:
                result.append(temp.pop())
            temp.append(token)
        else: # 피연산자는 결과 스택으로 직행
            result.append(token)
    # 임시 스택에 남은 연산자를 결과 스택으로 옮기기
    while temp:
        result.append(temp.pop())
    return result

보너스 : 후위식 스택 계산하기

보너스로 후위식으로 변환된 수식을 계산하는 함수를 작성했다. 빈 식은 0으로 평가하며, 입력된 수식은 올바른 식이라고 가정한다. ( 0으로 나누는 식등에 대한 처리를 하지 않음)

여기서 작성하는 함수 evaluate() 는 후위식으로 변환된 결과인 스택을 입력으로 받고, 계산된 식과 남은 수식 스택을 리턴한다. 여기서 앞서 정의한 알고리듬에 따라 식을 평가한다. 참고로 인자로 받은 스택에 대해서 .pop()을 호출하지 않기 때문에 입력받은 식을 소모하지 않는다.

def evaluate(stack):
    opertors = {
        '*': lambda x, y: x * y,
        '/': lambda x, y: x / y,
        '+': lambda x, y: x + y,
        '-': lambda x, y: x - y,
    }
    if not stack:
        return 0, []
    t = stack[-1]
    if t not in opertors:
        return int(t), stack[:-1]
    b, x = evaluate(stack[:-1])
    a, y = evaluate(x)
    print(a, t, b)
    return opertors[t](a, b), y