1. question: 逆波兰表达式求值(中等)
根据 逆波兰表示法,求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
示例 1:
1 2 3
| 输入:tokens = ["2","1","+","3","*"] 输出:9 解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
|
示例 2:
1 2 3
| 输入:tokens = ["4","13","5","/","+"] 输出:6 解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
|
示例 3:
1 2 3 4 5 6 7 8 9 10
| 输入: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
| 1 <= tokens.length <= 104 tokens[i] 是一个算符("+"、"-"、"*" 或 "/"),或是在范围 [-200, 200] 内的一个整数
|
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
2. answers
这道题也是比较简单,只需要弄明白逆波兰表达式是什么就可以了。简单的说就是,操作符在两个操作数的后面,并且整体上已经是满足了优先级的顺序。
所以可以采用栈数据结构来做,每次遇到操作符,就将栈顶的两个元素弹出来(先弹出来的元素是第二个操作符,后弹出来的元素是第一个操作符),根据操作符计算结果,并将结果入栈。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| public class Solution_0029 {
public static int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>(); Integer first, second;
for(String s: tokens) {
if(s.equals("+")) {
second = stack.pop(); first = stack.pop();
stack.push(first + second);
} else if(s.equals("-")) {
second = stack.pop(); first = stack.pop();
stack.push(first - second);
} else if(s.equals("*")) {
second = stack.pop(); first = stack.pop();
stack.push(first * second);
} else if(s.equals("/")) {
second = stack.pop(); first = stack.pop();
stack.push(first / second);
} else { stack.push(Integer.parseInt(s)); } }
return stack.pop(); }
public static void main(String[] args) {
String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}; System.out.println(evalRPN(tokens)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。