题目
描述
输入一个表达式(用字符串表示),求这个表达式的值。
保证字符串中的有效字符包括[‘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; } } }