Node JS formula parser recursive decent

Available for download at:  BitBucket

Javascript based formula elevator that does not require use of eval.   I wrote this code to test some ideas about how to use function pointers to completely decouple the implementation from class specification.

I used the function pointer style of the command pattern rather than inheritance because I originally intended to use this problem as an experiment in GO and RUST where function pointers are first class citizens.

Once I started playing with ideas in JavaScript the rest just kind of fell out. I don’t like the recursive descent mechanism in JavaScript due to the stack overhead but it would be great for languages that do a better job of tail recursion optimization like Scala.

It works but I would modify to remove recursion before heavier use. Other TODO are in the Readme file at bitbucket.

  • Applies JavaScript GREP to simplify parsing
  • Uses recursive descent parser to apply operator precedence
  • function pointer operator interface makes adding new operators easy.
  • V 0.001
  • (C) Jan-2017, MIT Free Use, No promises, No Warranty

We provide consulting services. Contact

Sample Formula

3+2 =

5 + 4 C + 8 =

-4*6/2 =

3! / 11 A + 9 =

3! / 11 =

0.4 1/x * 3 =

807 * 807 =

9999999999999.0 * 999999999999.0 =

calc.js – main implementation code

/* Simple calculator modeled on command pattern
using implementation swappable function pointers
this is the same general style that would work
well in Scala, Go and C where function pointers
are first class citizens.

Note: Could  remove the recursion overhead using a status
stack as we descend the parse priority but not worth
it for short expressions.
*/


var GBLLogLevel = 2;
function setLogLevel(ll) {
  GBLLogLevel = ll;
}
exports.setLogLevel = setLogLevel;
function log(ll, msg) {
  if (ll >= GBLLogLevel ) {
    console.log(msg);
  }
}
exports.log = log;

if (typeof Math.factorial === "undefined") {
  Math.factorial = function factorial (n) {
    if (n == 0 || n == 1)
      return 1;
    if (Math.factorial.f[n] > 0)
      return Math.factorial.f[n];
    else
      return Math.factorial.f[n] = factorial(n-1) * n;
  };
  Math.factorial.f = [];
}

/* fix common syntax variations such as 2+2 to 2 + 2
to make tokenizing parser easier */
function fixupLine(aline) {
  return aline.replace(/([\*\\+\-\!\C/])/g, " $1 ")
    .replace(/\s+/g, " ") // consolidate spaces
    .replace(/.*A/g, "") // elimiate anything before A
    .replace(/1\s+\/\s+x/g,"1/x") // reassamble 3 char oper to single token
    .replace(/.*Q.*/,"Q")
    .replace(/\s\d+\sC/g,"") // remove last entry before C
    .replace(/([\*\\+\-/])\s*([\*\\+\-/])/g,"$2") // remove duplicate operates like ++ or +* since only last applies.
    .replace(/[\=]$/,"") // remove dangling operands because do not do anything
    .trim();
}
exports.fixupLine = fixupLine;

// class object
function makeCalc(oper) {
   obj = {};
   obj.num = 0;
   obj.reg = 0;
   obj.oper = oper;
   obj.make = oper.new; // method to use ot construct more instanes if needed.
   return obj;
}

// Rule if + - then could be sub phrase with higher precendence following so
// recursively process.  If it is a * / then
// can process curren value and next number


// Command pattern requires methods independant from calculator
// object to allow different implementations to be supplied by different
// methods without changing the class defenition of Calc.
function clearAll(calc, remain) {
  calc.num = 0;
  calc.reg = 0;
  return nextTok(calc,remain);
}

function add(calc, remain) {
  if (remain.length < 1) return calc.num;
  var nCalc = calc.make(calc.oper);
  var subVal = nCalc.oper.NN(nCalc,remain);
  log(0,"   add calc.num = " + calc.num +  " subVal=" + subVal + " remain=" + remain);
  calc.num += subVal
  return calc.num;
}

function sub(calc, remain) {
  if (remain.length < 1) return calc.num;
  var nCalc = calc.make(calc.oper);
  var subVal = nCalc.oper.NN(nCalc,remain);
  log(0,"   sub calc.num = " + calc.num +  " subVal=" + subVal + " remain=" + remain);
  calc.num -= subVal
  return  calc.num;
}

function mult(calc, remain) {
  log(0,"   mult calc.num = " + calc.num + " remain=" + remain);
  if (remain.length < 1) return calc.num;
  calc.num = calc.num * remain.shift();
  return calc.oper.NN(calc, remain);
}

function divide(calc, remain) {
  log(0,"   div calc.num = " + calc.num + " remain=" + remain);
  if (remain.length < 1) return calc.num;
  var next = remain.shift();
  if (parseFloat(next) === 0) {
    calc.num = Infinity;
    return Infinity;
  }
  calc.num = calc.num / next;
  return calc.oper.NN(calc, remain);
}


function factorial(calc, remain) {
  log(0,"  factorial calc.num = " + calc.num + " remain=" + remain);
  calc.num = Math.factorial(calc.num);
  log(0,"  after factorial = " + calc.num);
  return calc.oper.NN(calc, remain);
}


function divideIntoOne(calc, remain) {
  log(0,"  divideIntoOne calc.num = " + calc.num + " remain=" + remain);
  calc.num = 1.0 / calc.num;
  log(0,"  after divideIntoOne = " + calc.num);
  return calc.oper.NN(calc, remain);
}

function quit(calc, remain) {
  log(3,"   quit calc.num = " + calc.num + " remain=" + remain);
  process.exit(-1);
}

function nextTok(calc, remain) {
  log(1,"   nextTok calc.num = " + calc.num +  " numRem=" + remain.length + " remain=" + remain);
  if (remain.length == 0) {
    log(1,"   nextTok Last calc.num= " + calc.num );
    return calc.num;
  }

  var tkn = remain.shift().trim();
  while ((remain.length > 0) && (tkn.length < 1)) {
    tkn = remain.shift().trim();
  }

  if (tkn in calc.oper) {
    var opCode = calc.oper[tkn]
    var tres = opCode(calc, remain);
    return calc.num;
  }
  else {
    if (tkn.length > 0 ) {
      // this token isn't a op code so must
      // be a number we have to do something with.
      var pnum = parseFloat(tkn);
      if (isNaN(pnum ) === false) {
        calc.num = pnum
        log(1,"   nextTok simpleVal=" + calc.num, " tkn=" + tkn);
      }
    }
    return nextTok(calc, remain);
  }
}

var defaultOperatMethods = {
    "Q" : quit,
    "A" : clearAll,
    "+" : add,
    "-" : sub,
    "*" : mult,
    "/" : divide,
    "!" : factorial,
    "1/X" : divideIntoOne,
    'NN': nextTok,
    'new' : makeCalc
};

exports.DefaultOperators = defaultOperatMethods;


function parse(aLine) {
   var fixLine = fixupLine(aLine);
   var tokens =  fixLine.split(" ");
   return tokens;
}
exports.parse = parse;


function executeTokens(tokens, oper) {
  var calc = oper.new(oper);
  return oper.NN(calc, tokens);
}


function execute(aStr, oper) {
  if (oper === undefined) {
    oper = defaultOperatMethods;
  }
  var fstr = fixupLine(aStr);
  var calc = oper.new(oper);
  var tokens = parse(fstr);
  var ares = executeTokens(tokens, oper);
  log(2,"IN=" + aStr +   "\n  Result=" + ares);
  return ares;
}


exports.execute = execute;

 

Test driver code

/* Test Driver for
  calc.js
  Tested with node.js V4.4.1
*/

var calc = require('./calc.js');
var log = calc.log;
//calc.setLogLevel(0); // set to 0 for verbose logging // leave default or =3 for most operations

/*********
*** Test Driver Code
**********/
var GBLTestPatterns = [
  ["2+2 =", 4],
  ["7 + 8 C + 7 =", 14],
  ["-5*5/3 =", -8.333333333333334],
  ["5! / 12 A + 9 =", 9],
  ["5! / 12 =", 10],
  ["0.5 1/x * 2 =", 4],
  ["807 * 807", 651249 ],
  ["9999999999999.0 * 999999999999.0", 9.999999999989e+24],
  ["13828 / 0",Infinity],
  ["128383*51C", 128383],
  ["(1+2)*(3-1)*2",12],  // expected to fail because did not implement ()
  ["0.5 1/x Q * 2 =", "Q"],
  ["Q", "Q"]
]


function testLine(aline, ans) {

  log(1,"in=" + aline);
  var tout = calc.fixupLine(aline);
  log(1," out=" + tout);

  var parsedArr = calc.parse(tout);
  log(1,"  parsed=" + parsedArr);

  var ares = calc.execute(aline, calc.DefaultOperators);
  if (ares === ans) {
    log(3,"  sucess");
  }
  else {
    log(13," fail  expected " + ans + " got " + ares);
  }
}


function testExecute(patts) {
  for (var lc in patts) {
    var tst = patts[lc];
    var inp = tst[0];
    var ans = tst[1];
    log(0, "inp=" + inp + " ans=" + ans)
    testLine(inp, ans);
  }
}

testExecute(GBLTestPatterns);

REPL Code

The novel aspect of this REPL is reading characters 1 at a time from stdin in node.js so it can immediately execute the calculation as soon as it encounters the = or \n input from the keyboard.   Most code reading from stdin uses the readln module.  This alternative is more flexible.

/*
  Add a REPL loop to the calculator function
  tested with node.js V4.4.1
  Node. Could use non blocking but not required for spec.
*/
const readline = require('readline');
const fs = require('fs');
const calc = require('./calc.js');
const log = calc.log;
var stdin = process.stdin;
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.setRawMode(true);

var validCharsStr = "0123456789-+*/=!ACQX\n\r";
validChars = {};
for (var vx in validCharsStr) {
  validChars[validCharsStr[vx]] = vx;
}
log(3, "validChars=" + validCharsStr);

function calcRepl() {
  var cmd = "";
  var buffer = " ";

  process.stdin.on('data', function (text) {
      //log(3, 'calcRep1 received data:**' + text+"**");
      text = text.toUpperCase();
      if (!(text in validChars)) {
        process.stdout.write("\007");
      }
      else if (text === 'Q') {
          process.exit(-1);
      }
      else if (text === "A") {
        cmd = "";
        process.stdout.write("\nAll Clear\n\nFormual>")
      }
      else if (( text === "=") || (text === "\r") || (text === "\n") || (text == "")) {
        var ares = calc.execute(cmd, calc.DefaultOperators);
        cmd = "";
        process.stdout.write("\nFormual>")
      }
      else if (text >= " ") {
        cmd += text;
        process.stdout.write(text);
      }
    });
}


calcRepl();

Code snippets added dynamically using PCSH syntax highlighter which reads the code directly from BitBucket.

Leave a Reply