"use strict";

(function parseExpressionLibrary() {
	// Utility function. Make sure that the denominator isn't 0.
	function checkDenominator(value) {
		if (value === 0) {
			throw "division by zero";
		}
		
		return value;
	}
	
	// Utility function. Make sure that the last calculation didn't result in
	// a NaN or infinity.
	function checkResult(value) {
		if (isNaN(value)) {
			throw "quantity is not a number";
		} else if (!isFinite(value)) {
			throw "quantity is not finite";
		}
		
		return value;
	}
	
	// precedence: Higher binds tighter.
	// associativity: The associativity of the binary form of the operator.
	// unary: Prefix or postfix, depending on the type of the operator.
	// evaluate: Function that executes the operation.
	var characters = {
		"+": {
			precedence: 1,
			unary: "prefix",
			evaluate: function add(u, v) { return u + v; }
		},
		"-": {
			precedence: 1,
			unary: "prefix",
			evaluate: function subtract(u, v) { return u - v; }
		},
		"*": {
			precedence: 2,
			evaluate: function multiply(u, v) { return u * v; }
		},
		"/": {
			precedence: 2,
			evaluate: function divide(u, v) { return u / checkDenominator(v); }
		},
		"%": {
			precedence: 2,
			evaluate: function modulus(u, v) { return u % checkDenominator(v); }
		},
		"^": {
			precedence: 3,
			associativity: "right",
			evaluate: Math.pow
		},
		"!": {
			unary: "postfix",
			evaluate: function factorial(u) {
				if (parseInt(u, 10) !== u || u < 0 || isNaN(u) || !isFinite(u)) {
					throw "factorial is only defined over non-negative integers";
				}
				
				// Calculate factorial the iterative way.
				var v = 1;
				for (var i = 2; i <= u; ++i) {
					v *= i;
				}
				return v;
			}
		},
		"(": {parenthesis: "left"},
		")": {parenthesis: "right"}
	};
	
	// Functions.
	var functions = {
		ln: {func: Math.log},
		exp: {func: Math.exp}
	};
	
	// Numeric constants.
	var constants = {
		pi: Math.PI,
		e: Math.E
	};
	
	// Utility function. Given an operator to consider and the stack of
	// operators to use, should the operator at the top of the stack be
	// evaluated immediately?
	function shouldPopForPrecedence(op1, operators) {
		// Make sure there is an operator at the top of the stack.
		if (operators.length === 0) { return false; }
		
		// Operator at the top of the stack.
		var op2 = operators[operators.length - 1];
		
		if (typeof op2.precedence === "undefined") {
			// Not a "real" operator.
			return false;
		} else if (op1.associativity === "right") {
			// Right-associative operators.
			return op1.precedence < op2.precedence;
		} else {
			// Left-associative operators.
			return op1.precedence <= op2.precedence;
		}
	}
	
	// Utility function. Given the operator stack, should we continue to
	// evaluate operators on the stack in search of a left parenthesis?
	function shouldPopTowardsLeftParenthesis(operators) {
		// The stack must not be empty.
		if (operators.length === 0) { return false; }
		
		// Keep going until we find a left parenthesis.
		return operators[operators.length - 1].parenthesis !== "left";
	}
	
	// Utility function. If the value at the top of the operator stack is a
	// function, execute it with the value at the top of the operand stack.
	function evaluateFunctionIfNeeded(operators, operands) {
		// Check if the value at the top of the stack is a function.
		if (operators.length > 0 && operators[operators.length - 1].func) {
			// Procure the function.
			var func = operators.pop().func;
			
			// Make sure there's an argument.
			if (operands.length < 1) {
				throw "incorrect number of arguments to function";
			}
			
			// Call the function.
			operands.push(func(operands.pop()));
		}
	}
	
	// Utility function. Given the operator and operands stacks, pop the topmost
	// operator and evaluate it, pushing the result on the operand stack.
	function evaluateOperator(operators, operands) {
		// Make sure we have an operator.
		if (operators.length < 1) {
			throw "expected an operator";
		}
		
		// Get the operator.
		var op = operators.pop();
		
		// If we found a left parenthesis, then it is mismatched.
		if (op.parenthesis === "left") {
			throw "mismatched parenthesis";
		}
		
		// Check if it is a function.
		if (op.func) {
			// Put it back on the stack and call it.
			operators.push(op);
			evaluateFunctionIfNeeded(operators, operands);
		} else if (op.unary === "postfix") {
			// Make sure we have an operand.
			if (operands.length < 1) {
				throw "incorrect number of operands to postfix operator";
			}
			
			// Evaluate the operator.
			operands.push(op.evaluate(operands.pop()));
		} else {
			// Make sure we have operands.
			if (operands.length < 2) {
				throw "incorrect number of operands";
			}
			
			// Get the operands.
			var arg2 = operands.pop();
			var arg1 = operands.pop();
			
			// Evaluate the operator.
			operands.push(op.evaluate(arg1, arg2));
		}
	}
	
	// Pass in a string to evaluate it.
	window.parseExpression = function parseExpression(expression, variables) {
		// If it's already a number, don't attempt to parse it.
		if (typeof expression === "number") { return expression; }
		
		// State variables.
		var operands = [], operators = [];
		var literal = "";
		var lastToken = "nothing";
		
		// Utility closure. Parse and push the current literal on the operand
		// stack, if there is in fact a literal to push.
		function pushLiteralIfNeeded() {
			if (literal !== "") {
				// Check if the literal is a function.
				var symbol = literal.toLowerCase();
				var value = functions[symbol];
				
				// If it is a function, push it on the operators stack.
				if (value && value.func) {
					operators.push(value);
					lastToken = "function";
				} else {
					// Check if the literal is a constant.
					value = constants[symbol];
					
					// If it wasn't a constant, see if it is a variable.
					if (variables && typeof value !== "number") {
						value = variables[symbol];
					}
					
					// If it's none of the above, treat it as a numeric literal.
					if (typeof value !== "number") {
						// Parse the literal.
						value = parseFloat(literal);
						
						// Check if there was a formatting error.
						if (isNaN(value)) {
							throw "unknown quantity '" + literal + "'";
						}
					}
					
					// Push the value on the operand stack.
					operands.push(value);
					lastToken = "operand";
				}
				
				// Reset the literal.
				literal = "";
			}
		}
		
		// Make sure that the parameter is actually a string.
		expression = expression.toString();
		
		// Parse the expression.
		for (var i = 0; i < expression.length; ++i) {
			var ch = expression.charAt(i);
			var op = characters[ch];
			
			if (typeof op === "undefined") {
				// Found a digit, decimal point, or other numeric element.
				if (!ch.match(/^\s+$/)) {
					// If it isn't whitespace, append it to the literal.
					literal += ch;
				} else {
					// If it is whitespace, try to push the existing literal.
					pushLiteralIfNeeded();
				}
			} else {
				// Found an operator. Push the current literal if needed.
				pushLiteralIfNeeded();
				
				if (op.unary === "prefix" && lastToken !== "operand") {
					// We're using the prefix form of this operator, which is
					// defined as having an implicit leading 0.
					operands.push(0);
				} else if (typeof op.precedence === "number") {
					// Account for precedence, if this is a "real" operator.
					// Unary operators never force the evaluation of other
					// operators on the stack.
					while (shouldPopForPrecedence(op, operators)) {
						evaluateOperator(operators, operands);
					}
				}
				
				if (op.parenthesis !== "right") {
					// Push the operator.
					operators.push(op);
					
					if (op.unary === "postfix") {
						// Evaluate postfix operators immediately.
						evaluateOperator(operators, operands);
						
						// The last token, for the purposes of prefix operators,
						// is an operand.
						lastToken = "operand";
					} else {
						// The last token is an operator.
						lastToken = "operator";
					}
				} else {
					// Right parenthesis.
					while (shouldPopTowardsLeftParenthesis(operators)) {
						evaluateOperator(operators, operands);
					}
					
					// Make sure that the stack isn't suddenly empty.
					if (operators.length === 0) {
						throw "mismatched parenthesis";
					}
					
					// Otherwise, pop the left parenthesis.
					operators.pop();
					
					// If the current last token is a function, call it.
					evaluateFunctionIfNeeded(operators, operands);
					
					// The last token, for the purposes of prefix operators,
					// is an operand.
					lastToken = "operand";
				}
			}
		}
		
		// Push the current literal if needed.
		pushLiteralIfNeeded();
		
		// Evaluate the remaining operators.
		while (operators.length > 0) {
			evaluateOperator(operators, operands);
		}
		
		// Make sure there's exactly one result.
		if (operands.length !== 1) {
			throw "syntax error";
		}
		
		// Final answer!
		return checkResult(operands[0]);
	};
}());