infix-expression.js

// This is an extremely fun exercise and I could have probably
// used something way simpler than this. But I love parsing <3
// For this lil calculator, I used a few mutually recursive
// functions aided by two very simple operations (or, star). It
// is an extremely simplified version of how Parsing Expression
// Grammars (PEG) work.

// Here's how it'd read in plain PEG

// Expr   <- _ Term
// Term   <- Fact (('+' / '-') _ Fact)*
// Fact   <- Unary (('*' / '/') _ Unary)*
// Unary  <- '-' _ Value / Value
// Value  <- '(' _ Expr ')' _ / Number
// Number <- Dec '.' Dec / Dec
// Dec    <- '-'? [0-9]*
// _      <- ' '*

class ParsingError extends Error {}

function infix(expr) {
  // ---- Parsing infrastructure ----
  let cursor = 0;
  const curr = () => expr[cursor];
  const next = () => expr[cursor++];
  const test = (c) => curr() === c;
  const match = (c) => test(c) && next();
  const expect = (c) => match(c) || error(`Expected char ${c} at ${cursor}`);
  const error = (msg) => { throw new ParsingError(msg); };
  const ws = () => { while (/[\s\t\n\r]/.test(curr())) next(); };
  // ---- Primitive operations ----
  const _isParsingErr = (e) => { if (!e instanceof ParsingError) throw e; };
  const or = (...choices) => {
    const saved = cursor;
    for (const choice of choices) {
      try { return choice(); }  // Backtrack
      catch (e) { _isParsingErr(e); cursor = saved; continue; }
    };
    throw new ParsingError();
  };
  const star = (f) => {
    const out = [];
    while (true) {
      try { out.push(f()); }
      catch (e) { _isParsingErr(e); return out; }
    }
  };
  // ---- Teeny lil parsers ----
  const _digits = () => {
    const digits = [];
    while (/\d/.test(curr())) digits.push(next());
    return digits.join('');
  };
  // Dec  <- '-'? [0-9]*
  const Dec = (base=10) => {
    const negative = Boolean(match('-'));
    const number = parseInt(_digits(), base);
    return negative ? -number : number;
  };
  // Unary  <- '-' Value / Value
  const _Unary = () => {
    // We only have one unary operator
    const operator = expect('-'); ws();
    const operand = Value();
    return -operand;
  };
  const Unary = () => or(_Unary, Value);
  // _ generic binary operator
  const _Binary = (operator, operand) => {
    const left = operand(); ws();
    const right = star(() => {
      const rator = operator(); ws();
      const rand = operand();
      return [rator, rand];
    });
    if (right.length === 0) return left;
    return right.reduce((acc, v) => {
      const [op, right] = v;
      return {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => a / b,
      }[op](acc, right);
    }, left);
  };
  // Number <- Dec '.' Dec / Dec
  const _Float = () => {
    const dec = _digits(); expect('.');
    return parseFloat(`${dec}.${_digits()}`);
  };
  const Number = () => or(_Float, Dec);
  // Value  <- '(' Expr ')' / Number
  const Value = () => or(() => {
    expect('('); ws();
    const expr = Term();
    expect(')'); ws();
    return expr;
  }, Number);
  // Term   <- Fact (('+' / '-') Fact)*
  const Term = () => {
    const operator = () => or(() => expect('+'), () => expect('-'));
    return _Binary(operator, Fact);
  };
  // Fact   <- Unary (('*' / '/') Unary)*
  const Fact = () => {
    const operator = () => or(() => expect('*'), () => expect('/'));
    return _Binary(operator, Unary);
  };
  // Expr   <- _ Term
  ws();
  return Term();
}

var calc = function (expression) {
  return infix(expression);
};