第 4 关 | 站不住的栈：3.黄金挑战——表达式问题-灵析社区
时光小少年1. 计算器问题
计算器也是非常常见的问题，我们看一个中等问题。
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意： 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2" 输出：7
示例 2：
输入：s = " 3/2 " 输出：1
示例 3：
输入：s = " 3+5 / 2 " 输出：5
解决运算问题，最好的工具就是栈，由于乘除优先于加减运算，所以可以考虑先进行所有的乘除运算，并且将这些乘除运算之后的整数值放回到原表达式的相应位置，然后整个表达式的值就等于一系列加减后的值。
在此基础上，我们可以使用一个栈，保存这些（进行乘除运算后的值。对于加减后的数字，我们可以先采取把他压入栈中的方式，然后在最后进行加减；对于乘除的数字，可以直接和栈顶元素计算，并且替换栈顶元素后为计算后的结果。
总体思路如下：
遍历整个数组，然后用变量 preSign 将这些数字都记录下来，对于第一个数字，与其之前的运算符都看做加好，每次加到数字末尾的时候，就使用 preSign 来决定计算方式；
- 加号： 数字直接压入栈
- 减号：将相反的数字压入栈
- 乘号：将栈顶元素出栈，与数字相乘之后再入栈
- 除号：将栈顶元素出栈，除完之后重新入栈
然后遍历到数字尾部或者读取到一个运算符之后，更新符号。
遍历完字符串之后，将栈中元素累加，就是该字符表达式的值。
class Solution {
public int calculate(String s) {
if(s == null || s.length() == 0) return 0;
Deque<Integer> stack = new ArrayDeque<Integer>();
char preSign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
}
if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
default:
stack.push(stack.pop() / num);
}
preSign = s.charAt(i);
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
}
2. 逆波兰表达式
表达式是编译原理，自然语言处理、文本分析等领域非常重要的问题，这里我们看一个相对中等的问题，逆波兰表达式。
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为 '+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零
- 算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
本题看起来很复杂，但是其实很简单，首先表达式就是指可以计算出结果的式子，根据不同的计法，可以分为前中后缀三种，其区别在于运算符相对于操作数的位置，前缀表达式的运算符位于操作数之前，中缀和后缀同理，如下图，这就对应了树的前中后三种遍历方式。
对应的三种表达式如下：
中缀： 1 + （2 + 3） x 4 -5
前缀：-+ 1 x + 2 3 4 5
后缀：1 2 3 + 4 x + 5 -
从上面来看，中缀表达式是我们经常遇见的，然后前缀被称为波兰式，后缀则被称为逆波兰式子
用栈来解释就是遇到数组进栈，遇到运算符就取出栈中最上面的两个元素进行计算，最后运算结果进栈即可。实现代码如下:
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int n = tokens.length;
for(int i = 0;i < n;i++){
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
}else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}
3. 通关文牒
阅读量：986
点赞量：0
收藏量:0