Mathematical equation syntax tree

Question

I'm writing these pieces of code to parse expressions in the context of a dice rolling application for DnD. It's pretty much my first try using TypeScript and I'm not that good in Javascript. It is also the first time I write a syntax tree.

It's been tested using the Jasmine framework.

I'll split the question in two blocks :

Parsing the expression into tokens

a.k.a converting "1+21-314" to ['1','+','21','-','314']). This part of the code is fairly easy but I find there's lot of nesting for such a simple operation, is there maybe a way to take care of this problem using the map/reduce pattern? :

class ExpressionTokenizer {
    public parse(expression : string) : Array<string> {
        const emptyString : string = "";
        let tokens: Array<string> = [];

        let buffer : string = emptyString;
        for(var i = 0;i < expression.length;i++) {
            let character : string = expression[i];

            if(isNaN(Number(character))) {
                if(buffer !== emptyString) {
                    tokens.push(buffer);
                }
                buffer = emptyString;
                tokens.push(character);
            } else {
                buffer += character;
            }
        }
        if(buffer !== emptyString) {
            tokens.push(buffer);
        }
        return tokens;
    }
}

Creating a syntax tree from the tokens

The algorithm yields the following results in these test cases :

• "1+2+3" => Add(Add(1,2),3)
• "1*2+3" => Add(Multiply(1,2),3)
• "3*(2+1)" => Multiply(3,Add(2,1))

Again, I don't like nesting. I feel like in such algorithms there's no real choice but maybe I'm wrong.. Is there a way to make the code look better/more explicit?

enum Operator {
    None = 0,
    Add,
    Substract,
    Multiply,
    Divide,
    LeftParenthesis,
    RightParenthesis
}

class Node {
    constructor(public value:number | Operator, public left?:Node, public right?:Node) {
    }
}

class SyntaxParser {
    private static map: { [symbol: string]: Operator } = {};

    private static populateMap() {
        if(Object.keys(SyntaxParser.map).length > 0) return;

        SyntaxParser.map["+"] = Operator.Add;
        SyntaxParser.map["-"] = Operator.Substract;
        SyntaxParser.map["*"] = Operator.Multiply;
        SyntaxParser.map["/"] = Operator.Divide;
        SyntaxParser.map["("] = Operator.LeftParenthesis;
        SyntaxParser.map[")"] = Operator.RightParenthesis;
    }

    constructor() {
        SyntaxParser.populateMap();
    }

    public parseTokens(expression: string): Node {
        if (SyntaxParser.isNumber(expression)) {
            return new Node(Number(expression));
        }

        var tokens = new ExpressionTokenizer().parse(expression);
        var stack: Array<Node> = [];
        var current: Node = new Node(Operator.None);

        for (var index = 0; index < tokens.length; index++) {
            var element = tokens[index];

            if (SyntaxParser.isNumber(element)) {
                SyntaxParser.assignNumber(current, Number(element));
                continue;
            }

            var symbol = SyntaxParser.map[element];
            switch (symbol) {
                case Operator.LeftParenthesis:
                    stack.push(current);
                    current = new Node(Operator.None);
                    break;
                case Operator.RightParenthesis:
                    var head = stack.pop();
                    head.right = current;
                    current = head;
                    break;
                default:
                    if (current.value == Operator.None) {
                        current.value = symbol;
                    } else {
                        var newNode = new Node(symbol, current, null);
                        current = newNode;
                    }
                    break;
            }
        }

        while (stack.length > 0) {
            current = stack.pop();
        }

        return current;
    }

    private static isNumber(value: any): boolean {
        return !isNaN(Number(value));
    }

    private static assignNumber(current: Node, value: number) {
        if (current.left == null) {
            current.left = new Node(value);
        } else {
            current.right = new Node(value);
        }
    }
}

Answer 1

It's pretty much my first try using TypeScript and I'm not that good in Javascript.

TypeScript is a superset of JavaScript. You're essentially already writing JavaScript if you write TypeScript.

If I were you, I would just skip all of this and just do eval or new Function. Others may say "eval is evil", which is true if used incorrectly. But if used correctly, you can easily bypass all of this effort by using the browser's parser to do all of this for you.

Now most of your code uses classes. However, the methods either are static or aren't doing any instance-related operations. The classes are just collections of related functions. Normally I would use classes/constructors only when I spawn instances and do inheritance. If not, I would just make them regular functions under one module.

// expression-tokenizer.js

export function parse(string){ ... }

// syntax-parser.js

function map(string){ ... }

function populateMap(string){ ... }

export function parseTokens(string){ ... }

export function isNumber(string){ ... }

export function assignNumber(string){ ... }

Additionally, an AST can be simply represented by plain objects and arrays. You don't need to go full OOP-ish with classes, instances, types etc.

// node.js

export function createNode(operator, left, right){
  return { type: 'Node', left, right, operator };
}

Vanilla JS has no concept of enums, but can easily be emulated by a map of strings.

// operators.js

export default Object.freeze({
    None            : 'OPERATOR_NONE',
    Add             : 'OPERATOR_ADD',
    Subtract        : 'OPERATOR_SUBTRACT',
    Multiply        : 'OPERATOR_MULTIPLY',
    Divide          : 'OPERATOR_DIVIDE',
    LeftParenthesis : 'OPERATOR_LEFT_PARENTHESIS',
    RightParenthesis: 'OPERATOR_RIGHT_PARENTHESIS',
});

With all that, usage becomes really simple. No instantiations, no special types. Just plain old JavaScript objects being passed around.

import { parse } from './expression-tokenizer.js';
import { createNode } from './node.js';
import Operators from './operators.js';

...

var stack   = [];
var tokens  = parse(expression);
var current = createNode(Operator.None);

Now for your functions...

public parse(expression : string) : Array<string> {
    ...
    for(var i = 0;i < expression.length;i++) {
        let character : string = expression[i];

This could have been simplified if you just split the string into individual characters using string.split and use forEach to loop through them.

expression.split('').forEach(character => {
  // do stuff
});

Same goes for your token parser:

parse(expression).split('').forEach(token => {
  // do stuff
});

---

switch (symbol) {
  case Operator.LeftParenthesis:
    stack.push(current);
    current = new Node(Operator.None);
    break;
  case Operator.RightParenthesis:
    var head = stack.pop();
    head.right = current;
    current = head;
    break;
  default:
    if (current.value == Operator.None) {
      current.value = symbol;
    } else {
      var newNode = new Node(symbol, current, null);
      current = newNode;
    }
    break;
}

I recommend a map of functions instead of a switch statement. The problem with a switch is that it quickly grows and tries to do everything in one piece of code. If you split off each operator into its own function, they become manageable. Here's an example of mapping.

// operations.js
import  Operators  from './operators.js';

const operations = {};

operations[Operators.LeftParenthesis] = function(){...};
operations[Operators.RightParenthesis] = function(){...};
// add more

export default operations;

Now when you use the operations:

import Operations from './operations.js';

export function parseExpression(expression){
  ...
  parse(expression).split('').forEach(token => {
    ...
    var symbol = map(token);

    // Instead of switching the symbol, we use it as key for Operations
    // to call the appropriate operation.
    Operations[symbol].call(null, /* pass in necessary args */ );

    ...

  });
}