题目
描述
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
数据范围：表达式计算结果和过程中满足 |val| \le 1000 \∣val∣≤1000 ，字符串长度满足 1 \le n \le 1000 \1≤n≤1000
输入描述：
输入一个算术表达式
输出描述：
得到计算结果
思路把中缀表达式转为后缀表达式
但现在的难点在于：如何把中缀表达式转成后缀表达式？
中缀表达式转后缀表达式步骤：
- 初始化两个栈：
- 运算符栈：s1
- 中间结果栈：s2
- 从左到右扫描中缀表达式
- 遇到操作数时，将其压入 s2
- 遇到运算符时比较 它 与 s1 栈顶运算符的优先级：再重复第 4.1 步骤，与新的栈顶运算符比较（因为 4.3 将 s1 栈顶运算符弹出了）这里重复的步骤在实现的时候有点难以理解，下面进行解说：
- 如果 s1 为空，或则栈顶运算符号为 ( ，则将其压入符号栈 s1
- 如果：优先级比栈顶运算符 高，也将其压入符号栈 s1
- 如果：优先级比栈顶运算符 低 或 相等，将 s1 栈顶的运算符 弹出，并压入到 s2 中
- 如果 s1 栈顶符号 优先级比 当前符号 高或则等于，那么就将其 弹出，压入 s2 中（循环做，是只要 s1 不为空）如果栈顶符号为 (，优先级是 -1，就不会弹出，就跳出循环了
- 跳出循环后，则将当前符号压入 s1
- 遇到括号时：
- 如果是左括号 ( ：则直接压入 s1
- 如果是右括号 )：则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 为止，此时将这一对括号 丢弃
- 重复步骤 2 到 5，直到表达式最右端
- 将 s1 中的运算符依次弹出并压入 s2
- 依次弹出 s2 中的元素并输出，结果的 逆序 即为：中缀表达式转后缀表达式
下面进行举例说明：
将中缀表达式：1+((2+3)*4)-5 转换为后
| 扫描到的元素 | s2 （栈底 -> 栈顶） | s1（栈底 -> 栈顶） | 说明 |
| 1 | 1 |
空 | 遇到操作数，将其压入 s2 |
+ |
1 |
+ |
s1 栈为空，将其压入 s1 |
( |
1 |
+ ( |
是左括号，压入 s1 |
( |
1 |
+ ( ( |
是左括号，压入 s1 |
| 2 | 1 2 |
+ ( ( |
遇到操作数，将其压入 s2 |
+ |
1 2 |
+ ( ( + |
遇到操作符：与 s1 栈顶运算符比较，为 (，将其压入 s1 |
| 3 | 1 2 3 |
+ ( ( + |
遇到操作数，将其压入 s2 |
) |
1 2 3 + |
+ ( |
遇到右括号：弹出 s1 中的 + 压入 s2 中，这里去掉这一对小括号 |
* |
1 2 3 + |
+ ( * |
遇到操作符：与 s1 栈顶比较，为 (，将其压入 s1 栈 |
| 4 | 1 2 3 + 4 |
+ ( * |
遇到操作数：将其压入 s2 |
) |
1 2 3 + 4 * |
+ |
遇到右括号：弹出 s 1 中的 * 压入 s2 中，这里去掉这一队小括号 |
- |
1 2 3 + 4 * + |
- |
遇到操作符：与 s1 栈顶比较，优先级一致，将 s1 中的 + 弹出，并压入 s2 中 |
| 5 | 1 2 3 + 4 * + 5 |
- |
遇到操作数：将其压入 s2 |
1 2 3 + 4 * + 5 - |
空 | 解析完毕，将 s1 中的符号弹出并压入 s2 中 |
由于 s2 是一个栈，弹出是从栈顶弹出，因此逆序后结果就是 1 2 3 + 4 * + 5 -
一个疑问
老师，你怎么知道这个中缀表达式转后缀表达式的思路是这样的？
在学习和使用上有两个层次：
- 应用层次：别人发明出来的东西，你学习、理解它，并灵活运用它
- 自创：你自己发明一个东西出来，并使用它
那么这里的中缀转后缀表达式的思路步骤，则属于第一个层次，相关的计算机专家之类的，发明出来了。我们要理解它并灵活运用它。等你能力达到一定层度时，有可能发明出来一个算法。
再比如：绝世武功 -> 降龙十八掌，别人已经创造出来了，你不去学习理解它，如何加以改进并自创？如果没有人教你，你怎么能学会降龙十八掌？
import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); List<String> infix = expressionToList(s); // List List<String> suffix = infixToSuffix(infix); // 中缀转后缀 Stack<String> stk = new Stack<>(); // 存储中间结果 // 逆波兰计算器 for (int i = 0; i < suffix.size(); i++) { String tmp = suffix.get(i); if (isOper(tmp)) { String num2 = stk.pop(); String num1 = stk.pop(); String reuslt = cal(num1, tmp, num2); stk.push(reuslt); } else { // 数字直接入栈 stk.push(tmp); } } System.out.println(stk.pop()); } public static String cal(String num1, String oper, String num2) { Long result = 0l; Long a = Long.parseLong(num1); Long b = Long.parseLong(num2); switch (oper) { case "+": result = a + b; break; case "-": result = a - b; break; case "*": result = a * b; break; case "/": result = a / b; break; } return String.valueOf(result); } public static List<String> infixToSuffix(List<String> infix) { List<String> suffix = new ArrayList<>(); Stack<String> stack1 = new Stack<>(); // 只用于保存操作符 Stack<String> stack2 = new Stack<>(); // 用于保存中间结果 for (int i = 0; i < infix.size(); i++) { String tmp = infix.get(i); if (!isOper(tmp)) { stack2.push(tmp); } else if (stack1.isEmpty() || "(".equals(tmp) || "[".equals(tmp) || "{".equals(tmp)) { // 如果 stack1 是空的，或者 tmp 是左括号，直接入栈 stack1.push(tmp); } else if (")".equals(tmp) || "]".equals(tmp) || "}".equals(tmp)) { // tmp 是右括号，则把 stack1 遇到左括号之前，全部倒入 stack2 while (!("(".equals(stack1.peek()) || "[".equals(stack1.peek()) || "{".equals(stack1.peek()))) { stack2.push(stack1.pop()); } stack1.pop(); // 丢掉左括号 } // 剩下的则是运算符 else { // 如果 s1 为空，或则栈顶运算符为 （，则压入符号栈 s1 // 如果优先级比栈顶运算符 高，则压入符号栈 s1,否则，否则将 s1 栈顶的运算符弹出，压入 s2 中 // 上面两句话，转换成下面的描述 // 上面如果 s1 栈顶符号优先级比 当前符号高，则弹出加入到 s2 中。 // 因为：如果栈顶符号是 （ 返回优先级为 -1.比当前符号低，则不会走该方法 while (!stack1.isEmpty() && priority(stack1.peek()) >= priority(tmp)) { stack2.push(stack1.pop()); } stack1.push(tmp); } } // stack1 剩余操作符全部倒入 stack2 while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } // stack2 的逆序才是结果，所以要再倒一次 while (!stack2.isEmpty()) { stack1.push(stack2.pop()); } // 现在 stack1 的元素倒出来的顺序就是后缀表达式 while (!stack1.isEmpty()) { suffix.add(stack1.pop()); } return suffix; } public static List<String> expressionToList(String expression) { List<String> list = new ArrayList<>(); int len = expression.length(); String keepNum = ""; for (int i = 0; i < len; i++) { char c = expression.charAt(i); if (Character.isDigit(c)) { if (i != len - 1 && Character.isDigit(expression.charAt(i + 1))) { // 如果下一个字符也是数字 keepNum += c; } else { // 当前是最后一个字符，或者下一个开始不是数字 keepNum += c; list.add(keepNum); keepNum = ""; } } else if (c == '-') { if (i == 0 || expression.charAt(i - 1) == '(' || expression.charAt(i - 1) == '[' || expression.charAt(i - 1) == '{') { keepNum += c; } else { list.add(c + ""); } } else { list.add(c + ""); } } return list; } public static boolean isOper(String str) { return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str) || "(".equals(str) || ")".equals(str) || "[".equals(str) || "]".equals(str) || "{".equals(str) || "}".equals(str); } public static int priority(String oper) { if ("+".equals(oper) || "-".equals(oper)) { return 0; } else if ("*".equals(oper) || "/".equals(oper)) { return 1; } else { return -1; } } }
