gpt4 book ai didi

c - 解析器树或表达式树

转载 作者:太空狗 更新时间:2023-10-29 15:53:00 24 4
gpt4 key购买 nike

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

calc 2*(3+4)*5

我已经完成了扫描步骤,返回了一个 token 数组。现在我在解析器步骤。但是我不知道如何做解析器/表达式树。

这就是我目前所拥有的一切:

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

然后我像这样传递 token 数组:

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

如您所见,我的树只是向左升起。我不知道如何让它按顶部的运算符和数字作为叶子进行排序,包括运算符优先顺序。

我希望能从编程(代码)方面得到启发。

最佳答案

我觉得你创建节点的代码没问题。问题是您需要代码来弄清楚如何正确构建二叉树。您不能只在发现 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

关于c - 解析器树或表达式树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11024682/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com