二叉表达式树将后缀转换为中缀，反之亦然
Binary expression tree converting postfix to infix and vice versa
任务
在这个项目中，你被要求开发一个二叉表达式树，并使用该树将后缀和中缀表达式相互转换。一个表达式可能包含 4 种类型的运算符：乘法 (*)、除法 (/)、加号 (+) 和减号 (-)。我们假设乘法和除法具有相同的优先级，加号和减号具有相同的优先级，乘法和除法的优先级高于加号和减号。所有运算符都是左关联的（即从左到右关联）。此外，表达式可能包含数字形式的操作数 (1, 129, ...) 或字母标识符 (a, x, var, ...)。
二叉表达式树：构建一个二叉表达式树class，名为"BET"。您的 BET class 必须有一个名为 "BinaryNode" 的嵌套 class 以包含与节点相关的信息（包括，例如，元素和指向子节点和父节点的指针）。您可以为 BinaryNode 的元素字段选择任何类型。另外，BET至少要支持以下接口功能：
Public接口：
•BET() -- 默认零参数构造函数。构建一个空树。
•BET(String expr, char mode) -- 双参数构造函数，其中参数 "mode" 指定 "expr" 是否为包含后缀或中缀表达式。 "mode" 的可能值为后缀 "p" 和中缀表达式 "i" 。应根据表达式构建树。表达式中的标记由 space 分隔。理想情况下，这应该通过调用 buildFromPostfix 或 buildFromInfix 来完成。如果构建树失败，则抛出 IllegalStateException。
•bool buildFromPostfix(String postfix) -- 参数 "postfix" 是一个包含后缀表达式的字符串。应根据后缀表达式构建树。后缀表达式中的标记由 space 分隔。如果树在调用函数之前包含节点，则需要先删除现有节点。 Return 如果新树构建成功则为真。 Return 如果遇到错误则为 false。
•bool buildFromInfix(String infix) -- 参数 "infix" 是包含中缀表达式的字符串。应根据中缀表达式构建树。中缀表达式中的标记由 space 分隔。如果树在调用函数之前包含节点，则需要先删除现有节点。 Return 如果新树构建成功则为真。 Return 如果遇到错误则为 false。
•void printInfixExpression() -- 打印出当前二叉表达式树的中缀表达式。应该通过使用私有（递归）版本来做到这一点
•void printPostfixExpression() -- 打印出当前二叉表达式树的后缀表达式。使用私有递归函数来帮助
•int size() -- returns 使用私有递归函数得到树中的节点数
•bool isEmpty() -- 如果树为空return则为真
•int leafNodes() -- Return 树中叶节点的数量。 （使用私有递归函数来帮忙）
私有辅助函数（所有必需的私有成员函数必须递归实现）：
•void printInfixExpression(BinaryNode n)：打印相应的全括号中缀表达式。你不应该有不必要的括号。
•void makeEmpty(BinaryNode t)：删除树中所有以t为根的节点。
•void printPostfixExpression(BinaryNode n)：打印对应的后缀表达式。
•int size(BinaryNode t): return树中以t为根的节点数。
•int leafNodes(BinaryNode t)：return树中以t为根的叶节点数。
后缀表示法：后缀表示法是一种不含括号的算术表达式的明确表达方式。它被定义为如果 (exp1) op (exp2) 是一个正常的完全括号表达式，其操作是 op，则它的后缀版本是 pexp1 pexp2 op 其中 pexp1 是 exp1 的后缀版本，pexp2 是 exp2 的后缀版本。单个数字或变量的后缀版本就是该数字或变量。因此，例如 ((5+2) * (8-3))/4 的后缀版本是 5 2 + 8 3 - * 4 /
Constructing BET from postfix expression: 从后缀表达式构建二叉表达式树的基本操作非常简单。你只需要一堆。每次遇到操作数（数字、变量）时，从中创建一个树节点并将其压入栈顶。如果遇到运算符，就弹出栈顶的两个操作数节点，将一个以该运算符为根，两个操作数为左右子节点的新树节点压回栈中。从表达式中读取每个标记后，堆栈中应该有一个树节点，即二叉表达式树。如果多于或少于该值，则表示表达式有误。
Constructing BET from infix expression: 从中缀表达式（不一定带括号）构建二叉表达式树的基本操作与计算算术表达式类似。在这种情况下，您需要两个堆栈，一个用于运算符，一个用于操作数。每次读取表达式中的操作数时，将其压入操作数堆栈的顶部。每次读取一个运算符时，将其压入运算符堆栈，但首先为堆栈中已经存在的所有更高或相等优先级运算符弹出并创建子树。每次你想为一个运算符创建一个子树时，你弹出运算符和两个操作数，并使操作数成为运算符的左右子节点。然后将生成的子树推回操作数堆栈。当您到达表达式的末尾时，对运算符堆栈中的所有剩余运算符执行相同的操作。最后，您应该有一个空的运算符堆栈，操作数堆栈上只有一个树节点，这是您的二叉表达式树的根。
将后缀转换为中缀表达式：。使用二叉表达式树将后缀表达式转换为中缀表达式涉及两个步骤。首先，从后缀表达式构建二叉表达式树。其次，使用树的中序遍历打印二叉表达式树的节点。
将中缀表达式转换为后缀表达式：使用二叉表达式树将中缀表达式转换为后缀表达式涉及两个步骤。首先，从中缀表达式构建二叉表达式树。其次，使用树的后序遍历打印二叉表达式树的节点。
注意，在打印中缀表达式时，需要加上括号，以保证中缀表达式与对应的后缀表达式和二叉表达式树具有相同的值（以及相同的求值顺序）。您的结果不应添加不必要的括号。中缀表达式中的标记也应该用 space 分隔。下面是几个后缀表达式和对应的中缀表达式的例子。
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。这是一个示例测试程序，将 运行 对您的实现进行一些测试。但是，您的 class 将使用更多示例驱动程序进行测试。建议您自己编写其他驱动程序，以便进行更彻底的测试。该测试程序的输出也包含在下面。
一般要求
• 适当地记录您的代码，使其可读且易于浏览。
• 对于这个项目，您可以使用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
这是一个经典的问题，可以使用堆栈数据结构来解决。看看这篇文章。
任务 在这个项目中，你被要求开发一个二叉表达式树，并使用该树将后缀和中缀表达式相互转换。一个表达式可能包含 4 种类型的运算符：乘法 (*)、除法 (/)、加号 (+) 和减号 (-)。我们假设乘法和除法具有相同的优先级，加号和减号具有相同的优先级，乘法和除法的优先级高于加号和减号。所有运算符都是左关联的（即从左到右关联）。此外，表达式可能包含数字形式的操作数 (1, 129, ...) 或字母标识符 (a, x, var, ...)。 二叉表达式树：构建一个二叉表达式树class，名为"BET"。您的 BET class 必须有一个名为 "BinaryNode" 的嵌套 class 以包含与节点相关的信息（包括，例如，元素和指向子节点和父节点的指针）。您可以为 BinaryNode 的元素字段选择任何类型。另外，BET至少要支持以下接口功能：
Public接口：
•BET() -- 默认零参数构造函数。构建一个空树。
•BET(String expr, char mode) -- 双参数构造函数，其中参数 "mode" 指定 "expr" 是否为包含后缀或中缀表达式。 "mode" 的可能值为后缀 "p" 和中缀表达式 "i" 。应根据表达式构建树。表达式中的标记由 space 分隔。理想情况下，这应该通过调用 buildFromPostfix 或 buildFromInfix 来完成。如果构建树失败，则抛出 IllegalStateException。
•bool buildFromPostfix(String postfix) -- 参数 "postfix" 是一个包含后缀表达式的字符串。应根据后缀表达式构建树。后缀表达式中的标记由 space 分隔。如果树在调用函数之前包含节点，则需要先删除现有节点。 Return 如果新树构建成功则为真。 Return 如果遇到错误则为 false。
•bool buildFromInfix(String infix) -- 参数 "infix" 是包含中缀表达式的字符串。应根据中缀表达式构建树。中缀表达式中的标记由 space 分隔。如果树在调用函数之前包含节点，则需要先删除现有节点。 Return 如果新树构建成功则为真。 Return 如果遇到错误则为 false。
•void printInfixExpression() -- 打印出当前二叉表达式树的中缀表达式。应该通过使用私有（递归）版本来做到这一点
•void printPostfixExpression() -- 打印出当前二叉表达式树的后缀表达式。使用私有递归函数来帮助
•int size() -- returns 使用私有递归函数得到树中的节点数
•bool isEmpty() -- 如果树为空return则为真
•int leafNodes() -- Return 树中叶节点的数量。 （使用私有递归函数来帮忙）
私有辅助函数（所有必需的私有成员函数必须递归实现）：
•void printInfixExpression(BinaryNode n)：打印相应的全括号中缀表达式。你不应该有不必要的括号。
•void makeEmpty(BinaryNode t)：删除树中所有以t为根的节点。
•void printPostfixExpression(BinaryNode n)：打印对应的后缀表达式。
•int size(BinaryNode t): return树中以t为根的节点数。
•int leafNodes(BinaryNode t)：return树中以t为根的叶节点数。
后缀表示法：后缀表示法是一种不含括号的算术表达式的明确表达方式。它被定义为如果 (exp1) op (exp2) 是一个正常的完全括号表达式，其操作是 op，则它的后缀版本是 pexp1 pexp2 op 其中 pexp1 是 exp1 的后缀版本，pexp2 是 exp2 的后缀版本。单个数字或变量的后缀版本就是该数字或变量。因此，例如 ((5+2) * (8-3))/4 的后缀版本是 5 2 + 8 3 - * 4 /
Constructing BET from postfix expression: 从后缀表达式构建二叉表达式树的基本操作非常简单。你只需要一堆。每次遇到操作数（数字、变量）时，从中创建一个树节点并将其压入栈顶。如果遇到运算符，就弹出栈顶的两个操作数节点，将一个以该运算符为根，两个操作数为左右子节点的新树节点压回栈中。从表达式中读取每个标记后，堆栈中应该有一个树节点，即二叉表达式树。如果多于或少于该值，则表示表达式有误。
Constructing BET from infix expression: 从中缀表达式（不一定带括号）构建二叉表达式树的基本操作与计算算术表达式类似。在这种情况下，您需要两个堆栈，一个用于运算符，一个用于操作数。每次读取表达式中的操作数时，将其压入操作数堆栈的顶部。每次读取一个运算符时，将其压入运算符堆栈，但首先为堆栈中已经存在的所有更高或相等优先级运算符弹出并创建子树。每次你想为一个运算符创建一个子树时，你弹出运算符和两个操作数，并使操作数成为运算符的左右子节点。然后将生成的子树推回操作数堆栈。当您到达表达式的末尾时，对运算符堆栈中的所有剩余运算符执行相同的操作。最后，您应该有一个空的运算符堆栈，操作数堆栈上只有一个树节点，这是您的二叉表达式树的根。 将后缀转换为中缀表达式：。使用二叉表达式树将后缀表达式转换为中缀表达式涉及两个步骤。首先，从后缀表达式构建二叉表达式树。其次，使用树的中序遍历打印二叉表达式树的节点。
将中缀表达式转换为后缀表达式：使用二叉表达式树将中缀表达式转换为后缀表达式涉及两个步骤。首先，从中缀表达式构建二叉表达式树。其次，使用树的后序遍历打印二叉表达式树的节点。 注意，在打印中缀表达式时，需要加上括号，以保证中缀表达式与对应的后缀表达式和二叉表达式树具有相同的值（以及相同的求值顺序）。您的结果不应添加不必要的括号。中缀表达式中的标记也应该用 space 分隔。下面是几个后缀表达式和对应的中缀表达式的例子。
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。这是一个示例测试程序，将 运行 对您的实现进行一些测试。但是，您的 class 将使用更多示例驱动程序进行测试。建议您自己编写其他驱动程序，以便进行更彻底的测试。该测试程序的输出也包含在下面。
一般要求 • 适当地记录您的代码，使其可读且易于浏览。 • 对于这个项目，您可以使用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
这是一个经典的问题，可以使用堆栈数据结构来解决。看看这篇文章。