Xây dựng cây biểu thức từ biểu thức tiền tố (Prefix) trong C++

Cây biểu thức là cây nhị phân biểu diễn biểu thức. Nút trong cây là toán tử, nút lá là toán hạng. Chương trình C++ này xây dựng cây biểu thức từ biểu thức tiền tố và duyệt theo inorder, preorder, postorder.

Thuật toán

Bắt đầu
  Lớp ExpressionTree với các hàm:
  push() - đẩy nút vào stack
  pop() - lấy nút ra khỏi stack
  insert() - chèn ký tự: nếu là chữ số thì push, nếu là toán tử thì pop hai toán hạng, tạo nút mới, push lại
  postOrder() - duyệt hậu tự
  inOrder() - duyệt trung tự
  preOrder() - duyệt tiền tự
Kết thúc

Ví dụ minh họa

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

class TreeN { // Nút cây
public:
    char d;
    TreeN *l, *r;
    TreeN(char d) { this->d = d; this->l = NULL; this->r = NULL; }
};

class StackNod { // Nút stack
public:
    TreeN *treeN;
    StackNod *n;
    StackNod(TreeN* treeN) { this->treeN = treeN; n = NULL; }
};

class ExpressionTree {
private:
    StackNod *top;
public:
    ExpressionTree() { top = NULL; }
    void clear() { top = NULL; }
    void push(TreeN *ptr) {
        if (top == NULL) top = new StackNod(ptr);
        else { StackNod *nptr = new StackNod(ptr); nptr->n = top; top = nptr; }
    }
    TreeN *pop() {
        if (top == NULL) { cout << "Underflow" << endl; return NULL; }
        TreeN *ptr = top->treeN; top = top->n; return ptr;
    }
    TreeN *peek() { return top->treeN; }
    void insert(char val) {
        if (isdigit(val)) { push(new TreeN(val)); }
        else if (val=='+'||val=='-'||val=='*'||val=='/') {
            TreeN *nptr = new TreeN(val);
            nptr->l = pop(); nptr->r = pop(); push(nptr);
        } else { cout << "Invalid Expression" << endl; }
    }
    void buildTree(string eqn) {
        for (int i = eqn.length()-1; i >= 0; i--) insert(eqn[i]);
    }
    void postfix() { postOrder(peek()); }
    void postOrder(TreeN* ptr) {
        if (ptr) { postOrder(ptr->l); postOrder(ptr->r); cout << ptr->d; }
    }
    void infix() { inOrder(peek()); }
    void inOrder(TreeN *ptr) {
        if (ptr) { inOrder(ptr->l); cout << ptr->d; inOrder(ptr->r); }
    }
    void prefix() { preOrder(peek()); }
    void preOrder(TreeN *ptr) {
        if (ptr) { cout << ptr->d; preOrder(ptr->l); preOrder(ptr->r); }
    }
};

int main() {
    string s; ExpressionTree et;
    cout << "\nNhap bieu thuc dang Prefix: "; cin >> s;
    et.buildTree(s);
    cout << "\nPrefix : "; et.prefix();
    cout << "\n\nInfix : "; et.infix();
    cout << "\n\nPostfix : "; et.postfix();
}

Kết quả

Nhap bieu thuc dang Prefix: ++7*626
Prefix : ++7*626
Infix : 7+6*2+6
Postfix : 762*+6+