-
-
Save amok/9f61b1234695f35c290e to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| // EVALUATOR | |
| function Evaluator() { | |
| this.isBinaryFunction = { | |
| '+': true, | |
| '-': true, | |
| '*': true, | |
| '/': true | |
| }; | |
| this.functions = { | |
| '+': function(args) { | |
| return args[0] + args[1]; | |
| }, | |
| '-': function(args) { | |
| return args[0] - args[1]; | |
| }, | |
| '*': function(args) { | |
| return args[0] * args[1]; | |
| }, | |
| '/': function(args) { | |
| return args[0] / args[1]; | |
| }, | |
| 'SUM': function(args) { | |
| var sum = 0; | |
| for ( var i = 0; i < args.length; i++ ) { | |
| sum += args[i] | |
| } | |
| return sum; | |
| } | |
| }; | |
| } | |
| Evaluator.prototype = { | |
| evaluateRPN: function(rpn) { | |
| if ( ! Array.isArray(rpn) ) { | |
| return value; | |
| } | |
| var evaluationStack = []; | |
| for (var i = 0; i < rpn.length; i++) { | |
| var token = rpn[i]; | |
| if ( token === '^' ) { | |
| var oper = evaluationStack.pop(); | |
| var func = this.functions[oper]; | |
| var arity = this.isBinaryFunction[oper] ? 2 : evaluationStack.pop(); | |
| var args = []; | |
| for (var j = 0; j < arity; j++) { | |
| args.push( evaluationStack.pop() ); | |
| } | |
| var res = func(args); | |
| evaluationStack.push(res); | |
| } else { | |
| evaluationStack.push(token); | |
| } | |
| } | |
| return evaluationStack.pop(); | |
| }, | |
| evaluateAST: function(ast) { | |
| if ( ! Array.isArray(ast) ) { | |
| return ast; | |
| } | |
| var oper = ast[0]; | |
| var func = this.functions[oper]; | |
| var evaluatedArgs = []; | |
| for (var i = 1; i < ast.length; i++) { | |
| evaluatedArgs.push( this.evaluateAST(ast[i]) ); | |
| } | |
| var res = func(evaluatedArgs); | |
| return res; | |
| } | |
| } | |
| // AST to RPN Convetor | |
| var isBinaryFunction = { | |
| '+': true, | |
| '-': true, | |
| '*': true, | |
| '/': true | |
| }; | |
| function AST2RPN(ast, rpn) { | |
| var isReady = false; | |
| if (!rpn) { | |
| isReady = true; | |
| rpn = [] | |
| }; | |
| if (!Array.isArray(ast)){ | |
| rpn.push(ast); | |
| return ast; | |
| } | |
| var operator = ast[0]; | |
| rpn.push('^'); // operator flag | |
| rpn.push(operator); | |
| if (! isBinaryFunction[operator] ) { | |
| // push number of arguments for not binary functions | |
| rpn.push(ast.length-1); | |
| } | |
| for (var i = 1; i < ast.length; i++) { | |
| var arg = ast[i]; | |
| AST2RPN(arg,rpn); | |
| }; | |
| if (isReady) { | |
| return rpn.reverse(); | |
| } | |
| } | |
| // BENCHMARK | |
| function timeRPN(rpn) { | |
| var evaluator = new Evaluator(); | |
| console.time('EVALUATE RPN'); | |
| for (var i = 0; i < 1000000; i++) { | |
| var res = evaluator.evaluateRPN(rpn); | |
| } | |
| console.timeEnd('EVALUATE RPN'); | |
| } | |
| function timeAST(ast) { | |
| var evaluator = new Evaluator(); | |
| console.time('EVALUATE AST'); | |
| for (var i = 0; i < 1000000; i++) { | |
| var res = evaluator.evaluateAST(ast); | |
| } | |
| console.timeEnd('EVALUATE AST'); | |
| } | |
| var ast1 = ['SUM', | |
| [ '-',['+',['/',['*',10,20],30],40],50], | |
| [ '-',['+',['/',['*',10,20],30],40],50], | |
| [ '-',['+',['/',['*',10,20],30],40],50], | |
| [ '-',['+',['/',['*',10,20],30],40],50] | |
| ]; | |
| var rpn1 = AST2RPN(ast1); | |
| timeRPN(rpn1); | |
| timeAST(ast1); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment