解析树或表达式树

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);
}

你可以看到我的树只向左生长。我不知道如何按运算符在顶部排序，并按叶子节点包括运算符优先级顺序进行排序。

如果能够提供编程（代码）方面的启示，我将不胜感激。

- Fabricio

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

- steveha

---

+1。另外，看看你的编程和数据结构教材对这个问题的解释，它应该在里面。 - catchmeifyoutry

Answer 2

@Fabricio: 提示。尝试将您的输入（中缀表达式）转换为后缀或前缀表达式。转换时将标记推入堆栈。弹出每个元组（一个运算符和两个操作数）进行评估，并将结果推入堆栈。重复此过程，直到堆栈为空。您可以在输入表达式中添加冗余括号以便于强制运算符优先级（但会损失一些分数，或者您必须说服您的教授 :)）。

- mK7

Answer 3

请参考以下链接，了解C++实现的相关内容：

1. 中缀表达式转后缀表达式解析器
2. 中缀表达式转二叉表达式树解析器

这两个实现都使用了堆栈，正如之前提到的那样。在将中缀表达式转换为二叉表达式树的情况下，使用了两个堆栈，一个用于操作符，一个用于操作数。

- Kurt Krueckeberg