Chương trình C++ triển khai thuật toán cây biểu thức (Expression Tree)

Cây biểu thức (Expression Tree) về cơ bản là một cây nhị phân dùng để biểu diễn các biểu thức. Trong cây biểu thức, các nút nội bộ tương ứng với các toán tử và mỗi nút lá tương ứng với một toán hạng. Dưới đây là chương trình C++ triển khai thuật toán cây biểu thức, nhận biểu thức hậu tố (postfix) làm đầu vào và tạo ra cây biểu thức tương ứng được duyệt theo thứ tự inorder.

Thuật toán

Bắt đầu
  Hàm construct_expression_tree():
    Flag = 1 khi là toán hạng.
    Flag = -1 khi là toán tử.
    S = suffix[0] nghĩa là đọc toán hạng đầu tiên từ biểu thức.
  Với i = 0 cho đến khi s != 0
    Kiểm tra ký hiệu là toán hạng hay toán tử.
    Gọi hàm void inorder() để duyệt inorder.
    In kết quả.
    Tăng i
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 inOrder(n *tree) {
    if (tree != NULL) {
        inOrder(tree->l);
        cout << tree->d;
        inOrder(tree->r);
    }
}

int main(int argc, char **argv) {
    cout << "Nhập biểu thức hậu tố (Postfix): ";
    cin >> pf;
    construct_expression_tree(pf);
    cout << "\nBiểu thức trung tố (Infix): ";
    inOrder(a[0]);
    return 0;
}

Kết quả đầu ra

Nhập biểu thức hậu tố (Postfix): 762*+6+
Biểu thức trung tố (Infix): 7+6*2+6