Shunting Yard

gistfile1.js

//the Shunting Yard algorithm: turns infix expressions into postfix (RPN)
//supports all but function expressions
//written both for fun, and as an attempt to:
// 1. build a query-less system (only commands)
// 2. follow the "Functions Do Only One Thing" law (or what Uncle Bob calls
//	   "extract until you drop")
//1 is violated once, in parse.op_weaker; a clever solution will have to be
// found to bypass that hurdle. 2 is violated in parse.parse_op, but as soon as
//	I can name that damn while loop, it should be solved.
function shunting_yard ( infix, operators ) {
	var postfix = parse( lex(infix, operators), operators );
	return postfix.map( stringify_token ).join( ' ' );

	function stringify_token ( token ) {
		return token.value.toString();
	}
}

function lex ( input, operators ) {
	var re = create_lexer_regex( operators );

	return tokenize_stack( input.match(re) );

	function tokenize_stack ( stack ) {
		if ( !stack ) {
			return;
		}
		return stack.map( tokenize_item );
	}

	function tokenize_item ( item ) {
		if ( item in operators ) {
			return tokenize_op( item );
		}
		return tokenize_num( item );
	}

	function tokenize_op ( op ) {
		var op_obj = operators[ op ];

		return {
			value	   : op,
			precedence : op_obj.precedence,
			assoc	   : op_obj.assoc,
			type	   : 'operator'
		};
	}

	function tokenize_num ( num ) {
		return {
			value : num,
			type  : 'number'
		};
	}

	function create_lexer_regex () {
		var op_names = Object.keys( operators );

		return new RegExp( '\d+|[\\' + op_names.join('\\') + ']', 'g' );
	}
}

function parse ( tokens, operators ) {
	var out_stack = [], op_stack = [];

	while ( tokens.length ) {
		parse_token( tokens.shift() );
	}
	while ( op_stack.length ) {
		out_stack.push( op_stack.pop() );
	}

	return out_stack;

	function parse_token ( token ) {
		if ( token.type === 'number' ) {
			parse_num( token );
		}
		else {
			parse_op( token );
		}
	}

	function parse_num ( num ) {
		out_stack.push( num );
	}

	//a violation of functions-do-only-one-thing
	function parse_op ( op ) {
		//I don't like this
		while ( op_top() && op_weaker(op, op_top()) ) {
			out_stack.push( op_stack.pop() );
		}

		op_stack.push( op );
	}

	//a violation of query-less systems
	function op_weaker ( op0, op1 ) {
		if ( op0.precedence < op1.precedence ) {
			return true;
		}
		return op0.assoc === 'left' && op0.precedence === op1.precedence;
	}

	function op_top () {
		return op_stack[ op_stack.length - 1 ];
	}
}