一、表达式概念详解
1. 前缀表达式（波兰表达式）
· 定义：运算符位于操作数之前，如 + 1 2 等价于 1 + 2。
· 特点：无需括号，优先级由运算符位置决定，适合计算机解析。
2. 中缀表达式
· 定义：运算符在操作数中间，如 1 + (2 * 3)，符合人类阅读习惯，但需括号控制优先级。
3. 后缀表达式（逆波兰表达式）
· 定义：运算符位于操作数之后，如 1 2 3 * + 等价于 1 + (2 * 3)。
· 特点：计算顺序明确，无需括号，适合栈结构处理。
二、中缀转前缀/后缀表达式的方法与Java实现
将中缀表达式字符串转换为列表及一些方法准备
/**
? ? * 将中缀表达式字符串转换为列表
? ? * 此方法遍历输入的中缀表达式字符串，将其中的数字和运算符提取出来，分别以字符串形式存入列表中
? ? * 对于连续的数字字符，将它们合并成一个完整的数字字符串再添加到列表中
? ? *
? ? * @param input 中缀表达式字符串，例如 "3+5*(6-2)"
? ? * @return 包含中缀表达式各个部分的列表，例如 ["3", "+", "5", "*", "(", "6", "-", "2", ")"]
? ? */
? ?public static List toInfixExpressionList(String input) {
? ? ? ?List list = new ArrayList<>();
? ? ? ?int index = 0;
? ? ? ?String str = "";
? ? ? ?char c;
? ? ? ?do {
? ? ? ? ? ?if ((c = input.charAt(index)) == ' ') {
? ? ? ? ? ? ? ?index++;
? ? ? ? ? ? ? ?continue;
? ? ? ? ? }
? ? ? ? ? ?// 遇到非数字字符时，直接将其添加到列表中
? ? ? ? ? ?if (((c = input.charAt(index)) < '0' || (c = input.charAt(index)) > '9') && (c = input.charAt(index)) != '.') {
? ? ? ? ? ? ? ?list.add(String.valueOf(c));
? ? ? ? ? ? ? ?index++;
? ? ? ? ? } else {
? ? ? ? ? ? ? ?// 遇到数字字符时，将其连续的数字字符组合成一个数字字符串
? ? ? ? ? ? ? ?while (index < input.length() && ((index < input.length() && (c = input.charAt(index)) >= '0' && (c = input.charAt(index)) <= '9') || (c = input.charAt(index)) == '.')) {
? ? ? ? ? ? ? ? ? ?str += String.valueOf(c);
? ? ? ? ? ? ? ? ? ?index++;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?list.add(str);
? ? ? ? ? }
? ? ? ? ? ?// 重置str，为下一个数字字符串做准备
? ? ? ? ? ?str = "";
? ? ? } while (index < input.length());
? ? ? ?return list;
? }
?
/**
? ? * 计算给定运算符的优先级。
? ? *
? ? * 该函数用于确定运算符在表达式中的优先级。支持的运算符包括加、减、乘、除。
? ? *
? ? * @param s 表示运算符的字符串，支持的运算符为 "+", "-", "*", "/"。
? ? * @return 返回运算符的优先级值。加和减的优先级为0，乘和除的优先级为1，其他情况返回-1表示不支持。
? ? */
? ?public static int priority(String s) {
? ? ? ?// 判断运算符是否为加或减，返回对应的优先级
? ? ? ?if (s.equals("+") || s.equals("-")) {
? ? ? ? ? ?return 0;
? ? ? }
? ? ? ?// 判断运算符是否为乘或除，返回对应的优先级
? ? ? ?else if (s.equals("*") || s.equals("/")) {
? ? ? ? ? ?return 1;
? ? ? }
? ? ? ?// 对于不支持的运算符，返回-1
? ? ? ?else {
? ? ? ? ? ?return -1;
? ? ? }
? } 转换核心步骤
1. 中缀转后缀
步骤：
（1）初始化运算符栈 s1 和结果栈 s2。
（2）从左到右扫描中缀表达式：
- 数字直接入 s2。
- 左括号 "(" 入 s1；右括号 “)” 则弹出 s1 压入 s2，直到遇到左括号。
- 运算符比较优先级：弹出 s1 中优先级 ≥ 当前运算符的元素 压入 s2，再压入当前运算符到s1。
（3）将 s1 剩余元素弹出到 s2，逆序输出即为后缀表达式。
Java代码示例：
turn 后缀表达式列表
? ? */
? ?public static List parseSuffixExpressionList(List list) {
? ? ? ?// 运算符/**
? ? * 将中缀表达式转换为后缀表达式
? ? *
? ? * @param list 中缀表达式列表，包含数字和运算符
? ? * @re栈，用于暂存运算符
? ? ? ?Stack s1 = new Stack<>();
? ? ? ?// 输出队列，用于存放最终的后缀表达式
? ? ? ?List s2 = new ArrayList<>();
?
? ? ? ?// 遍历中缀表达式列表
? ? ? ?for (String item : list) {
? ? ? ? ? ?// 如果是数字，则直接加入输出队列
? ? ? ? ? ?if (item.matches("\\d+(\\.\\d*)?")) {
? ? ? ? ? ? ? ?s2.add(item);
? ? ? ? ? ?// 如果是左括号，则压入栈s1
? ? ? ? ? } else if (item.equals("(")) {
? ? ? ? ? ? ? ?s1.push(item);
? ? ? ? ? ?// 如果是右括号，则将栈s1中的运算符弹出到输出队列，直到遇到左括号
? ? ? ? ? } else if(item.equals(")")) {
? ? ? ? ? ? ? ?while (!s1.peek().equals("(")) {
? ? ? ? ? ? ? ? ? ?s2.add(s1.pop());
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?// 弹出左括号，不放入输出队列
? ? ? ? ? ? ? ?s1.pop();
? ? ? ? ? ?// 如果是运算符，则根据运算符的优先级进行处理
? ? ? ? ? } else {
? ? ? ? ? ? ? ?// 当栈不为空且当前运算符的优先级小于等于栈顶运算符的优先级时，将栈顶运算符弹出到输出队列
? ? ? ? ? ? ? ?while (!s1.isEmpty() && priority(item) <= priority(s1.peek())) {
? ? ? ? ? ? ? ? ? ?s2.add(s1.pop());
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?// 将当前运算符压入栈s1
? ? ? ? ? ? ? ?s1.push(item);
? ? ? ? ? }
? ? ? }
? ? ? ?// 将栈中剩余的运算符弹出到输出队列
? ? ? ?while (!s1.isEmpty()) {
? ? ? ? ? ?s2.add(s1.pop());
? ? ? }
? ? ? ?// 返回后缀表达式列表
? ? ? ?return s2;
? } 2. 中缀转前缀
步骤：
从右到左扫描中缀表达式，步骤类似转后缀，但需反转输入和输出顺序。
代码关键点：
/**
? ? * 解析前缀表达式列表
? ? * 该方法将一个由中缀表达式组成的字符串列表转换为前缀表达式列表
? ? * 前缀表达式（波兰表示法）是一种将运算符置于操作数之前的表达式表示法
? ? *
? ? * @param list 一个包含中缀表达式的字符串列表
? ? * @return 一个包含前缀表达式的字符串列表
? ? */
? ?public static List parsePrefixExpressionList(List list) {
? ? ? ?// 存储最终的前缀表达式结果
? ? ? ?List prefixList = new ArrayList<>();
? ? ? ?// s1用于暂存运算符
? ? ? ?Stack s1 = new Stack<>();
? ? ? ?// s2用于构建前缀表达式
? ? ? ?Stack s2 = new Stack<>();
? ?
? ? ? ?// 逆序遍历输入列表，因为前缀表达式是从右向左处理的
? ? ? ?for (int i = list.size() - 1; i >= 0; i--) {
? ? ? ? ? ?String item = list.get(i);
? ? ? ? ? ?// 如果是数字（包括小数），直接压入s2栈
? ? ? ? ? ?if (item.matches("\\d+(\\.\\d*)?")) {
? ? ? ? ? ? ? ?s2.push(item);
? ? ? ? ? ?// 如果是右括号，压入s1栈
? ? ? ? ? } else if (item.equals(")")) {
? ? ? ? ? ? ? ?s1.push(item);
? ? ? ? ? ?// 如果是左括号，将s1栈中的运算符弹出并压入s2栈，直到遇到右括号
? ? ? ? ? } else if(item.equals("(")) {
? ? ? ? ? ? ? ?while (!s1.peek().equals(")")) {
? ? ? ? ? ? ? ? ? ?s2.push(s1.pop());
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?// 弹出右括号，不放入s2栈
? ? ? ? ? ? ? ?s1.pop();
? ? ? ? ? ?// 如果是运算符，根据运算符的优先级进行处理
? ? ? ? ? } else {
? ? ? ? ? ? ? ?// 如果当前运算符的优先级小于s1栈顶的运算符，将s1栈中的运算符弹出并压入s2栈
? ? ? ? ? ? ? ?while (!s1.isEmpty() && priority(item) < priority(s1.peek())) {
? ? ? ? ? ? ? ? ? ?s2.push(s1.pop());
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?// 将当前运算符压入s1栈
? ? ? ? ? ? ? ?s1.push(item);
? ? ? ? ? }
? ? ? }
? ? ? ?// 将s1栈中剩余的运算符全部弹出并压入s2栈
? ? ? ?while (!s1.isEmpty()) {
? ? ? ? ? ?s2.push(s1.pop());
? ? ? }
? ? ? ?// 将s2栈中的所有元素（即前缀表达式）转移到prefixList中
? ? ? ?while (!s2.isEmpty()) {
? ? ? ? ? ?prefixList.add(s2.pop());
? ? ? }
? ? ? ?// 返回前缀表达式列表
? ? ? ?return prefixList;
? } 三、前缀/后缀表达式求值方法与Java实现
1. 前缀表达式求值
步骤：
（1）从右到左扫描表达式。
（2）遇到操作数入栈；遇到运算符则弹出栈顶两个元素运算，结果入栈。
Java代码示例：
/**
? ? * 计算前缀表达式的结果
? ? * 前缀表达式（波兰表示法）是一种将运算符置于操作数之前的表达式表示方法
? ? * 本方法通过栈结构解析前缀表达式，执行相应的算术运算，并返回计算结果
? ? *
? ? * @param list 包含前缀表达式的字符串列表，列表中的每个元素代表一个操作数或运算符
? ? * @return 返回前缀表达式的计算结果，以字符串形式输出
? ? */
? ?public static String calculatePrefix(List list) {
? ? ? ?// 创建一个栈，用于存储操作数
? ? ? ?Stack numStack = new Stack<>();
? ? ? ?// 初始化两个操作数
? ? ? ?double num1 = 0;
? ? ? ?double num2 = 0;
? ? ? ?// 从后向前遍历列表，因为前缀表达式是从右向左计算的
? ? ? ?for (int i = list.size() - 1; i >= 0; i--) {
? ? ? ? ? ?// 获取当前遍历到的字符串
? ? ? ? ? ?String s = list.get(i);
? ? ? ? ? ?// 如果是数字，则入栈
? ? ? ? ? ?if (s.matches("\\d+(\\.\\d*)?")) {
? ? ? ? ? ? ? ?numStack.push(s);
? ? ? ? ? } else {
? ? ? ? ? ? ? ?// 如果是运算符，则弹出栈顶的两个数字作为操作数
? ? ? ? ? ? ? ?num1 = Double.parseDouble(numStack.pop());
? ? ? ? ? ? ? ?num2 = Double.parseDouble(numStack.pop());
? ? ? ? ? ? ? ?// 根据运算符执行相应的算术运算，并将结果入栈
? ? ? ? ? ? ? ?switch (s) {
? ? ? ? ? ? ? ? ? ?case "+":
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 + num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? ?case "-":
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 - num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? ?case "*":
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 * num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? ?case "/":
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 / num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
? ? ? ?// 最后栈中剩余的元素即为计算结果
? ? ? ?return numStack.pop();
? } 2. 后缀表达式求值
步骤：
1. 从左到右扫描表达式。
2. 操作数入栈；运算符弹出栈顶两个元素运算（注意顺序：次顶元素 减 栈顶元素）。
Java代码示例：
/**
? ? * 计算给定列表中的逆波兰表达式
? ? * 逆波兰表达式是一种将运算符置于操作数之后的表示方式，例如 (3 + 4) * 5 的逆波兰表达式为 "3 4 + 5 *"
? ? * 该方法使用栈来处理逆波兰表达式的计算，遇到数字则入栈，遇到运算符则弹出栈顶两个数字进行计算，并将结果入栈
? ? *
? ? * @param list 包含逆波兰表达式的列表，列表中的元素为数字或运算符
? ? * @return 计算结果的字符串表示
? ? */
? ?public static String calculateSuffix(List list) {
? ? ? ?// 创建一个栈，用于存放数字
? ? ? ?Stack numStack = new Stack<>();
? ? ? ?// 定义两个变量，用于存储运算符前后的两个数字
? ? ? ?double num1 = 0;
? ? ? ?double num2 = 0;
? ? ? ?// 遍历列表中的每个元素
? ? ? ?for (int i = 0; i < list.size(); i++) {
? ? ? ? ? ?String s = list.get(i);
? ? ? ? ? ?// 判断当前元素是否为运算符
? ? ? ? ? ?if (s.charAt(0) > '9' || s.charAt(0) < '0') {
? ? ? ? ? ? ? ?// 从栈中弹出两个数字，准备进行运算
? ? ? ? ? ? ? ?num2 = Double.parseDouble(numStack.pop());
? ? ? ? ? ? ? ?num1 = Double.parseDouble(numStack.pop());
? ? ? ? ? ? ? ?// 根据运算符进行相应的运算
? ? ? ? ? ? ? ?switch (s) {
? ? ? ? ? ? ? ? ? ?case "+":
? ? ? ? ? ? ? ? ? ? ? ?// 加法运算，并将结果入栈
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 + num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? ?case "-":
? ? ? ? ? ? ? ? ? ? ? ?// 减法运算，并将结果入栈
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 - num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? ?case "*":
? ? ? ? ? ? ? ? ? ? ? ?// 乘法运算，并将结果入栈
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 * num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? ?case "/":
? ? ? ? ? ? ? ? ? ? ? ?// 除法运算，并将结果入栈
? ? ? ? ? ? ? ? ? ? ? ?numStack.push(String.valueOf(num1 / num2));
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? } else {
? ? ? ? ? ? ? ?// 如果当前元素为数字，则将其入栈
? ? ? ? ? ? ? ?numStack.push(s);
? ? ? ? ? }
? ? ? }
? ? ? ?// 返回栈顶元素，即最终的计算结果
? ? ? ?return numStack.pop();
? } 四、应用场景
1. 编译器设计：语法树生成时常用后缀表达式简化中间代码生成。
2. 计算器程序：如逆波兰式直接支持高效运算（如早期HP计算器）。
3. 表达式解析优化：前缀/后缀形式避免优先级歧义，提升计算效率。
五、总结对比
表达式类型 | 可读性 | 计算效率 | 括号需求 | 适用场景 |
中缀表达式 | 高 | 低 | 需要 | 人类输入、显示 |
前缀表达式 | 低 | 高 | 不需要 | 编译器优化、函数式语言 |
后缀表达式 | 低 | 高 | 不需要 | 栈式计算、自动化解析 |