[抄题]:
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +
, -
, *
, /
. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
[暴力解法]:
时间分析:
空间分析:
[优化后]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
[思维问题]:
怕写:也没那么难,分为加减乘除来讨论下就可以了
[英文数据结构或算法,为什么不用别的数据结构或算法]:
逆波兰表达式,英文为 Reverse Polish notation,跟波兰表达式(Polish notation)相对应。平时我们习惯将表达式写成 (1 + 2) * (3 + 4),加减乘除等运算符写在中间,因此称呼为中缀表达式。而波兰表达式的写法为 (* (+ 1 2) (+ 3 4)),将运算符写在前面,因而也称为前缀表达式。逆波兰表达式的写法为 ((1 2 +) (3 4 +) *),将运算符写在后面,因而也称为后缀表达式。波兰表达式和逆波兰表达式有个好处,就算将圆括号去掉也不会引起歧义。上述的波兰表达式去掉圆括号,变为 * + 1 2 + 3 4。逆波兰表达式去掉圆括号,变成 1 2 + 3 4 + * 也是无歧义并可以计算的。事实上我们通常说的波兰表达式和逆波兰表达式就是去掉圆括号的。而中缀表达式,假如去掉圆括号,将 (1 + 2) * (3 + 4) 写成 1 + 2 * 3 + 4,就改变原来意思了。为什么叫波兰表达式和逆波兰表达式呢?是为了纪念波兰的数理科学家 Jan Łukasiewicz,其在著作中提到。我在1924年突然有了一个无需括号的表达方法,我在文章第一次使用了这种表示法。现实中,波兰表达式和逆波兰表达式,具体用于什么地方呢?波兰表达式(前缀表达式),实际是抽象语法树的表示方式,比如中缀 (1 + 2) * (3 + 4) 编译时转成的抽象语法树为 *
/ \
+ +
/ \ / \
1 2 3 4
这个操作符就是根节点,操作数为左右子节点。我们将这棵树用符号表达出来,可以写成 (* (+ 1 2) (+ 3 4))。这实际就是 Lisp 的 S-表达式。S-表达式可看成将整棵抽象语法树都写出来,每层节点都加上圆括号。至于逆波兰表示式,可用栈进行计算,天生适合于基于栈的语言。遇到数字就将数字压栈,遇到操作符,就将栈顶的两个元素取出计算,将计算结果再压入栈。比较典型的基于栈的语言为 Forth 和 PostScript。
[一句话思路]:
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
用stack,注意一下:先pop出来的是晚进去的。a-b a/b都当作b。
[一刷]:
字符串要用.equals函数,只有单个的字母才用等号
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[算法思想:迭代/递归/分治/贪心]:
[关键模板化代码]:
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
[是否头一次写此类driver funcion的代码] :
[潜台词] :
class Solution {
public int evalRPN(String[] tokens) {
//cc
if (tokens == null || tokens.length == 0) return 0; //ini: stack
Stack<Integer> stack = new Stack<>(); //for loop: 5 cases
for (String s : tokens) {
//string should use .equals function
if (s.equals("+")) {
stack.push(stack.pop() + stack.pop());
}else if (s.equals("-")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
}else if (s.equals("*")) {
stack.push(stack.pop() * stack.pop());
}else if (s.equals("/")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
}else {
stack.push(Integer.valueOf(s));
}
} return stack.pop();
}
}