我正在互联网上寻找一种将代数表达式转换为二叉树的逻辑。
我只能找到那些首先将代数表达式转换为后缀或前缀,然后将其转换为二进制树的表达式。
我确实尝试了使用逻辑,但它并不是在所有情况下都有效,问题是选择正确的操作数作为根父节点。我找不到一个通用的逻辑来破解这个问题。
我只是想知道,如果可能的话。
有任何指向外部链接或逻辑答案的指针可以让我朝着正确的方向前进吗?
编辑
是的语法树
所以这个表达式
A+(B-C)*D+E*F
应该翻译成
|-(+)-|
| |
|---(*)---| |---(*)---|
| | | |
|---(+)---| D E F
| |
| |
A |--( - )--|
| |
B C
我的简单建议是:
- 解析表达式并将其分离,如
A
、+(B-C)*D
和+E*F
- 尝试按变量/运算的数量对这些组进行分组,这样您就可以将表达式大致一分为二——例如,将
A
和-(E*F)
分组为一组——A - E*F
,另一组为+(B-C)*D
。现在,您可以递归地将每个组划分为节点和叶
编辑:
这会导致类似的结果
步骤1:
String left = "A - E*F";
String right = "+(B-C)*D";
步骤2:
|------------(+)---------|
| |
|---(-)---| |---(*)---|
| | | |
| | | D
A |--(*)--| |---(-)---|
| | | |
E F B C
当然,所有这些都意味着您的解析器应该知道操作顺序