龙空技术网

Java数据结构:栈(表达式求值)

奋斗中的独城人 46

前言:

此时兄弟们对“利用栈计算后缀表达式”大致比较讲究,大家都想要了解一些“利用栈计算后缀表达式”的相关内容。那么小编在网络上收集了一些关于“利用栈计算后缀表达式””的相关内容,希望小伙伴们能喜欢,各位老铁们快快来学习一下吧!

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

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

下面以表达式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(); // 返回栈顶元素,即表达式的计算结果    }}

说明:

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

标签: #利用栈计算后缀表达式