150. Evaluate Reverse Polish Notation
你被給予一個字符串數組 tokens，該數組表示一個逆波蘭表示法的算術表達式。
計算該表達式。返回表示該表達式值的整數。
注意：
有效的操作符有 '+', '-', '*', 和 '/'。 每個操作數可以是整數或另一個表達式。 兩個整數之間的除法總是向零截斷。 不會有任何除以零的情況。 輸入表示一個有效的逆波蘭表示法算術表達式。 答案和所有中間計算都可以表示為32位整數。
範例：
輸入: tokens = ["2","1","+","3","*"] 輸出: 9 說明: ((2 + 1) * 3) = 9
Python
from typing import List
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token in "+-*/":
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
# int() is used to truncate towards zero
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
17.20MB, 80ms
C++
#include <vector>
#include <string>
#include <stack>
#include <cstdlib> // For std::stoi
using namespace std;
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stack;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = stack.top(); stack.pop();
int a = stack.top(); stack.pop();
if (token == "+") stack.push(a + b);
if (token == "-") stack.push(a - b);
if (token == "*") stack.push(a * b);
if (token == "/") stack.push(a / b);
} else {
stack.push(stoi(token));
}
}
return stack.top();
}
};
15.57MB, 12ms
Javascript
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
const stack = [];
for (const token of tokens) {
if (token === '+' || token === '-' || token === '*' || token === '/') {
const b = stack.pop();
const a = stack.pop();
let result;
if (token === '+') {
result = a + b;
} else if (token === '-') {
result = a - b;
} else if (token === '*') {
result = a * b;
} else if (token === '/') {
result = Math.trunc(a / b); // Math.trunc() is used to truncate toward zero
}
stack.push(result);
} else {
stack.push(parseInt(token, 10));
}
}
return stack.pop();
};
51.82MB, 88ms
