LeetCode Problems

In this tutorial we will solve 150. Evaluate Reverse Polish Notation from leetcode.

Reference: 150. Evaluate Reverse Polish Notation

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].
```

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
```

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();
};
```

**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