Đánh giá cây biểu thức trong C++

Trong bài toán này, chúng ta được cho một cây biểu thức bao gồm các phép toán nhị phân như +, -, *, /. Nhiệm vụ là đánh giá giá trị của cây biểu thức và trả về kết quả.

Cây biểu thức (Expression Tree)

Cây biểu thức là một loại cây nhị phân đặc biệt, trong đó mỗi nút chứa một toán tử hoặc một toán hạng, được phân bố như sau:

• Các nút lá (leaf nodes) chứa các giá trị (toán hạng) sẽ được thực hiện phép toán.
• Các nút không phải lá (non-leaf nodes) chứa các toán tử nhị phân biểu thị phép toán cần thực hiện.

Ví dụ minh họa

Đầu vào:

Đầu ra: 1

Giải thích:

Giải mã cây biểu thức:

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

Phương pháp giải

Một giải pháp đơn giản là thực hiện đệ quy từ gốc cây. Đối với các nút lá (toán hạng), ta trả về giá trị của nút đó. Đối với các nút nội bộ (toán tử), ta đệ quy tính giá trị của cây con bên trái và bên phải, sau đó áp dụng toán tử tương ứng. Vì tất cả các phép toán đều là nhị phân, mỗi nút sẽ có đúng hai nút con hoặc không có nút con nào.

Chương trình minh họa

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

class Node {
public:
    string value;
    Node *left = nullptr, *right = nullptr;
    Node(string x) {
        value = x;
    }
};

int solveExpressionTree(Node* root) {
    if (!root) return 0;
    // Nếu là nút lá (toán hạng)
    if (!root->left && !root->right)
        return stoi(root->value);

    int leftVal = solveExpressionTree(root->left);
    int rightVal = solveExpressionTree(root->right);

    if (root->value == "+") return leftVal + rightVal;
    if (root->value == "-") return leftVal - rightVal;
    if (root->value == "*") return leftVal * rightVal;
    if (root->value == "/") return leftVal / rightVal;

    return -1; // Toán tử không hợp lệ
}

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 << "Kết quả đánh giá cây biểu thức là " << solveExpressionTree(root);
    return 0;
}

Đầu ra

Kết quả đánh giá cây biểu thức là 1