TrainShunting

For ages now I've been trying to implement the Shunting Yard Algorithm to take an expression and evaluate it. Yesterday I finally did it! I completed an iterative Shunting Yard Algorithm along with an evaluation function. The current calculator application is just using the built in javascript eval() function, but now that my shunting yard algo is finished I can use that!

The reason my algorithm is special is that it doesn't just return the prefix statement, but also returns the operator stack and output stack after each pass through the loop! This was actually a little tricky because I needed to make copies of the array at each stage rather than just make a reference to the array. If I had not used Array.from() to make a copy at each stage, I would end up with an array of references to the same object. In other words I would end up with a javascript object containing the final prefix expression, an array of multiple copies of the final prefix expression, and an array of empty arrays.

Another problem I ran into was that, since I was doing this algorithm so infrequently, I never actually took the time out to learn it. I was trying to implement it from pure pseudo-code rather than understand what was actually happening. Understanding what was happening wasn't easy either though, I had never heard of operator associativity or precedence (maybe they're worth a short post in and of themselves). Once I finally had a grasp on it thought, the implementation was fast.

One improvement I want to make is to my evaluate function. I think there must be a way to evaluate the prefix expression recursively (like a recursive in order tree traversal), but right now I'm evaluating it iteratively.

Here's the code, it's got a lot of cleaning up and commenting to do, but what I've got now is in functioning order. Also notice that it currently doesn't handle sin, cos, tan functions.

	var trainShunting = {
	isReallyNaN: function(x){
	return x!==x;
	},
	hashCode: function(x){
	var hash = 0, i, chr, len;
	if (x.length === 0) return hash;
	for (i = 0, len = x.length; i < len; i++) {
	chr = x.charCodeAt(i);
	hash = ((hash << 5) - hash) + chr;
	hash |= 0; // Convert to 32bit integer
	}
	return hash;
	},
	evaluate: function(str){
	var val = 0;
	var stack = [];
	var left, right;
	while(str.length > 0){
	val = str.shift();
	let isOperator = (val === "+" || val === "-" || val === "/" || val === "*" || val === "(" || val === ")" || val === "^");
	if(isOperator){
	right = stack.pop();
	left = stack.pop();
	str.unshift(eval(String.concat(left,val,right)));
	} else {
	if(str.length === 0)
	return val;
	stack.push(val);
	}
	}
	},
	toPreFix: function(str){
	// algo: https://en.wikipedia.org/wiki/Shunting-yard_algorithm
	let prefixQueue = [], operatorStack = [], timeOperatorStack = [], prefixQueueStack = [], ret = {}, vals = [] ;
	// take out the digits and operators then use the train shunting algo
	// for each value in the string, I'm running the function... basically running it N times
	str.match(/\d+\.+\d+|\d+|[\^+\*\-()/]/g).map((val) => {
	if(val != "undefined"){
	let isNaN = this.isReallyNaN(parseFloat(val));
	// console.log(val); console.log(this.hashCode(val));
	let isOperator = (val === "+" || val === "-" || val === "/" || val === "*" || val === "(" || val === ")" || val === "^");
	// push numbers to the prefixQueue
	if(!isNaN && !isOperator){
	prefixQueue.push(val);
	} else if(isNaN && isOperator) {
	// if we're at an operator
	let nextOperator = operatorStack[operatorStack.length-1];
	// at parenthases, we push everything from the operatorStack to the prefixQueue
	if(val === ")"){
	while(nextOperator != "("){
	prefixQueue.push(operatorStack.pop());
	nextOperator = operatorStack[operatorStack.length-1];
	}
	// get rid of trailing paren from the operatorStack
	operatorStack.pop();
	// dealing with left associative operators
	} else if(
	((val === "+" || val === "-") && (nextOperator === "*" || nextOperator === "/"))
	|| ((val === "*" || val === "/") && (nextOperator === "/" || nextOperator === "*"))
	){
	prefixQueue.push(operatorStack.pop());
	operatorStack.push(val);
	} else {
	operatorStack.push(val);
	}
	}
	prefixQueueStack.push(Array.from(prefixQueue));
	timeOperatorStack.push(Array.from(operatorStack));
	}
	});
	while(operatorStack.length > 0){
	prefixQueue.push(operatorStack.pop());
	}
	timeOperatorStack.push(Array.from(operatorStack));
	ret = {prefixQueue: prefixQueue, operators: timeOperatorStack, prefixes: prefixQueueStack }
	return ret;
	}
	}

view raw trainShunting.js hosted with ❤ by GitHub