As a self-learning project, I wrote an expression parser using the shunting yard algorithm in JavaScript. It's a larger part of what I plan to be a program for handling dice expressions in tabletop games, like 2d6 (2 six-sided dice).
I know a parsing library would be a better fit, but this is also a self-learning project for me, so I'd rather stick to implementing it myself.
My original implementation had functions jcontains
and jpeek
on the array prototype. I decided to refactor those out and now have assignments on arrays I create. But now I have functions like evaluate
setting up functions on arrays. It seems to break SRP but maybe I'm being pedantic.
var exprjs = (function (my) {
"use strict";
var jcontains = function (value, propertyName) {
if (propertyName) {
for (var i = 0; i < this.length; i++) {
if (value === this[i][propertyName]) return this[i];
}
} else {
for (var i = 0; i < this.length; i++) {
if (value === this[i]) return this[i];
}
}
},
jpeek = function () {
return this[this.length - 1];
},
operators = [
{
oper: '+', precedence: 1, associativity: 'left', func: function (a, b) {
trigger(this.oper, b, a);
return b + a;
}
},
{
oper: '-', precedence: 1, associativity: 'left', func: function (a, b) {
trigger(this.oper, b, a);
return b - a;
}
},
{
oper: '*', precedence: 2, associativity: 'left', func: function (a, b) {
trigger(this.oper, b, a);
return b * a;
}
},
{
oper: '/', precedence: 2, associativity: 'left', func: function (a, b) {
trigger(this.oper, b, a);
if (a === 0) {
throw new Error('Divide by 0, attempted to divide ' + b + ' by ' + a);
}
return b / a;
}
},
{
oper: '^', precedence: 3, associativity: 'right', func: function (a, b) {
trigger(this.oper, b, a);
return Math.pow(b, a);
}
}
],
listeners = {},
trigger = function(oper, b, a) {
if (listeners[oper]) {
listeners[oper].forEach(function(func) {
func(b, a);
});
}
},
addListener = function(oper, func) {
if (listeners[oper]) {
listeners[oper].push(func);
} else {
listeners[oper] = [ func ];
}
},
exprParse = function (input) {
var expr = typeof input === 'function' ? input() : input,
operStack = [],
output = [],
numberRegexp = /[\d\.]/,
readToken = function (input) {
var workingToken = '',
oper = '',
isOper = function (input) {
return operators.jcontains(input, 'oper');
},
handleOperator = function (input) {
var peeked = operStack.jpeek(),
lowerPrecedence = function () {
return (input.precedence <= peeked.precedence) || (input.associativity === 'right' &&
input.precedence < peeked.precedence);
};
while (peeked && lowerPrecedence()) {
output.push(operStack.pop());
peeked = operStack[operStack.length - 1];
}
operStack.push(input);
expr = expr.slice(1);
},
handleParens = function (input) {
if (input[0] == '(') {
operStack.push(input[0]);
}
if (input[0] == ')') {
var peeked = operStack.jpeek();
while (peeked !== '(') {
output.push(operStack.pop());
peeked = operStack.jpeek();
}
operStack.pop();
}
expr = expr.slice(1);
};
// Operator?
if (oper = isOper(input[0])) {
handleOperator(oper);
return;
}
// Parentheses?
if (input[0] == '(' || input[0] == ')') {
handleParens(input[0]);
return;
}
//Number?
for (var i = 0; i < input.length + 1; i++) {
if (input[i] && input[i].search(numberRegexp) !== -1) {
workingToken = workingToken.concat(input[i]);
} else {
output.push(+workingToken);
expr = expr.slice(i);
return;
}
}
throw new Error("Unexpected value in expression.");
};
operStack.jcontains = jcontains;
operStack.jpeek = jpeek;
while (expr.length > 0) {
readToken(expr);
}
while (operStack.length > 0) {
output.push(operStack.pop());
}
output.reverse();
return output;
},
evaluate = function (input) {
var workingStack = [],
workingToken,
inputStack = exprParse(input);
inputStack.jpeek = jpeek;
inputStack.jcontains = jcontains;
while (!!((workingToken = inputStack.jpeek()) + (workingToken === 0))) {
if (workingToken.func) {
workingStack.push(workingToken.func(workingStack.pop(), workingStack.pop()));
inputStack.pop();
} else {
workingStack.push(inputStack.pop());
}
}
return workingStack[0];
};
listeners.jpeek = jpeek;
listeners.jcontains = jcontains;
operators.jpeek = jpeek;
operators.jcontains = jcontains;
my.evaluate = evaluate;
my.addListener = addListener;
return my;
}(exprjs || {}));