트리로 수식 표현과 계산

2026. 07. 21

들어가는 말

스택으로 수식 변환과 계산에서는 전위, 중위, 후위 표현식이 무엇인지 살펴봤다.
스택을 이용해 중위 표현식을 후위 표기식으로 바꾸고, 그 결과를 계산하는 과정까지 다뤘다.

수식은 트리 자료구조로도 표현할 수 있으며, 이를 수식 트리라고 한다.
이 글에서는 후위 표기식으로 수식 트리를 만들고, 수식 트리를 이용해 사칙연산을 계산하는 방법을 살펴본다.

수식 트리

전위, 중위, 후위 표기식은 모두 수식 트리로 표현할 수 있다.
이 중 후위 표기식은 스택을 이용해 수식 트리를 비교적 간단히 만들 수 있다.
중위 표기식을 후위 표기식으로 변환하는 방법은 이전 글에서 다뤘으므로, 이 글에서는 변환이 끝난 후위 표기식이 주어진다고 가정한다.
후위 표기식 23+4*는 다음과 같은 수식 트리로 표현할 수 있다.

수식 트리에서 단말 노드는 피연산자를, 내부 노드는 연산자를 나타낸다.
사칙연산은 모두 이항 연산이므로 각 내부 노드는 왼쪽과 오른쪽 자식을 가진다.
자식 노드는 숫자일 수도 있고, 다른 연산과 피연산자로 이루어진 서브트리일 수도 있다.

수식 트리에서는 노드를 방문하는 순서에 따라 서로 다른 표기식을 얻을 수 있다.
위 트리를 전위, 중위, 후위 순회하면 각각 다음과 같은 결과를 얻는다.

루트 노드를 먼저 방문한 뒤 왼쪽과 오른쪽 서브트리를 방문하는 전위 순회의 결과는 *+234이다.
왼쪽 서브트리, 루트 노드, 오른쪽 서브트리 순으로 방문하는 중위 순회의 결과는 2+3*4이다.
다만 수식 트리의 연산 순서를 그대로 나타내려면 (2+3)*4처럼 괄호를 추가해야 한다.
왼쪽과 오른쪽 서브트리를 모두 방문한 뒤 루트 노드를 방문하는 후위 순회의 결과는 23+4*이다.

수식 트리는 후위 순회를 이용해 계산할 수 있다.
단말 노드에서는 숫자 값을 반환하고, 내부 노드에서는 왼쪽과 오른쪽 서브트리의 계산 결과에 연산자를 적용한다.

소스 코드

#include <cstdio>
#include <stack>
#include <string>

using namespace std;

struct Node
{
    char value;
    Node* left;
    Node* right;
};

static Node* create_node(char value)
{
    Node* node = new Node();

    node->value = value;
    node->left = nullptr;
    node->right = nullptr;

    return node;
}

Node* build_expression_tree(const string* postfix_expression)
{
    stack<Node*> node_stack;

    for (char ch : *postfix_expression)
    {
        if (ch >= '0' && ch <= '9')
        {
            node_stack.push(create_node(ch));
            continue;
        }

        Node* operator_node = create_node(ch);

        operator_node->right = node_stack.top();
        node_stack.pop();

        operator_node->left = node_stack.top();
        node_stack.pop();

        node_stack.push(operator_node);
    }

    return node_stack.top();
}

int evaluate_expression_tree(const Node* root)
{
    if (root->left == nullptr && root->right == nullptr)
        return root->value - '0';

    int left_value = evaluate_expression_tree(root->left);
    int right_value = evaluate_expression_tree(root->right);

    switch (root->value)
    {
    case '+':
        return left_value + right_value;
    case '-':
        return left_value - right_value;
    case '*':
        return left_value * right_value;
    case '/':
        return left_value / right_value;
    }

    return 0;
}

void destroy_expression_tree(Node* root)
{
    if (root == nullptr)
        return;

    destroy_expression_tree(root->left);
    destroy_expression_tree(root->right);
    delete root;
}

int main()
{
    string postfix_expression = "23+4*";

    Node* root = build_expression_tree(&postfix_expression);

    int expression_result = evaluate_expression_tree(root);
    printf("%d\n", expression_result);

    destroy_expression_tree(root);

    return 0;
}

구현 설명

수식 트리 만들기

build_expression_tree() 함수는 후위 표기식의 문자를 왼쪽부터 하나씩 읽어 수식 트리를 만든다.
숫자를 읽으면 그 숫자를 값으로 갖는 노드를 만들어 스택에 넣는다.
연산자를 읽으면 해당 연산자를 값으로 가지는 연산자 노드를 만든다.
이후 스택의 맨 위에서 노드 두 개를 꺼내 연산자 노드의 자식으로 연결하고, 연산자 노드를 스택에 넣는다.
따라서 연산자 노드는 숫자를 값으로 가지는 노드뿐 아니라 다른 연산자 노드를 루트로 하는 서브트리도 자식으로 가질 수 있다.

읽은 문자	스택 상태	처리
`2`	`2`	`2`를 값으로 갖는 노드를 스택에 넣는다.
`3`	`2`, `3`	`3`을 값으로 갖는 노드를 스택에 넣는다.
`+`	`(2+3)`	`3`을 값으로 갖는 노드를 오른쪽 자식으로, `2`를 값으로 갖는 노드를 왼쪽 자식으로 연결한 `+` 노드를 넣는다.
`4`	`(2+3)`, `4`	`4`를 값으로 갖는 노드를 스택에 넣는다.
`*`	`((2+3)*4)`	`4`를 값으로 갖는 노드를 오른쪽 자식으로, `(2+3)` 서브트리의 루트 노드를 왼쪽 자식으로 연결한 `*` 노드를 넣는다.

모든 문자를 처리한 뒤 스택에 남은 하나의 노드가 수식 트리의 루트가 된다.

수식 트리 계산하기

evaluate_expression_tree() 함수는 왼쪽과 오른쪽 서브트리의 값을 먼저 계산한 뒤 루트 연산자를 적용한다.
이는 노드를 마지막에 방문하는 후위 순회와 같은 순서다.
단말 노드에서는 저장된 숫자를 반환하고, 연산자 노드에서는 두 자식의 계산 결과에 해당 연산을 적용한 값을 반환한다.
예제의 후위 표기식 23+4*를 계산한 결과는 20이다.