代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
根据 逆波兰表示法,求该后缀表达式的计算结果。
有效的算符包括 +
、-
、*
、/
。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
示例 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)
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。