สร้าง Expression Tree จาก Prefix Expression ใน C++

Expression Tree เป็น Binary Tree ที่ใช้แสดงนิพจน์ทางคณิตศาสตร์ โดยโหนดภายใน (internal nodes) เป็นตัวดำเนินการ (operators) และโหนดใบ (leaf nodes) เป็นตัวถูกดำเนินการ (operands)

อัลกอริทึมสร้างจาก Prefix

1. อ่าน Prefix expression จากขวาไปซ้าย
2. ถ้าเป็นตัวเลข (operand) → สร้างโหนดและ push เข้า stack
3. ถ้าเป็นตัวดำเนินการ (operator) → pop 2 โหนดจาก stack, สร้างโหนดใหม่เป็น parent, push กลับเข้า stack
4. สุดท้าย stack จะเหลือเพียงโหนดเดียว คือ root ของ Expression Tree

ตัวอย่างโค้ด

#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

class ExpressionTree {
private:
    TreeNode* root;
    
    bool isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
    }
    
    bool isOperand(char ch) {
        return isdigit(ch) || isalpha(ch);
    }

public:
    ExpressionTree() : root(nullptr) {}
    
    void buildFromPrefix(const string& prefix) {
        stack<TreeNode*> st;
        
        // อ่านจากขวาไปซ้าย
        for (int i = prefix.length() - 1; i >= 0; --i) {
            char ch = prefix[i];
            
            if (isspace(ch)) continue;
            
            if (isOperand(ch)) {
                st.push(new TreeNode(ch));
            } else if (isOperator(ch)) {
                if (st.size() < 2) {
                    cerr << "Invalid prefix expression" << endl;
                    return;
                }
                TreeNode* node = new TreeNode(ch);
                node->left = st.top(); st.pop();
                node->right = st.top(); st.pop();
                st.push(node);
            }
        }
        
        if (!st.empty()) root = st.top();
    }
    
    // Traversals
    void inorder(TreeNode* node) {
        if (!node) return;
        if (isOperator(node->data)) cout << "(";
        inorder(node->left);
        cout << node->data;
        inorder(node->right);
        if (isOperator(node->data)) cout << ")";
    }
    
    void preorder(TreeNode* node) {
        if (!node) return;
        cout << node->data;
        preorder(node->left);
        preorder(node->right);
    }
    
    void postorder(TreeNode* node) {
        if (!node) return;
        postorder(node->left);
        postorder(node->right);
        cout << node->data;
    }
    
    void printAll() {
        cout << "Prefix:   "; preorder(root); cout << endl;
        cout << "Infix:    "; inorder(root); cout << endl;
        cout << "Postfix:  "; postorder(root); cout << endl;
    }
    
    ~ExpressionTree() {
        // TODO: implement destructor to free memory
    }
};

int main() {
    ExpressionTree et;
    string prefix;
    
    cout << "Enter prefix expression (e.g., ++7*626): ";
    cin >> prefix;
    
    et.buildFromPrefix(prefix);
    et.printAll();
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter prefix expression (e.g., ++7*626): ++7*626
Prefix:   ++7*626
Infix:    (7+((6*2)+6))
Postfix:  762*+6+

การใช้งาน Expression Tree

• การคำนวณนิพจน์: ใช้ postorder traversal กับ stack
• การจัดรูปแบบนิพจน์: แปลงระหว่าง prefix, infix, postfix
• Compiler design: ส่วนหนึ่งของ parsing และ code generation
• Symbolic math: การ微分, integration แบบสัญลักษณ์

ขยายความสามารถ

สามารถเพิ่มรองรับ: ตัวเลขหลายหลัก, ตัวแปร, ฟังก์ชัน (sin, cos), และการประเมินค่า (evaluate) ได้