-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
0150-evaluate-reverse-polish-notation.js
71 lines (57 loc) · 1.74 KB
/
0150-evaluate-reverse-polish-notation.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* https://leetcode.com/problems/evaluate-reverse-polish-notation
* Time O(N^2) | Space(1)
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens, index = 0) {
while (1 < tokens.length) {/* Time O(N) */
const isOperation = () => tokens[index] in OPERATORS;
while (!isOperation()) index++;/* Time O(N) */
const value = performOperation(tokens, index);
tokens[index] = value;
tokens.splice((index - 2), 2);/* Time O(N) */
index--;
}
return tokens[0];
};
var OPERATORS = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => Math.trunc(a / b),
};
var performOperation = (tokens, index) => {
const [ rightNum, leftNum ] = [ Number(tokens[index - 1]), Number(tokens[index - 2]) ]
const operation = OPERATORS[tokens[index]];
return operation(leftNum, rightNum);
}
/**
* https://leetcode.com/problems/evaluate-reverse-polish-notation
* Time O(N) | Space(N)
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function (tokens, stack = []) {
for (const char of tokens) {/* Time O(N) */
const isOperation = char in OPERATORS;
if (isOperation) {
const value = performOperation(char, stack);
stack.push(value); /* Space O(N) */
continue;
}
stack.push(Number(char)); /* Space O(N) */
}
return stack.pop();
}
var OPERATORS = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => Math.trunc(a / b)
};
var performOperation = (char, stack) => {
const [ rightNum, leftNum ] = [ stack.pop(), stack.pop() ];
const operation = OPERATORS[char];
return operation(leftNum, rightNum);
}