博文中会简要介绍Leetcode P0150题目分析及解题思路。
“Evaluate Reverse Polish Notation”是一道比较基础的题目。算法的详解可以参考我的这篇博文：表达式求值“利器”：逆波兰算法详解
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
以下是Java的题解代码实现。
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();
for (int idx=0; idx<tokens.length; ++idx) {
switch (tokens[idx]) {
case "+": {
int right = stack.pollFirst();
int left = stack.pollFirst();
stack.offerFirst(right+left);
break;
}
case "-": {
int right = stack.pollFirst();
int left = stack.pollFirst();
stack.offerFirst(left-right);
break;
}
case "*": {
int right = stack.pollFirst();
int left = stack.pollFirst();
stack.offerFirst(right*left);
break;
}
case "/": {
int right = stack.pollFirst();
int left = stack.pollFirst();
stack.offerFirst(left/right);
break;
}
default:
stack.offerFirst(Integer.parseInt(tokens[idx]));
}
}
return stack.pollFirst();
}
}
以下是C++的题解代码实现。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> token_stack;
for (string token: tokens) {
if (token == "+") {
int right = token_stack.top();
token_stack.pop();
int left = token_stack.top();
token_stack.pop();
token_stack.push(left+right);
}
else if (token == "-") {
int right = token_stack.top();
token_stack.pop();
int left = token_stack.top();
token_stack.pop();
token_stack.push(left-right);
}
else if (token == "*") {
int right = token_stack.top();
token_stack.pop();
int left = token_stack.top();
token_stack.pop();
token_stack.push(left*right);
}
else if (token == "/") {
int right = token_stack.top();
token_stack.pop();
int left = token_stack.top();
token_stack.pop();
token_stack.push(left/right);
}
else {
token_stack.push(stoi(token));
}
}
return token_stack.top();
}
};