Evaluate Reverse Polish Notation in Javascript
Input: ["3", "1", "+", "5", "*"]
Output: 9
Explanation: ((3 + 1) * 5) = 20
Algorithm:
The key thing to realize in this to use stack as a data structure for the solution. Also, in most of the mathematical operations stack is used.
- Push operands to stack until you encounter an operator
- When you encounter an operator, pop two operands from stack
- Calculate operands using given operator and push the result to the stack
Solution:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function RPN (seq) { | |
if (seq.length <= 2) { | |
console.log('Please enter valid RPN'); | |
return; | |
} | |
let operands = ['+', '-', '*', '/' ], | |
stack = [], | |
i = 0; | |
stack.push(seq[i]); | |
i++; | |
while (i <= seq.length) { | |
let item = seq[i]; | |
if (isNaN(item)) { | |
let operandIndex = operands.indexOf(item); | |
if (operandIndex == 0) { | |
// pop the stack by removing the last element | |
// splice mutates the array | |
// let a = parseInt(stack.splice(-1)[0], 10), | |
let a = parseInt(stack.pop(), 10), | |
b = parseInt(stack.pop(), 10); | |
stack.push(a+b); | |
} | |
if (operandIndex == 1) { | |
let a = parseInt(stack.pop(), 10), | |
b = parseInt(stack.pop(), 10); | |
stack.push(b-a) | |
} | |
if (operandIndex == 2) { | |
let a = parseInt(stack.pop(), 10), | |
b = parseInt(stack.pop(), 10); | |
stack.push(a*b) | |
} | |
if (operandIndex == 3) { | |
let a = parseInt(stack.pop(), 10), | |
b = parseInt(stack.pop(), 10); | |
stack.push(b/a) | |
} | |
} else { | |
stack.push(parseInt(item, 10)); | |
} | |
i++ | |
} | |
return stack[0]; | |
}; | |
console.log(RPN(["2", "1", "+", "3", "*"])) // 9 | |
console.log(RPN(["4", "13", "5", "/", "+"])) // 6 | |
console.log(RPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) // 22 | |
console.log(RPN(["2", "1"])) // Please enter valid RPN undefined |