我想建立中缀计算器.我选择的方法是使用节点中的运算符和叶子中的操作数解析树中的输入,然后从下到上遍历树(从高优先级运算符到下层).

树的例子：

                         (12 + 8) / 2 - 5

                                –
                              /   \
                            '/'    5
                            / \
                           +   2    
                          / \  
                         12  8

第一：我是Java的新手,我应该选择哪种数据结构,或者我需要用自己的树实现创建新类？

第二：处理括号优先级的最佳方法是什么？

解决方法:

您应该使用一个小类层次结构,其中操作数被子类化为Operation和Literal. Operation有一个字段供运算符使用(最好：枚举)和两个操作数字段.

解析器可以创建Operation和Literal对象,并将它们的引用存储到包含的Operation中.

括号消失,因为结果树(如Q中所示)将根据优先级进行组织：按括号分组,然后按运算符优先级,最后从左到右.

你可以编写一个简单的递归下降解析器,不需要为这个小小的学术练习设置antlr.

稍后这是算术表达式的简单语法的BNF：

<expression> ::= <term> | <term> <addop> <expression>
<term>       ::= <factor> | <term> <mulop> <factor>
<factor>     ::= <constant> | (" <expression> ")"
<constant>   ::= <digit> | <digit> <constant>
<addop>      ::= "+" | "-"
<mulop>      ::= "*" | "/"
<digit>      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

递归下降解析器包括通过查找终端(括号,运算符,数字)并根据备选方案之一组成非终端来解析非终端的方法.成功时,返回Literal或Operation对象,并将其合并到调用者组成的对象中.