Math expression parser in JavaScript

Question

I've written the second iteration of my math expression parser, utilising what I learned from the first attempt to make a more reliable, maintainable piece of code.

If anybody wants to see the first iteration to see my progress, see here.

With the first version, I tried to evaluate the expression string directly, without tokenising it and running it through several levels of progressive processing. It turned into a hard-to-follow mess of boolean flags and if-else blocks.

With the second version, I split the process up into various stages:

1. I replace the variables with their stored values.
2. I look for parentheses and parse those recursively, replacing the range of tokens the brackets spanned with their evaluated values.
3. I parse for negative values, making the proceeding token's value either positive or negative, and removing the operator token.
4. I parse for function calls, and replace their token ranges with the resulting value.
5. I parse the arithmetic operators in the standard order of operations, deducing the value on each round until there is only one value left. The value is then returned.

const NUMERIC_CHARSET = '01234567890.',
      ALPHA_CHARSET = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_',
      OPERATOR_CHARSET = '+-/*^%',
      WHITE_SPACE_REGEX = /\s/;

const MathFunctions = {
    sin: radians => Math.sin(radians),
    cos: radians => Math.cos(radians),
    tan: radians => Math.tan(radians),
    fact: value => {
        var iter,
            multiplier;

        for(multiplier = value - 1; multiplier > 0; --multiplier) {
            value *= multiplier;
        }

        return value;
    },
    exp: value => Math.exp(value),
    sqrt: value => Math.sqrt(value),
    ceil: value => Math.ceil(value),
    floor: value => Math.floor(value),
    abs: value => Math.abs(value),
    acos: value => Math.acos(value),
    asin: value => Math.asin(value),
    atan: value => Math.atan(value),
    log: value => Math.log(value),
    round: value => Math.round(value)
};

const Helpers = {
    isNumeric: char => NUMERIC_CHARSET.indexOf(char) !== -1,
    isAlpha: char => ALPHA_CHARSET.indexOf(char) !== -1,
    isOperator: char => OPERATOR_CHARSET.indexOf(char) !== -1,
    isMathFunction: keyword => typeof MathFunctions[keyword] === 'function',
    isWhitespace: char => WHITE_SPACE_REGEX.test(char),
    radians: angle => angle * Math.PI / 180
};

const OperatorFunctions = {
    '+': (left, right) => left + right,
    '-': (left, right) => left - right,
    '/': (left, right) => left / right,
    '*': (left, right) => left * right,
    '%': (left, right) => left % right,
    '^': (left, right) => Math.pow(left, right)
};

function ExpressionParser() {
    'use strict';

    this.variables = {
        pi: Math.PI,
        PI: Math.PI,
        e: Math.E,
        E: Math.E,
        rand: () => Math.random()
    };

    this.readOnlyVariables = [ ];

    for(var varName in this.variables) {
        this.readOnlyVariables.push(varName);
    }
};

/* Sets a variable */
ExpressionParser.prototype.setVariable = function(name, value) {
    'use strict';

    if(this.readOnlyVariables.indexOf(name) !== -1) {
        throw new Error('Error: Cannot set read only variable "' + name + '"');
    }

    this.variables[name] = value;
};

/* Gets a variable */
ExpressionParser.prototype.getVariable = function(name) {
    'use strict';

    if(this.isVariable(name)) {
        var variable = this.variables[name];

        if(typeof variable === 'function') {
            return variable();
        }

        return variable;
    }
};

/* Checks if a variable exists */
ExpressionParser.prototype.isVariable = function(name) {
    'use strict';

    return this.variables.hasOwnProperty(name);
};

/* Parse an expression */
ExpressionParser.prototype.parse = function(expression) {
    'use strict';

    var tokens = this.tokenize(expression);

    tokens = this.parseTokens(tokens);

    var tokensLength = tokens.length,
        iter,
        value = null,
        last_number = null,
        flag_assignment = false;

    for(iter = 0; iter < tokensLength; ++iter) {
        // Get the value
        if(tokens[iter][0] === 'number') {
            value = tokens[iter][1];
        }

        if(tokens[iter][0] === 'assignment') {
            if(
                iter - 1 === 0 &&                   // Check there is a keyword previous
                iter + 1 < tokensLength &&          // Check there is a value to set next

                tokens[iter - 1][0] === 'keyword'
            ) {
                flag_assignment = true;
            } else {
                throw new Error('Error: Unexpected assignment');
            }
        }
    }

    if(flag_assignment) {
        this.setVariable(tokens[0][1], value);
    }

    return value;
};

/* Parse tokens */
ExpressionParser.prototype.parseTokens = function(tokens) {
    'use strict';

    tokens = this.parseVariables(tokens);
    tokens = this.parseBrackets(tokens);
    tokens = this.parseNegatives(tokens);
    tokens = this.parseFunctions(tokens);
    tokens = this.parseOperations(tokens);

    return tokens;
};

ExpressionParser.prototype.parseBrackets = function(tokens) {
    'use strict';

    var tokensLength = tokens.length,
        bracketDepth = 0,
        bracketIndex = 0,
        iter;

    for(iter = 0; iter < tokensLength; ++iter) {
        if(tokens[iter][0] === 'bracket') {
            if(bracketDepth > 0) {
                if(tokens[iter][1] === ')') {
                    --bracketDepth;
                }

                if(bracketDepth === 0) {
                    let leftSide = tokens.slice(0, bracketIndex),
                        parsed = this.parseTokens(tokens.slice(bracketIndex + 1, iter)),
                        rightSide = tokens.slice(iter + 1);

                    tokens = leftSide.concat(parsed, rightSide);
                    iter += tokens.length - tokensLength;
                    tokensLength = tokens.length;
                }
            }

            if(tokens[iter][1] === '(') {
                if(bracketDepth === 0) {
                    bracketIndex = iter;
                }

                ++bracketDepth;
            }
        }
    }

    return tokens;
};

ExpressionParser.prototype.parseNegatives = function(tokens) {
    'use strict';

    var tokensLength = tokens.length,
        iter;

    for(iter = 0; iter < tokensLength; ++iter) {
        // Logic for a negative number
        if(
            tokens[iter][0] === 'operator' &&
            (
                tokens[iter][1] === '-' ||          // Check it's a minus symbol
                tokens[iter][1] === '+'             // Or a plus symbold
            ) &&
            (
                iter - 1 < 0 ||                     // Either there is no previous token...
                tokens[iter - 1][0] !== 'number'    // Or it's not a number
            ) &&
            iter + 1 < tokensLength &&              // Check there is a proceeding token
            tokens[iter + 1][0] === 'number'        // And it's a number
        ) {
            // Make the next number a negative
            tokens[iter + 1][1] = tokens[iter][1] === '-' ? -tokens[iter + 1][1] : tokens[iter + 1][1];
            // Remove this token from stack
            tokens.splice(iter, 1);
            --tokensLength;
            --iter;
            continue;
        }
    }

    return tokens;
};

ExpressionParser.prototype.parseVariables = function(tokens) {
    'use strict';

    var tokensLength = tokens.length,
        iter;

    for(iter = 0; iter < tokensLength; ++iter) {
        if(tokens[iter][0] === 'keyword') {
            if(
                !Helpers.isMathFunction(tokens[iter][1]) && // Check it's not a function
                (
                    iter === tokensLength - 1 ||            // Either this is the last token
                    tokens[iter + 1][0] !== 'assignment'    // Or the next token is not an assignment
                )
            ) {
                // Check variable exists
                if(this.isVariable(tokens[iter][1])) {
                    tokens[iter][0] = 'number';
                    tokens[iter][1] = this.getVariable(tokens[iter][1]);
                    continue;
                } else {
                    throw new Error('Error: Undefined variable "' + tokens[iter][1] + '"');
                }
            }
        }
    }

    return tokens;
};

ExpressionParser.prototype.parseFunctions = function(tokens) {
    'use strict';

    var tokensLength = tokens.length,
        iter;

    for(iter = 0; iter < tokensLength; ++iter) {
        if(tokens[iter][0] === 'keyword' && tokens[iter][1] in MathFunctions) {
            if(
                iter + 1 < tokensLength &&          // Check this is not the last token
                tokens[iter + 1][0] === 'number'    // And the last next token is a number
            ) {
                // Apply math function
                tokens[iter + 1][1] = MathFunctions[tokens[iter][1]](tokens[iter + 1][1]);
                // Remove this token from stack
                tokens.splice(iter, 1);
                --tokensLength;
                --iter;
            } else {
                throw new Error('Error: unexpected function "' + tokens[iter][1] + '"');
            }
        }
    }

    return tokens;
};

ExpressionParser.prototype.parseOperations = function(tokens) {
    'use strict';

    // Order of operations 
    var operators = ['^', '*', '/', '+', '-'];

    operators.forEach(operator => {
        tokens = this.parseOperator(tokens, operator);
    });

    return tokens;
};

ExpressionParser.prototype.parseOperator = function(tokens, operator) {
    'use strict';

    var tokensLength = tokens.length,
        iter;

    for(iter = 0; iter < tokensLength; ++iter) {
        var token = tokens[iter],
            token_type = token[0],
            token_value = token[1];

        if(token_type === 'operator' && token_value === operator) {
            if(
                iter - 1 >= 0 &&                        // Check there is a previous token
                iter + 1 < tokensLength &&              // Check there is a next token
                tokens[iter - 1][0] === 'number' &&     // Check the previous token is a number
                tokens[iter + 1][0] === 'number'        // Check the next token is a number
            ) {
                tokens[iter + 1][1] = OperatorFunctions[token_value](tokens[iter - 1][1], tokens[iter + 1][1]);

                let leftSide = tokens.slice(0, iter - 1),
                    rightSide = tokens.slice(iter + 1);

                // Replace sub-expression with the result value
                tokens = leftSide.concat(rightSide);
                iter += tokens.length - tokensLength;
                tokensLength = tokens.length;

                continue;
            } else {
                throw new Error('Error: unexpected operator "' + tokens[iter][1] + '"');
            }
        }
    }

    return tokens;
};

/**
 * Split expression into tokens
 */
ExpressionParser.prototype.tokenize = function(expression) {
    'use strict';

    // Append space so that the last character before that space is tokenised
    expression += ' ';

    // TOKENIZER VARS
    var expressionLength = expression.length,
        iter,
        tokens = [ ],
        buffer = '';

    // FLAGS
    var flag_numeric = false,
        flag_keyword = false,
        flag_operator = false;

    // Iterate through expression
    for(iter = 0; iter < expressionLength; ++iter) {
        var char = expression.charAt(iter),
            char_isNumeric = Helpers.isNumeric(char),
            char_isOperator = Helpers.isOperator(char),
            char_isAlpha = Helpers.isAlpha(char);

        if(flag_keyword) {
            // We've reached the end of the keyword
            if(!char_isAlpha) {
                flag_keyword = false;
                tokens.push(['keyword', buffer]);
                buffer = '';
            }
        }

        if(flag_numeric) {
            // We've reached the end of the number
            if(!char_isNumeric) {
                // Skip char if comma, so we can allow for formatted numbers
                if(char === ',' && iter + 1 < expressionLength && Helpers.isNumeric(expression[iter + 1])) {
                    continue;
                }

                let parsingFunction = parseInt;

                if(buffer.indexOf('.') !== -1) { // Check for float
                    parsingFunction = parseFloat;
                }

                tokens.push(['number', parsingFunction(buffer, 10)]);

                flag_numeric = false;
                buffer = '';
            }
        }

        if(char_isNumeric) {                     // Check for a number
            flag_numeric = true;
            buffer += char;
        } else if(char_isAlpha) {                // Check for a keyword
            flag_keyword = true;
            buffer += char;
        } else if(char_isOperator) {             // Check for an operator
            tokens.push(['operator', char]);
        } else if(char === '(') {                // Check for parentheses
            tokens.push(['bracket', '(']);
        } else if(char === ')') {                // Check for closing parentheses
            tokens.push(['bracket', ')']);
        } else if(char === '=') {                // Check for assignment
            tokens.push(['assignment', char]);
        } else if(!Helpers.isWhitespace(char)) { // Check for whitespace
            throw new Error('Error: Unexpected char "' + char + '"');
        }
    }

    return tokens;
};

var ep = new ExpressionParser();

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(expression) {
    try {
        var result = ep.parse(expression);
        if(result !== false) {
            console.log(result)
        }
    } catch(e) {
        console.log(e.message);
    }

    process.stdout.write("> ");
});
console.log("Welcome to math2.js:");
process.stdout.write("> ");

Here is the console log for the tests I did:

$ node math2.js
Welcome to math2.js:
> value = 11 + (exp(2.010635 + sin(PI/2)*3) + 50) / 2
110.9999779427841
> c = 3*10^8
300000000
> c*value
33299993382.835228
> sin pi
1.2246467991473532e-16
> sin (pi)
1.2246467991473532e-16
> fact 5
120
> fact(5 + 1)
720
> fact(c)
Infinity
> 22*-.5
-11
> 2,000 + 4,000
6000
> ,2000
Error: Unexpected char ","
> pi sin
Error: unexpected function "sin"
> sin pi
1.2246467991473532e-16
> E^2
7.3890560989306495

I would like to know if there are things I could have done differently that would result in a more efficient process.

Answer 1

One common theme I notice in the code is that you alter existing variables. For instance value in this function:

fact: value => {
    var iter,
        multiplier;

    for(multiplier = value - 1; multiplier > 0; --multiplier) {
        value *= multiplier;
    }

    return value;
},

There's a rule in ESLint called no-param-reassign which will consider this an error if enabled. There's a linked article with regards to why this is harmful, why that ESLint rule exists, and why you shouldn't be doing this. In a gist, altering the value of an argument alters the arguments object itself.

---

this.variables = {
    pi: Math.PI,
    PI: Math.PI,
    e: Math.E,
    E: Math.E,
    rand: () => Math.random()
};

I wonder why these aren't extracted to its own "enum", unless this is something unique to the expression parser.

---

this.readOnlyVariables = [ ];

for(var varName in this.variables) {
    this.readOnlyVariables.push(varName);
}

Shorter:

Object.keys(this.variables).map(varName => varName);

---

/* Gets a variable */
ExpressionParser.prototype.getVariable = function(name) {
    'use strict';

    if(this.isVariable(name)) {
        var variable = this.variables[name];

        if(typeof variable === 'function') {
            return variable();
        }

        return variable;
    }
};

This code implies that there may be a case where this.isVariable(name) is false however there is no return for a falsy case. This can make this function a bit ambiguous especially when it is named getVariable. It implies that the function returns something. If undefined is a valid value, make it explicit in the code.

---

I can't speak much about the parser, although I believe parsing in the simplest sense is just exploding a string into tokens and trying to make sense of it. This may be as simple as having a string be exploded into an array and being fed through a loop of operations, with a few storages (stacks, registers, etc.) to keep state and markers.

In this case, array operations like forEach, map, reduce and filter might be handy in place of loops. From a performance perspective, loops are faster, but from a readability standpoint, array methods are often shorter and more concise.