Chương trình C++ xây dựng cây biểu thức cho biểu thức hậu tố

Cây biểu thức (expression tree) về cơ bản là cây nhị phân dùng để biểu diễn biểu thức. Trong cây biểu thức, nút tương ứng với toán tử và mỗi nút lá tương ứng với toán hạng. Đây là chương trình C++ xây dựng cây biểu thức cho biểu thức hậu tố (postfix) với duyệt inorder, preorder, postorder.

Thuật toán

Bắt đầu
  Hàm r() nhận tham số ký tự.
    Nếu ký tự là + - * / thì trả về -1.
    Nếu ký tự từ A-Z thì trả về 1.
    Nếu ký tự từ a-z thì trả về 1.
    Ngược lại trả về -100.
  Hàm construct_expression_tree() xây dựng cây biểu thức.
  Hàm push() đẩy giá trị vào stack.
  Hàm pop() lấy giá trị từ stack.
  Hàm preOrder() duyệt pre-order.
  Hàm inOrder() duyệt in-order.
  Hàm postOrder() duyệt post-order.
Kết thúc.

Mã ví dụ

#include <iostream>
using namespace std;

struct n {
    char d;
    n *l;
    n *r;
};

char pf[50];
int top = -1;
n *a[50];

int r(char inputch) {
    if (inputch == '+' || inputch == '-' || inputch == '*' || inputch == '/')
        return (-1);
    else if (inputch >= 'A' || inputch <= 'Z')
        return (1);
    else if (inputch >= 'a' || inputch <= 'z')
        return (1);
    else
        return (-100);
}

void push(n *tree) {
    top++;
    a[top] = tree;
}

n *pop() {
    top--;
    return (a[top + 1]);
}

void construct_expression_tree(char *suffix) {
    char s;
    n *newl, *p1, *p2;
    int flag;
    s = suffix[0];
    for (int i = 1; s != 0; i++) {
        flag = r(s);
        if (flag == 1) {
            newl = new n;
            newl->d = s;
            newl->l = NULL;
            newl->r = NULL;
            push(newl);
        } else {
            p1 = pop();
            p2 = pop();
            newl = new n;
            newl->d = s;
            newl->l = p2;
            newl->r = p1;
            push(newl);
        }
        s = suffix[i];
    }
}

void preOrder(n *tree) {
    if (tree != NULL) {
        cout << tree->d;
        preOrder(tree->l);
        preOrder(tree->r);
    }
}

void inOrder(n *tree) {
    if (tree != NULL) {
        inOrder(tree->l);
        cout << tree->d;
        inOrder(tree->r);
    }
}

void postOrder(n *tree) {
    if (tree != NULL) {
        postOrder(tree->l);
        postOrder(tree->r);
        cout << tree->d;
    }
}

int main(int argc, char **argv) {
    cout << "Nhập biểu thức hậu tố: ";
    cin >> pf;
    construct_expression_tree(pf);
    cout << "\nDuyệt In-Order: ";
    inOrder(a[0]);
    cout << "\nDuyệt Pre-Order: ";
    preOrder(a[0]);
    cout << "\nDuyệt Post-Order: ";
    postOrder(a[0]);
    return 0;
}

Kết quả

Nhập biểu thức hậu tố: 762*+6+
Duyệt In-Order: 7+6*2+6
Duyệt Pre-Order: ++7*626
Duyệt Post-Order: 762*+6+