前言:
此时兄弟们对“利用栈计算后缀表达式”大致比较讲究,大家都想要了解一些“利用栈计算后缀表达式”的相关内容。那么小编在网络上收集了一些关于“利用栈计算后缀表达式””的相关内容,希望小伙伴们能喜欢,各位老铁们快快来学习一下吧!表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。表达式求值可以通过将中缀表达式转换为后缀表达式(逆波兰表达式)来实现,并使用栈对后缀表达式进行求值。
将中缀表达式转换为后缀表达式(逆波兰表达式)。使用栈来存储操作符,遍历中缀表达式的每个元素。如果是数字,则直接输出。如果是操作符,则判断其与栈顶操作符的优先级,如果栈顶操作符优先级较高,则弹出栈顶操作符并输出,直到栈为空或者栈顶操作符优先级不高于当前操作符。如果是左括号,则入栈。如果是右括号,则弹出栈内所有操作符并输出,直到遇到左括号为止。使用栈对后缀表达式进行求值。遍历后缀表达式的每个元素。如果是数字,则入栈。如果是操作符,则从栈中弹出两个操作数进行计算,并将结果入栈。
下面以表达式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 方法对后缀表达式进行求值。
标签: #利用栈计算后缀表达式