Skip to content

Instantly share code, notes, and snippets.

@cdelahousse
Last active August 29, 2015 14:03
Show Gist options
  • Save cdelahousse/83f2094ba3764d8ca2ec to your computer and use it in GitHub Desktop.
Save cdelahousse/83f2094ba3764d8ca2ec to your computer and use it in GitHub Desktop.
Reverse Polish Notation Math Expression Parser
function assert(res, expected) {
var result = rpn(res);
if (result !== expected) {
throw new Error('Not equals: ', result);
}
}
function apply(operator, opd1, opd2) {
var str = 'return ' + opd1 + operator + opd2 + ';';
return (new Function(str))();
}
function isOperator(char) {
return "*/+-".indexOf(char) > -1;
}
function rpn(str) {
function rpnRecur(stack) {
var last = stack.pop();
if (isOperator(last)) {
var oper = last;
var opd1 = rpnRecur(stack);
var opd2 = rpnRecur(stack);
stack.push(apply(oper, opd1, opd2));
return rpnRecur(stack);
} else {
return +last;
}
}
var ast = str.split(' ');
return rpnRecur(ast);
}
assert('1', 1);
assert('1 2 +', 3);
assert('1 2 -', 1);
assert('1 2 3 + +', 6);
assert('1 2 + 3 + 4 +', 10);
assert('1 2 + 3 + 4 -', -2);
assert('2 2 *', 4);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment