分析树或表达式树

Question

我正在做一个命令行计算器,所以我需要解析表达式.

calc 2*(3+4)*5

我已完成扫描仪步骤,返回令牌的数组.现在我正处于解析器步骤.但是我不清楚如何做一个解析器/表达式树.

这就是我到目前为止所做的一切:

NODE* create_node(TOKEN* t) {
    NODE* n = (NODE*)malloc(sizeof(NODE));
    n->t = t;
    n->l = n->r = 0;
    return n;
}

void insert_node(NODE** top, NODE** n) {
    if (!*top) {
        *top = *n;
        return;
    }

    if (!(*top)->l) insert_node(&(*top)->l, n);
    else
    if (!(*top)->r) insert_node(&(*top)->r, n);
    else
        insert_node(&(*top)->l, n);
}

然后我传递令牌数组,如:

while (*tokens != 0) {
    NODE* n = create_node(*tokens++);
    insert_node(&root, &n);
}

你可以看到我的树只向左抬起.我不知道如何通过顶部的操作员和数字作为叶子(包括运算符优先顺序)进行排序.

我会很感激启发,也喜欢编程(代码)术语.

Answer 1

您创建节点的代码对我来说没问题.问题是你需要代码来弄清楚如何正确构建二叉树.您不能只在任何找到NULL指针的地方粘贴节点.

你的示例表达式: 2*(3+4)*5

会变成这样的东西:

    *
   / \
  *   5
 / \
2   +
   / \
  3   4

你的老师应该已经告诉你如何做到这一点.

当我在大学时,我编写了这种代码,我们编写了自己的"递归下降解析器".另一种流行的方法是使用像GNU Bison这样的系统.

你应该检查你的笔记,看看老师对此有何看法,并问老师你是否真的不知道.

http://en.wikipedia.org/wiki/Recursive_descent_parser

http://en.wikipedia.org/wiki/GNU_bison