在C中将句子表达到二叉树

Question

我必须将中缀表达式解析为二叉树.

表达式是:

 (((x1 + 5.12) ? (x2 ? 7.68))/x3) 

我真的不知道如何解释表达式.有人知道如何处理这个问题吗？

Answer 1

你的任务并不那么难,首先你要熟悉符号类型,然后用表达式解析.

通常,要解析和评估(中缀)表达式,您需要:

• 读取并标记它,即将每个符号分类为:操作数,操作等.

• 从中缀转换为二进制表达式树:这通常使用诸如分流码算法之类的算法来完成.

• 创建一个定义操作优先级的语法,并允许严格的¹阶表达式求值.

使用中缀表示法编写的表达式稍微难以解析,这就是为什么通常将它们转换为更"机器友好"的版本,例如(反向)波兰表示法,其提供一些优点,其中包括消除括号的需要.

所以,你可以看到这大致是一幅大图,你的任务就是它的一部分.以下是二进制表达式树的可视化:2 * 3 / ( 2 – 1 ) + 5 * ( 4 – 1 )

这里有更多关于主题和C++中的示例实现.

^{1.在你的情况下遵守代数规则.}