解析器树或表达式树

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

Answer 2

@Fabricio：提示。尝试将您的输入（中缀表达式）转换为后缀或前缀表达式。在转换它们时将令牌推入堆栈。弹出每个元组（一个操作符和两个操作数）评估并将结果推送到堆栈。重复，直到堆栈为空。您可以在输入表达式中添加冗余大括号，以便轻松实施运算符优先级（但需要付出代价，否则将不得不说服您的教授:)）。

Answer 3

参见这些链接的

1. An infix to postfix parser
2. An infix to binary-expression-tree parser

两种实现为C++实现使用堆栈如已经提及。在二元表达式树中缀的情况下，使用两个堆栈，一个用于运算符，一个用于操作数。