150. 逆波兰表达式求值
LeetCode题目要求
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
示例
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
解题思路
首先逆波兰表达式实际就是后缀表达式，也就是数字在前，符号在后，即 2,1+,3,；而咱们通常的计算都是中缀表达式，即 a+b
这个表达式 "2","1","+","3","" 转换为 ((2 + 1) * 3) = 9
观察这个表达式，发现我们需要计算的是 2 与 1 的和，它是由 2 ，1 后面的 + 号决定的。之后 2 + 1 的结果 在与 3 相乘，是由 3 后面的符号决定的。
这时我们想一下用栈的操作是否可以
首先将数字入栈，这里是 2 、1
当遇到符号，这里是 + ，2、1 出栈，并通过 + 进行运算，运算后我们怎么办，这里可以考虑将结果 3 入栈
再向后遍历，3 入栈，
接着遇到符号 * ，3、3 出栈，通过 * 运算得到结果。
这里我们要做的是遇到符号就做出栈操作，且出栈两个元素；运算结果需要入栈，便于后面数字的运算操作
简单模拟一个过程
/**
入栈操作 2 1 入栈
1 栈顶
2 栈底
遇到符号 + 出栈操作，出栈两个 2 和 1，并通过 + 做运算
结果 1 + 2 = 3 将 3 入栈
3 栈底
遍历，发现数字 3 入栈
3 栈顶
3 栈底
遇到符号 * 出栈操作，出栈两个 3 和 3，并通过 * 做运算
结果 3 * 3 = 9 将 9 入栈
最终从栈中弹出结果
*/
上代码
class Solution {
public int evalRPN(String[] tokens) {
// "2","1","+","3","*"
String symbol = "+-*/";
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < tokens.length; i++) {
if (symbol.contains(tokens[i])) {
// 出栈 2 个元素
int a = stack.pop();
int b = stack.pop();
if ("+".equals(tokens[i])) {
stack.push(a+b);
} else if ("-".equals(tokens[i])) {
stack.push(b-a);
} else if ("*".equals(tokens[i])) {
stack.push(b*a);
} else if ("/".equals(tokens[i])) {
stack.push(b/a);
}
} else {
// 入栈
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
附：学习资料链接
标签：150,出栈,入栈,tokens,Day11,求值,stack,表达式,运算 From： https://www.cnblogs.com/blacksonny/p/17050637.html