数据结构程序设计——使用栈和二叉树对中缀表达式求值

实验须知：

代码实现：

import java.util.Scanner;
import java.util.Stack;

class TreeNodes {
    char val;
    TreeNodes left, right;

    public TreeNodes(char val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class ExpressionTree {
    public static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    public static int getPriority(char c) {
        if (c == '+' || c == '-') {
            return 1;
        } else if (c == '*' || c == '/') {
            return 2;
        }
        return 0;
    }

    public static TreeNodes buildExpressionTree(String expression) {
        Stack<TreeNodes> nodeStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();

        for (char c : expression.toCharArray()) {
            if (Character.isDigit(c)) {
                nodeStack.push(new TreeNodes(c));
            } else if (isOperator(c)) {
                while (!opStack.isEmpty() && getPriority(opStack.peek()) >= getPriority(c)) {
                    TreeNodes right = nodeStack.pop();
                    TreeNodes left = nodeStack.pop();
                    TreeNodes operatorNode = new TreeNodes(opStack.pop());
                    operatorNode.left = left;
                    operatorNode.right = right;
                    nodeStack.push(operatorNode);
                }
                opStack.push(c);
            }
        }

        while (!opStack.isEmpty()) {
            TreeNodes right = nodeStack.pop();
            TreeNodes left = nodeStack.pop();
            TreeNodes operatorNode = new TreeNodes(opStack.pop());
            operatorNode.left = left;
            operatorNode.right = right;
            nodeStack.push(operatorNode);
        }

        return nodeStack.isEmpty() ? null : nodeStack.pop();
    }

    public static void postOrderTraversal(TreeNodes root) {
        if (root != null) {
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.print(root.val + " ");
        }
    }

    public static int evaluateExpression(TreeNodes root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val - '0';
        }

        int leftEval = evaluateExpression(root.left);
        int rightEval = evaluateExpression(root.right);

        switch (root.val) {
            case '+':
                return leftEval + rightEval;
            case '-':
                return leftEval - rightEval;
            case '*':
                return leftEval * rightEval;
            case '/':
                return leftEval / rightEval;
            default:
                return 0;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("        ?   ?  ");
        String infixExpression = scanner.nextLine();

        String[] tokens = infixExpression.split(" ");

        StringBuilder postfixExpression = new StringBuilder();
        for (String token : tokens) {
            postfixExpression.append(token);
            postfixExpression.append(" ");
        }

        System.out.println("  ?   ?  " + infixExpression);
        TreeNodes root = buildExpressionTree(infixExpression);
        System.out.print("  ?   ?  ");
        postOrderTraversal(root);
        System.out.println();

        int result = evaluateExpression(root);
        System.out.println("        " + result);

        scanner.close();
    }
}

有需要的自取~~