comments | edit_url |
---|---|
true |
根据 逆波兰表示法,求该后缀表达式的计算结果。
有效的算符包括 +
、-
、*
、/
。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 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 <= tokens.length <= 104
tokens[i]
要么是一个算符("+"
、"-"
、"*"
或"/"
),要么是一个在范围[-200, 200]
内的整数
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式,如
( 1 + 2 ) * ( 3 + 4 )
。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )
。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成
1 2 + 3 4 + *
也可以依据次序计算出正确结果。 - 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中。
注意:本题与主站 150 题相同: https://leetcode.cn/problems/evaluate-reverse-polish-notation/
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
nums = []
for t in tokens:
if len(t) > 1 or t.isdigit():
nums.append(int(t))
else:
if t == "+":
nums[-2] += nums[-1]
elif t == "-":
nums[-2] -= nums[-1]
elif t == "*":
nums[-2] *= nums[-1]
else:
nums[-2] = int(nums[-2] / nums[-1])
nums.pop()
return nums[0]
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stk = new ArrayDeque<>();
for (String t : tokens) {
if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
stk.push(Integer.parseInt(t));
} else {
int y = stk.pop();
int x = stk.pop();
switch (t) {
case "+":
stk.push(x + y);
break;
case "-":
stk.push(x - y);
break;
case "*":
stk.push(x * y);
break;
default:
stk.push(x / y);
break;
}
}
}
return stk.pop();
}
}
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (auto& t : tokens) {
if (t.size() > 1 || isdigit(t[0])) {
stk.push(stoi(t));
} else {
int y = stk.top();
stk.pop();
int x = stk.top();
stk.pop();
if (t[0] == '+')
stk.push(x + y);
else if (t[0] == '-')
stk.push(x - y);
else if (t[0] == '*')
stk.push(x * y);
else
stk.push(x / y);
}
}
return stk.top();
}
};
func evalRPN(tokens []string) int {
// https://github.com/emirpasic/gods#arraystack
stk := arraystack.New()
for _, token := range tokens {
if len(token) > 1 || token[0] >= '0' && token[0] <= '9' {
num, _ := strconv.Atoi(token)
stk.Push(num)
} else {
y := popInt(stk)
x := popInt(stk)
switch token {
case "+":
stk.Push(x + y)
case "-":
stk.Push(x - y)
case "*":
stk.Push(x * y)
default:
stk.Push(x / y)
}
}
}
return popInt(stk)
}
func popInt(stack *arraystack.Stack) int {
v, _ := stack.Pop()
return v.(int)
}
class Solution {
func evalRPN(_ tokens: [String]) -> Int {
var stk = [Int]()
for token in tokens {
if let num = Int(token) {
stk.append(num)
} else {
let y = stk.removeLast()
let x = stk.removeLast()
switch token {
case "+":
stk.append(x + y)
case "-":
stk.append(x - y)
case "*":
stk.append(x * y)
default:
stk.append(x / y)
}
}
}
return stk.removeLast()
}
}