题目大意：
逆波兰表达式求值
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: ((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"] 输出: 6 解释: (4 + (13 / 5)) = 6
示例 3：
输入: ["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 = 2
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=150
解题思路分析：
关于逆波兰表达式的定义大家可以参考：
- 百度百科：逆波兰式
- wikipedia：Reverse Polish notation
关于本题，这是一道典型的Stack题目，我们从数组首位向后逐一循环，如果当前字符是数字，我们将它push进栈，如果是运算符号，我们就从Stack中取出2个元素a和b，然后用当前符号对a和b进行运算，运算结果再push进栈。这里需要注意一点，从Stack中pop出2个元素a和b时，Stack基于先进后出的原则，先pop出的a实际上是在后pop出的b的后面，所以，计算时应该用b(+-*/)a，不要写反。
最后循环完所有字符串，Stack中应该剩下唯一一个数值，该数值即是返回结果。
实现代码：
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
// 循环每一个字符串
for(String s : tokens){
// 如果当前字符串是运算符号
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
// 从Stack取出两个数字
int a=stack.pop();
int b=stack.pop();
// 根据符号对两个数字进行运算，并将运算结果存入Stack
if(s.equals("+")) stack.push(b+a);
if(s.equals("-")) stack.push(b-a);
if(s.equals("*")) stack.push(b*a);
if(s.equals("/")) stack.push(b/a);
}else{
// 如果当前字符串是数字，存入Stack
stack.push(Integer.valueOf(s));
}
}
// Stack中最后剩下的数字是返回结果。
if(stack.size()>0) return stack.pop();
return 0;
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 74.91% of Java online submissions for Evaluate Reverse Polish Notation.
Memory Usage: 46.7 MB, less than 6.00% of Java online submissions for Evaluate Reverse Polish Notation.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-150-evaluate-reverse-polish-notation-解题思路分析/