【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);
    }
}

?