/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function (tokens) {
// 这种算法的前提是 tokens是有效的，
// 当然这由算法来保证
const stack = [];
for (let index = 0; index < tokens.length; index++) {
const token = tokens[index];
// 对于运算数， 我们直接入栈
if (!Number.isNaN(Number(token))) {
stack.push(token);
} else {
// 遇到操作符，我们直接大胆运算，不用考虑算术优先级
// 然后将运算结果入栈即可
// 当然如果题目进一步扩展，允许使用单目等其他运算符，我们的算法需要做微小的调整
const a = Number(stack.pop());
const b = Number(stack.pop());
if (token === "*") {
stack.push(b * a);
} else if (token === "/") {
stack.push((b / a) >> 0);
} else if (token === "+") {
stack.push(b + a);
} else if (token === "-") {
stack.push(b - a);
}
}
}
return stack.pop();
};
Python Code:
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
if len(tokens) > 2:
stack = []
operations = ['+', '-', '*', '/']
for token in tokens:
if token in operations:
b = int(stack.pop())
a = int(stack.pop())
if '+' == token:
tmp = a + b
elif '-' == token:
tmp = a - b
elif '*' == token:
tmp = a * b
else:
tmp = int(a / b)
stack.append(tmp)
else:
stack.append(token)
return stack[0]
return int(tokens[-1])
Java Code:
class Solution {
public static int evalRPN(String[] tokens) {
int[] numStack = new int[tokens.length / 2 + 1];
int index = 0;
for (String s : tokens) {
if (s.equals("+")) {
numStack[index - 2] += numStack[--index];
} else if (s.equals("-")) {
numStack[index - 2] -= numStack[--index];
} else if (s.equals("*")) {
numStack[index - 2] *= numStack[--index];
} else if (s.equals("/")) {
numStack[index - 2] /= numStack[--index];
} else {
numStack[index++] = Integer.parseInt(s);
}
}
return numStack[0];
}
}
CPP Code:
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (string t : tokens) {
if (isdigit(t.back())) s.push(stoi(t));
else {
int n = s.top();
s.pop();
switch(t[0]) {
case '+': s.top() += n; break;
case '-': s.top() -= n; break;
case '*': s.top() *= n; break;
case '/': s.top() /= n; break;
}
}
}
return s.top();
}
};
