任务在这个项目中，要求您开发一个二进制表达式树，并使用该树将后缀表达式和中缀表达式相互转换。表达式可包含4种运算符：乘法（*），除法（/），加号（+）和减号（-）。我们假设乘法和除法具有相同的优先级，加号和减号具有相同的优先级，并且乘法和除法的优先级高于加号和减号。所有运算符都是左关联的（即从左到右关联）。此外，表达式可能包含数字（1，129，...）或字母标识符（a，x，var，...）形式的操作数。二进制表达式树：构建一个名为“ BET”的二进制表达式树类。您的BET类必须具有一个名为“ BinaryNode”的嵌套类，才能包含与节点有关的信息（包括元素和指向子节点和父节点的指针）。您可以为BinaryNode的元素字段选择任何类型。此外，BET必须至少支持以下接口功能：
公共界面：
•BET（）-默认的零参数构造函数。建立一棵空树。
•BET（String expr，char mode）-两参数构造函数，其中参数“ mode”指定“ expr”是包含后缀还是后缀表达式的字符串。对于后缀，“模式”的可能值为“ p”，对于中缀表达式，可能的值为“ i”。该树应基于表达式构建。表达式中的标记由空格分隔。理想情况下，应通过调用buildFromPostfix或buildFromInfix来完成。如果构建树失败，则抛出IllegalStateException。
•bool buildFromPostfix（String postfix）-参数“ postfix”是一个包含后缀表达式的字符串。该树应基于后缀表达式构建。后缀表达式中的标记用空格分隔。如果在调用函数之前树中包含节点，则需要首先删除现有节点。如果成功构建了新树，则返回true。如果遇到错误，则返回false。
•bool buildFromInfix（String infix）-参数“ infix”是包含中缀表达式的字符串。该树应基于infix表达式构建。 infix表达式中的标记用空格分隔。如果在调用函数之前树中包含节点，则需要首先删除现有节点。如果成功构建了新树，则返回true。如果遇到错误，则返回false。
•void printInfixExpression（）-打印当前二进制表达式树的中缀表达式。应该通过使用私有（递归）版本来做到这一点
•void printPostfixExpression（）-打印出当前二进制表达式树的后缀表达式。使用私有递归函数来帮助
•int size（）-使用私有递归函数返回树中的节点数
•bool isEmpty（）-如果树为空，则返回true
•int leafNodes（）-返回树中叶节点的数量。 （使用私有递归函数来帮助）
专用帮助器功能（所有必需的私有成员功能必须递归实现）：
•void printInfixExpression（BinaryNode n）：打印相应的带括号的中缀表达式。您不应有不必要的括号。
•void makeEmpty（BinaryNode t）：删除树中所有根为t的节点。
•void printPostfixExpression（BinaryNode n）：打印相应的后缀表达式。
•int size（BinaryNode t）：返回树中根为t的节点数。
•int leafNodes（BinaryNode t）：返回树中根为t的叶节点数。
Postfix Notation：后缀表示法是写无括号的算术表达式的明确方法。定义为，如果（exp1）op（exp2）是运算符为op的正常的全括号表达式，则其后缀版本为pexp1 pexp2 op，其中pexp1是exp1的后缀版本，而pexp2是exp2的后缀版本。单个数字或变量的后缀版本就是该数字或变量。因此，例如，（（5 + 2）*（8-3））/ 4的后缀版本为5 2 + 8 3-* 4 /
从后缀表达式构造BET：从后缀表达式构建二进制表达式树的基本操作非常简单。您只需要一个堆栈。每次遇到操作数（数字，变量）时，请从该操作数创建一个树节点，并将其压入堆栈顶部。如果遇到运算符，只需弹出顶部的两个操作数节点，然后将一个以该运算符为根，两个操作数为左，右子级的新树节点推回堆栈。从表达式中读取每个标记后，堆栈中应有一个树节点，即二叉表达式树。如果大于或小于此值，则表示表达式中有错误。
从中缀表达式构造BET：从中缀表达式（不必带括号）构建二进制表达式树的基本操作与评估算术表达式相似。在这种情况下，您需要两个堆栈，一个用于运算符，一个用于操作数。每次您在表达式中读取操作数时，将其推入操作数堆栈顶部。每次阅读运算符时，将其压入运算符堆栈，但首先弹出并为堆栈中已存在的所有优先级较高或相等的运算符创建子树。每次要为运算符创建子树时，都将弹出该运算符和两个操作数，并使该操作数成为该运算符的左，右子级。然后，将结果子树推回操作数堆栈。当到达表达式的末尾时，请对运算符堆栈上的所有其余运算符执行相同的操作。最后，您应该有一个空的运算符堆栈，并且操作数堆栈上只有一个树节点，它是二进制表达式树的根。将后缀转换为中缀表达式：使用二进制表达式树将后缀表达式转换为中缀表达式需要两个步骤。首先，从后缀表达式构建二进制表达式树。其次，使用树的有序遍历来打印二进制表达式树的节点。
将后缀转换为后缀表达式：使用二进制表达式树将中缀表达式转换为后缀表达式需要两个步骤。首先，从中缀表达式构建二进制表达式树。其次，使用树的后序遍历打印二进制表达式树的节点。请注意，在打印中缀表达式期间，需要添加括号以确保中缀表达式与相应的后缀表达式和二进制表达式树具有相同的值（和相同的评估顺序）。您的结果不应添加不必要的括号。中缀表达式中的标记也应以空格分隔。以下是一些后缀表达式和相应的中缀表达式的示例。
postfix expression infix expression
4 50 6 + + ( 4 + ( 50 + 6 ) )
4 50 + 6 + ( ( 4 + 50 ) + 6 )
4 50 + 6 2 * + ( ( 4 + 50 ) + ( 6 * 2 ) )
4 50 6 + + 2 * ( ( 4 + ( 50 + 6 ) ) * 2 )
a b + c d e + * * ( ( a + b ) * ( c * ( d + e ) ) )
下面还包括一个驱动程序Main.java。这是一个示例测试程序，它将在您的实现上运行一些测试。但是，您的课程将不仅使用此示例驱动程序进行测试。建议您编写自己的其他驱动程序，以进行更全面的测试。此测试程序的输出也包含在下面。
一般要求•适当地记录您的代码，使其易于阅读且易于浏览。•对于此项目，您可以使用Java中的ArrayList和Stack实现。 （java.util.Stack，java.util.ArrayList）•您编写的任何帮助程序功能都应在专用部分
public static void main(String[] args) {
try {
System.out.println("\n\ntest1: a b c + * d -");
BET test = new BET("a b c + * d -" , 'p');
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
System.out.println("\n\ntest2: ( 3 + 2 ) * 3 + 1");
test = new BET("( 3 + 2 ) * 3 + 1" , 'i');
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
System.out.println("\n\ntest3: abc / 2 / f3 + z4 - 1 * 2");
test.buildFromInfix("abc / 2 / f3 + z4 - 1 * 2");
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
System.out.println("\n\ntest4: ( 3 + 2 * 3 + 1");
test = new BET("( 3 + 2 * 3 + 1" , 'i');
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
}
catch(IllegalStateException e) {
System.out.println(e.getMessage());
}
}
}
输出：
test1: a b c + * d -
postfix: a b c + * d -
infix: ( ( a * ( b + c ) ) - d )
size: 7
isEmpty: false
# of leaves: 4
test2: ( 3 + 2 ) * 3 + 1
postfix: 3 2 + 3 * 1 +
infix: ( ( ( 3 + 2 ) * 3 ) + 1 )
size: 7
isEmpty: false
# of leaves: 4
test3: abc / 2 / f3 + z4 - 1 * 2
postfix: abc 2 / f3 / z4 + 1 2 * -
infix: ( ( ( ( abc / 2 ) / f3 ) + z4 ) - ( 1 * 2 ) )
size: 11
isEmpty: false
# of leaves: 6
test4: ( 3 + 2 * 3 + 1
Invalid notation: ( 3 + 2 * 3 + 1
这是一个经典问题，可以使用堆栈数据结构来解决。看看这篇文章。