Prompt
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
- The valid operators are
'+','-','*', and'/'. - Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
Examples
- Example 1:
- Input: tokens = [“2”,“1”,”+”,“3”,”*”]
- Output: 9
- Explanation: ((2 + 1) * 3) = 9
- Example 2:
- Input: tokens = [“4”,“13”,“5”,”/”,”+”]\
- Output: 6
- Explanation: (4 + (13 / 5)) = 6
- Example 3:
- Input: tokens = [“10”,“6”,“9”,“3”,”+”,“-11”,”*”,”/”,”*”,“17”,”+”,“5”,”+”]
- Output: 22
- Explanation:
- ((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
Solution
In C++
bool is_op(string str) {
return
str == "+" ||
str == "-" ||
str == "*" ||
str == "/";
}
int apply_op(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '*': return a * b;
case '/': return a / b;
case '-': return a - b;
}
return 0;
}
int evalRPN(vector<string>& tokens) {
stack<int> stack;
for (const string& str : tokens) {
if (is_op(str)) {
int b = stack.top(); stack.pop();
int a = stack.top(); stack.pop();
char op = str[0];
int answer = apply_op(a, b, op);
stack.push(answer);
} else {
stack.push(stoi(str));
}
}
return stack.top();
}Explanation
Use a stack. Store the answer on the stack as well. Once the entire expression is evaluated, the final remaining element of the stack will be the final answer.
Big O Analysis
Time Complexity