【Java】构建表达式二叉树和表达式二叉树求值

问题背景

1. 实现一个简单的计算器。通过键盘输入一个包含圆括号、加减乘除等符号组成的算术表达式字符串，输出该算术表达式的值。要求：

（1）系统至少能实现加、减、乘、除等运算；

（2）利用二叉树算法思想求解表达式的值，先构造由表达式构成的二叉树，按中序、后序遍历的方式输出二叉树中的结点，然后再利用通过对二叉树进行后序遍历求解算术表达式的值。

思路描述

• 构建表达式二叉树：先用栈将算术表达式转成后缀表达式（具体思路参考），再根据后缀表达式构建表达式二叉树，构建过程：从左到右扫描后缀表达式的每个元素：如果当前元素是操作数，则创建一个只包含该操作数的节点，并将该节点压入栈中；如果当前元素是操作符，则创建一个只包含该操作符的节点，并从栈中弹出两个节点作为其左右子节点，再将该节点压入栈中。最后栈中唯一的节点即为根节点。
• 表达式二叉树求值：后序遍历二叉树，递归计算左右子树的值，代入运算符计算

 代码实现

//二叉链表存储二叉树
public class TreeNode {String value;TreeNode left;TreeNode right;public TreeNode(String value){this.value=value;}public TreeNode(String value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}
}
public class Calculator {private TreeNode root;public Calculator() {root = null;}public Calculator(TreeNode root) {this.root = root;}//中缀转后缀，List中每个元素就是后缀表达式中每个操作数或运算符public static List<String> infixToPostfix(String infixExpression){Stack<Character> operatorStack=new Stack<>();List<String> postfixExpression=new ArrayList<>();for(int i=0;i<infixExpression.length();i++){//如果是数字if(Character.isDigit(infixExpression.charAt(i))){//可能是多位的数StringBuilder temp=new StringBuilder();temp.append(infixExpression.charAt(i));while (++i<infixExpression.length()&&Character.isDigit(infixExpression.charAt(i))){temp.append(infixExpression.charAt(i));}postfixExpression.add(temp.toString());i--;//while判断完后，i多往后挪了一位，所以要-1}//如果是左括号else if(infixExpression.charAt(i)=='('){operatorStack.push(infixExpression.charAt(i));}//如果是右括号，去匹配左括号else if(infixExpression.charAt(i)==')'){while (!operatorStack.empty()&&operatorStack.peek()!='('){postfixExpression.add(operatorStack.pop()+"");}operatorStack.pop();}//如果是+-*/else {//将优先级<=当前运算符优先级的运算符pop出来，追加到后缀表达式中while (!operatorStack.empty()&&getPrecedence(infixExpression.charAt(i))<=getPrecedence(operatorStack.peek())){postfixExpression.add(operatorStack.pop()+"");}operatorStack.push(infixExpression.charAt(i));}}//将栈中剩余的运算符依次pop出来追加到结果中while (!operatorStack.empty()){postfixExpression.add(operatorStack.pop()+"");}return postfixExpression;}//在中缀转后缀时要判断符号优先级private static int getPrecedence(char operator) {switch (operator) {case '+':case '-':return 1;case '*':case '/':case '%':return 2;default:return 0;}}//利用后缀表达式构建表达式二叉树public static TreeNode buildExpressionTree(List<String> postfixExpression){Stack<TreeNode> stack=new Stack<>();//从左至右遍历后缀表达式for(String str:postfixExpression){//如果是运算数if(str.charAt(0)>=48&&str.charAt(0)<=57){TreeNode treeNode = new TreeNode(str, null, null);stack.push(treeNode);} else {//如果是运算符//从栈中弹出两个节点TreeNode pop1 = stack.pop();TreeNode pop2 = stack.pop();TreeNode treeNode = new TreeNode(str, pop1, pop2);stack.push(treeNode);}}//最后栈中剩余的节点就是二叉树根节点return stack.peek();}//中序遍历表达式二叉树(左根右)public static void inorderTraversal(TreeNode treeNode){if(treeNode==null)return;inorderTraversal(treeNode.left);System.out.print(treeNode.value+" ");inorderTraversal(treeNode.right);}//后序遍历表达式二叉树（左右根）public static void postorderTraversal(TreeNode treeNode){if(treeNode==null)return;postorderTraversal(treeNode.left);postorderTraversal(treeNode.right);System.out.print(treeNode.value+" ");}//后序遍历表达式二叉树求值public int evaluateExpression(){return evaluateExpression(root);}public int evaluateExpression(TreeNode root){if(root==null){return 0;}// 递归计算左右子树的值int leftValue = evaluateExpression(root.left);int rightValue = evaluateExpression(root.right);switch (root.value){case "+":return leftValue+rightValue;case "-":return leftValue-rightValue;case "*":return leftValue*rightValue;case "/":return leftValue/rightValue;default:// 如果是操作数，则返回对应的整数值return Integer.valueOf(root.value);}}
}

 运行效果

public class Main {public static void main(String[] args) {System.out.println("请输入你要计算的表达式：");Scanner sc = new Scanner(System.in);String infixExpression = sc.next();List<String> postfixExpression = Calculator.infixToPostfix(infixExpression);//中缀转后缀TreeNode binaryTree = Calculator.buildExpressionTree(postfixExpression);//利用后缀表达式构建表达式二叉树System.out.print("中序遍历：");Calculator.inorderTraversal(binaryTree);//中序遍历System.out.println();System.out.print("后序遍历：");Calculator.postorderTraversal(binaryTree);//后序遍历System.out.println();Calculator calculator = new Calculator(binaryTree);int i = calculator.evaluateExpression();System.out.println("值为："+i);}
}