150. Evaluate Reverse Polish Notation
1. Description
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
2. 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.
3. Example
Example 1:
Input: [“2”, “1”, “+”, “3”, “*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: [“4”, “13”, “5”, “/”, “+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: [“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
4. Solutions
My Accepted Solution
n = i_tokens.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// int evalRPN(vector<string>& tokens)
int evalRPN(const vector<string> &i_tokens)
{
stack<string> numbers;
for(int i = 0; i < i_tokens.size(); i++)
{
if(i_tokens[i] == "+" || i_tokens[i] == "-" || i_tokens[i] == "*" || i_tokens[i] == "/")
{
int right = stoi(numbers.top());
numbers.pop();
int left = stoi(numbers.top());
numbers.pop();
int calculationResult;
if(i_tokens[i] == "+") calculationResult = left + right;
if(i_tokens[i] == "-") calculationResult = left - right;
if(i_tokens[i] == "*") calculationResult = left * right;
if(i_tokens[i] == "/") calculationResult = left / right;
numbers.push(to_string(calculationResult));
}
else
{
numbers.push(i_tokens[i]);
}
}
return stoi(numbers.top());
}
};