Java数据结构:栈(表达式求值)（java实现栈数据结构）

表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。表达式求值可以通过将中缀表达式转换为后缀表达式（逆波兰表达式）来实现，并使用栈对后缀表达式进行求值。

1. 将中缀表达式转换为后缀表达式（逆波兰表达式）。
2. 使用栈来存储操作符，遍历中缀表达式的每个元素。
3. 如果是数字，则直接输出。
4. 如果是操作符，则判断其与栈顶操作符的优先级，如果栈顶操作符优先级较高，则弹出栈顶操作符并输出，直到栈为空或者栈顶操作符优先级不高于当前操作符。
5. 如果是左括号，则入栈。
6. 如果是右括号，则弹出栈内所有操作符并输出，直到遇到左括号为止。
7. 使用栈对后缀表达式进行求值。
8. 遍历后缀表达式的每个元素。
9. 如果是数字，则入栈。
10. 如果是操作符，则从栈中弹出两个操作数进行计算，并将结果入栈。

下面以表达式4+2*3-10/5为例编写应用程序。

import java.util.Stack;

public class ExpressionEvaluator {
    public static void main(String[] args) {
        String expression = "4+2*3-10/5";
        System.out.println("Result: " + evaluateExpression(expression)); // 输出计算结果
    }

    public static int evaluateExpression(String expression) {
        String postfixExpression = infixToPostfix(expression); // 中缀转后缀
        return evaluatePostfix(postfixExpression); // 求值后缀表达式
    }

    public static String infixToPostfix(String expression) {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> operatorStack = new Stack<>();

        for (char ch : expression.toCharArray()) {
            if (Character.isDigit(ch)) {
                postfix.append(ch); // 如果是数字，直接输出到后缀表达式
            } else if (ch == '+' || ch == '-') {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-' || operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    postfix.append(operatorStack.pop()); // 弹出栈内优先级高于当前操作符的操作符
                }
                operatorStack.push(ch); // 当前操作符入栈
            } else if (ch == '*' || ch == '/') {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    postfix.append(operatorStack.pop()); // 弹出栈内优先级高于当前操作符的操作符
                }
                operatorStack.push(ch); // 当前操作符入栈
            } else if (ch == '(') {
                operatorStack.push(ch); // 左括号入栈
            } else if (ch == ')') {
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    postfix.append(operatorStack.pop()); // 弹出栈内所有操作符直到遇到左括号
                }
                operatorStack.pop(); // 弹出左括号
            }
        }

        while (!operatorStack.isEmpty()) {
            postfix.append(operatorStack.pop()); // 将栈内剩余操作符输出
        }

        return postfix.toString();
    }

    public static int evaluatePostfix(String postfixExpression) {
        Stack<Integer> operandStack = new Stack<>();

        for (char ch : postfixExpression.toCharArray()) {
            if (Character.isDigit(ch)) {
                operandStack.push(Character.getNumericValue(ch)); // 如果是数字，入栈
            } else {
                int operand2 = operandStack.pop();
                int operand1 = operandStack.pop();
                switch (ch) {
                    case '+':
                        operandStack.push(operand1 + operand2);
                        break;
                    case '-':
                        operandStack.push(operand1 - operand2);
                        break;
                    case '*':
                        operandStack.push(operand1 * operand2);
                        break;
                    case '/':
                        operandStack.push(operand1 / operand2);
                        break;
                }
            }
        }

        return operandStack.pop(); // 返回栈顶元素，即表达式的计算结果
    }
}

说明：

1. infixToPostfix 方法将中缀表达式转换为后缀表达式。
2. evaluatePostfix 方法对后缀表达式进行求值。