C++로 표현식 트리(Expression Tree) 평가하기

이 문제에서는 +, -, /, *와 같은 이항 연산자로 구성된 표현식 트리가 주어집니다. 우리의 목표는 이 표현식 트리를 평가(evaluation)하여 그 결과값을 반환하는 것입니다.

표현식 트리란?

표현식 트리(Expression Tree)는 각 노드가 연산자(operator) 또는 피연산자(operand)로 구성되는 특수한 형태의 이진 트리입니다. 노드의 구성은 다음과 같이 나뉩니다.

• 리프(leaf) 노드는 연산을 수행할 값(피연산자)을 담고 있습니다.
• 비 리프(non-leaf) 노드는 수행할 연산을 나타내는 이항 연산자를 담고 있습니다.

예제로 이해하기

입력:

출력: 1

설명:

트리를 수식으로 해석하면 다음과 같습니다.

Exp = ((5+9) / (2*7))
= (14 / 14)
= 1

해결 접근 방법

가장 간단한 해결 방법은 루트 노드부터 시작해 한 번에 하나의 연산씩 처리하는 것입니다. 피연산자에 해당하는 경우에는 해당 서브트리를 재귀적으로 해결합니다. 모든 연산이 이항 연산이므로, 트리의 각 노드는 자식을 두 개 가지거나 전혀 가지지 않습니다(리프 노드).

즉, 재귀(recursion)를 활용해 각 노드의 이항 연산을 순차적으로 계산하면 됩니다. 알고리즘의 동작 흐름은 다음과 같습니다.

1. 현재 노드가 NULL이면 0을 반환합니다.
2. 현재 노드가 리프 노드(양쪽 자식이 모두 없음)라면, 해당 값을 정수로 변환해 반환합니다.
3. 그렇지 않다면 왼쪽 서브트리와 오른쪽 서브트리를 각각 재귀적으로 평가합니다.
4. 현재 노드의 연산자에 따라 두 결과값을 연산하여 반환합니다.

솔루션 구현 코드

#include <bits/stdc++.h>
using namespace std;

class node {

    public:
        string value;
        node *left = NULL, *right = NULL;
        node(string x)
        {
            value = x;
        }
};

int solveExpressionTree(node* root) {

    if (!root)
        return 0;

    if (!root->left && !root->right)
        return stoi(root->value);

    int leftSubTreeSol = solveExpressionTree(root->left);
    int rightSubTreeSol = solveExpressionTree(root->right);

    if (root->value == "+")
        return leftSubTreeSol + rightSubTreeSol;

    if (root->value == "-")
        return leftSubTreeSol - rightSubTreeSol;

    if (root->value == "*")
        return leftSubTreeSol * rightSubTreeSol;

    if (root -> value == "/")
        return leftSubTreeSol / rightSubTreeSol;

    return -1;
}

int main()
{
    node *root = new node("/");
    root->left = new node("+");
    root->left->left = new node("9");
    root->left->right = new node("5");
    root->right = new node("*");
    root->right->left = new node("2");
    root->right->right = new node("7");
    cout<<"The evaluation of expression tree is "<<solveExpressionTree(root);
    return 0;
}

실행 결과

The evaluation of expression tree is 1

복잡도 분석

이 솔루션은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)(N은 노드의 개수)입니다. 공간 복잡도 역시 재귀 호출에 따른 스택 사용으로 O(N)입니다.