Problem
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression.For example:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Naive Approach
It can be solved using Stack
- Read array
- Push item into stack if it is number
- Pop numbers from stack, if item is operator, do the operation for those numbers and push into the stack
function evalRPN(tokens) { var returnValue = 0; var operators = "+-*/"; var stack = []; for (var i=0; i<tokens.length; i++) { if (operators.indexOf(tokens[i]) == -1) { stack.push(tokens[i]); } else { var a = parseInt(stack.pop()); var b = parseInt(stack.pop()); switch (tokens[i]) { case "+": stack.push(a + b); break; case "-": stack.push(b - a); break; case "*": stack.push(a * b); break; case "/": stack.push(b / a); break; } } } returnValue = parseInt(stack.pop()); return returnValue; } console.log(evalRPN(['2','1','+','3','*']));
Complexity
This algorithm takes O(n) space and O(n) time
I like this post! The company https://topessaybrands.com/review/ewriters-pro-review/ has been around for more than a decade now. Within this time, they have brought more than 1,500 academic paper helpers on board. Among the papers that this platform handles include all types of essays (marketing, physics, nursing, chemistry, critical analysis, admission, etc.). They also handle other kinds of assignments like
ReplyDeleteSMCC Conjugation Kit for Amine Cd-based Core/shellQuantum Dots-450 nm - We offer a bright and efficient portfolio for printed electronics, leading the industry in nanoparticle engineering and formulation. We can help you develop and commercialize new product designs. Time-to-market is minimized with rapid material screening and robust quality control processes. This ensures that only the highest quality materials are released to the electronics markets.
ReplyDelete