150. Evaluate Reverse Polish Notation
LeetCode Problems
In this tutorial we will solve 150. Evaluate Reverse Polish Notation from leetcode.
Table of Content
Reference: 150. Evaluate Reverse Polish Notation
Problem statement
In this problem statement we are given an input string tokens that represents an arithmetic expression in Reverse Polish Notation. We have to evaluate the expression and return an integer result. There are few points that we have to consider.
- The answer and all the intermediate calculations can be represented in 32 bit integer.
- The valid operations for this problem statement are
+ - * /. - Each operand may be an integer or another expression.
- Division between two integers always truncates towards zero.
- There will not by any division by zero.
The valid operations for this problem statement are + - * /.
Reverse Polish notation (RPN), is a mathematical notation in which operators follow their operands. The notation does not need any parentheses for as long as each operator has a fixed number of operands. - Wikipedia
Example from leetcode.
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
Constraints:
1 <= tokens.length <= 10^4
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Approach
To solve this problem we will use the stack data structure. Each time we encounter an integer value we will push it into the stack. And whenever we encounter an operator (like +) we will first pop two items from the stack. The first popped item will represent the second operand and the second popped item will represent the first operand. We will then perform the operation. The result of the operation will be pushed back into the stack and we will continue parsing the input tokens. In the end, when we have parsed the input token we would have the result in the stack. So, we will pop the result from the stack and return it.
Let us look at the following input tokens = ["2","1","+","3","*"]
stack = []
tokens = ["2", "1", "+", "3", "*"]
^
is current token an operator ? no
-> push the token into the stack
stack = [2]
tokens = ["2", "1", "+", "3", "*"]
^
is current token an operator ? no
-> push the token into the stack
stack = [2, 1]
tokens = ["2", "1", "+", "3", "*"]
^
is current token an operator ? yes
-> pop item from the stack = [2, 1]
-> 1
-> this is the second operand
-> pop item from the stack = [2]
-> 2
-> this is the first operand
-> perform + operation
-> 2 + 1 = 3
-> push the result into the stack
stack = [3]
tokens = ["2", "1", "+", "3", "*"]
^
is current token an operator ? no
-> push the token into the stack
stack = [3, 3]
tokens = ["2", "1", "+", "3", "*"]
^
is current token an operator ? yes
-> pop item from the stack = [3, 3]
-> 1
-> this is the second operand
-> pop item from the stack = [3]
-> 3
-> this is the first operand
-> perform * operation
-> 3 * 3 = 9
-> push the result into the stack
stack = [9]
we have processed the input tokens
so we pop the result from the stack
answer is 9
Code
JavaScript
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
const operators = '+-*/';
let stack = [];
const calc = {
'+': (x,y) => x+y,
'-': (x,y) => x-y,
'*': (x,y) => x*y,
'/': (x,y) => parseInt(x/y),
}
tokens.forEach(t => {
if (operators.indexOf(t) > -1) {
const second = stack.pop();
const first = stack.pop();
const result = calc[t](first, second);
stack.push(result);
} else {
stack.push(+t);
}
});
return stack.pop();
};TypeScript
function evalRPN(tokens: string[]): number {
let stack: number[] = [];
const operators = '+-*/';
const op = {
'+': (x: number, y: number) => x + y,
'-': (x: number, y: number) => x - y,
'*': (x: number, y: number) => x * y,
'/': (x: number, y: number) => parseInt((x / y).toString()),
};
for(let t of tokens) {
if (operators.indexOf(t) > -1) {
const second = stack.pop();
const first = stack.pop();
const result = op[t](first, second);
stack.push(result);
} else {
stack.push(+t);
}
}
return stack.pop();
};Complexity
Time complexity: O(n)
If input tokens is of size n then the time complexity will be O(n).
Space complexity: O(n)
In the worst case, for n input tokens, we will have to save n elements in the stack. So space complexity will be O(n).
ADVERTISEMENT