本文共 3222 字，大约阅读时间需要 10 分钟。
中缀表达式转换为逆波兰表达式的过程涉及几个关键步骤，包括初始化栈、扫描表达式、处理括号和运算符优先级。以下是详细的转换步骤：
初始化栈：创建两个栈，一个用于存储运算符（运算符栈s1），另一个用于存储中间结果（操作数栈s2）。
扫描表达式：从左到右遍历中缀表达式中的每个元素：
处理剩余运算符：扫描完表达式后，弹出运算符栈s1中的运算符并压入操作数栈s2。
逆波兰表达式：操作数栈s2中的元素按顺序即为逆波兰表达式。
以下是具体的代码实现：
package com.wang.stack;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class PolandNotation { public static void main(String[] args) { String expression = "1+((2+3)*4)-5"; List infixList = toInfixExpressionList(expression); System.out.println(infixList); List suffixList = parseSuffixExpressionList(infixList); System.out.println("后缀表达式的List结果为：" + suffixList); int result = calculate(suffixList); System.out.println("计算结果为：" + result); } public static List toInfixExpressionList(String s) { List ls = new ArrayList<>(); int i = 0; String str = ""; char c; while (i < s.length()) { if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) { ls.add(c + ""); i++; } else { str = ""; while (i < s.length() && (c = s.charAt(i)) >= 48 && c <= 57) { str += c; i++; } if (!str.isEmpty()) { ls.add(str); } } } return ls; } public static List parseSuffixExpressionList(List ls) { Stack s1 = new Stack<>(); List s2 = new ArrayList<>(); for (String item : ls) { if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { while (!s1.isEmpty() && !s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop(); } else { while (!s1.isEmpty() && getOperationPriority(s1.peek()) >= getOperationPriority(item)) { s2.add(s1.pop()); } s1.push(item); } } while (!s1.isEmpty()) { s2.add(s1.pop()); } return s2; } private static int getOperationPriority(String operation) { switch (operation) { case "+": case "-": return 1; case "*": case "/": return 2; default: return 0; } } public static int calculate(List ls) { Stack stack = new Stack<>(); for (String item : ls) { if (item.matches("\\d+")) { stack.push(item); } else { String num2 = stack.pop(); String num1 = stack.pop(); int res = 0; switch (item) { case "+": res = Integer.parseInt(num1) + Integer.parseInt(num2); break; case "-": res = Integer.parseInt(num1) - Integer.parseInt(num2); break; case "*": res = Integer.parseInt(num1) * Integer.parseInt(num2); break; case "/": res = Integer.parseInt(num1) / Integer.parseInt(num2); break; default: throw new RuntimeException("运算符有误"); } stack.push(res + ""); } } return Integer.parseInt(stack.pop()); } public static void main(String[] args) { // 请在此处添加您的测试代码 } // 其他辅助方法...} 代码解释：
该实现支持多位数和括号，确保正确处理运算符优先级，并能处理整数运算。可以扩展为支持浮点数运算和更多功能。
转载地址：http://vhdk.baihongyu.com/