การประเมินต้นไม้นิพจน์ใน C++

บทนำ

ในปัญหานี้ เราได้รับต้นไม้นิพจน์ (Expression Tree) ที่ประกอบด้วยการดำเนินการทางคณิตศาสตร์แบบทวิภาค เช่น +, -, *, / เป้าหมายคือการประเมินค่าของต้นไม้นิพจน์และส่งคืนผลลัพธ์

ต้นไม้นิพจน์ (Expression Tree) คืออะไร?

ต้นไม้นิพจน์เป็นชนิดหนึ่งของต้นไม้แบบทวิภาค (Binary Tree) ที่แต่ละโหนดจะเป็นตัวดำเนินการ (Operator) หรือตัวถูกดำเนินการ (Operand) โดยมีการกระจายดังนี้:

• โหนดใบ (Leaf nodes) คือค่าที่จะนำไปดำเนินการ
• โหนดที่ไม่ใช่ใบ (Non-leaf nodes) ประกอบด้วยตัวดำเนินการแบบทวิภาค ที่ระบุการดำเนินการที่จะทำ

ตัวอย่างเพื่อความเข้าใจ

อินพุต:

เอาต์พุต: 1

คำอธิบาย:

การถอดรหัสต้นไม้นิพจน์:

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

แนวทางแก้ปัญหา

วิธีแก้ที่เรียบง่ายคือการดำเนินการทีละขั้นตอนจากราก (Root) สำหรับตัวถูกดำเนินการ เราจะแก้ปัญหาย่อยของต้นไม้รอง (Subtree) เนื่องจากทุกการดำเนินการเป็นแบบทวิภาค โหนดของต้นไม้จึงมีลูกสองตัวหรือไม่มีเลย

เราจะใช้การเรียกซ้ำ (Recursion) เพื่อแก้ปัญหาการดำเนินการแบบทวิภาคของแต่ละโหนด

โปรแกรมตัวอย่าง

#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