트리 순회와 수식의 표현

같은 수식트리를 읽는 순서만 바꾸어 전위·중위·후위 표기를 얻을 수 있습니다. 이진트리와 재귀·귀납을 바탕으로 정점을 처리하는 시점을 추적합니다.

자식을 언제 처리하는가

전위는 현재 정점→왼쪽→오른쪽, 중위는 왼쪽→현재→오른쪽, 후위는 왼쪽→오른쪽→현재입니다. 비어 있는 자식은 아무것도 처리하지 않고 돌아옵니다. 레벨 순회는 큐를 사용해 깊이가 작은 정점부터 읽습니다.

루트 *, 왼쪽 자식 +, 오른쪽 자식 c이고 +의 자식이 a,b인 트리는 $(a+b)c$를 뜻합니다. 전위는 * + a b c, 중위는 a + b * c, 후위는 a b + c *입니다. 중위만 괄호 없이 쓰면 원래 우선순위를 잃을 수 있어 $(a+b)*c$처럼 괄호를 복원합니다.

후위표기는 스택으로 계산한다

후위 수식 '2 3 + 4 *'를 왼쪽부터 읽습니다. 2,3을 스택에 넣고 +에서 두 값을 꺼내 5를 넣습니다. 4를 넣은 뒤 *에서 5·4=20을 넣습니다. 뺄셈·나눗셈은 두 번째로 꺼낸 값이 왼쪽 피연산자입니다. '8 2 -'에서 먼저 꺼낸 2에서 8을 빼는 것이 아닙니다.

def postfix(tokens):
    stack = []
    for token in tokens:
        if token not in ('+', '-', '*'):
            stack.append(int(token))
            continue
        if len(stack) < 2:
            raise ValueError('피연산자가 부족합니다')
        right, left = stack.pop(), stack.pop()
        if token == '+': value = left + right
        elif token == '-': value = left - right
        else: value = left * right
        stack.append(value)
    if len(stack) != 1:
        raise ValueError('완전한 수식이 아닙니다')
    return stack[0]

print(postfix('2 3 + 4 *'.split()))  # 20
print(postfix('8 2 -'.split()))      # 6

Python 3에서 정수·+,−,*만 처리하는 작은 교육용 계산기입니다. 일반 언어 파서나 모든 수식 문법을 지원하는 코드는 아닙니다. 수식트리의 내부 연산자가 두 자식 결과를 필요로 하므로 후위가 계산 순서에 자연스럽다는 점을 확인합니다.

스스로 풀어보기

문제 1. 이전 절의 8·3·10·1·6 트리에서 전위·중위·후위 순서를 쓰세요.

풀이: 전위 8,3,1,6,10; 중위 1,3,6,8,10; 후위 1,6,3,10,8입니다. 각 하위트리에서 같은 규칙을 반복한 결과이며 레벨 순서 8,3,10,1,6과 다릅니다.

문제 2. 후위 '7 2 3 + -'를 계산하고 괄호 있는 중위식으로 바꾸세요.

풀이: 2와 3의 합 5를 먼저 만들고 7−5=2입니다. 중위식은 7−(2+3)입니다. 스택에서 오른쪽 5를 먼저 꺼낸 뒤 왼쪽 7을 꺼내야 합니다.

순서가 틀리면 현재 정점을 기록할 시점을 표시하세요. 중위에서 정렬된 키를 얻는 특별한 구조는 이진탐색트리입니다.