infixToBinaryTreeSimple

infixToBinaryTreeSimple

function Stack() {
	this.stack = new Array();
}

Stack.prototype = {
	isEmpty: function() {
		return this.stack.length == 0;
	},

	pop: function() {
		return this.stack.pop();
	},

	peek: function() {
		return this.stack[this.stack.length - 1];
	},

	push: function(o) {
		this.stack.push(o);
	}
}

function Operator(t){
	this.sign = t;
	return this;
}

Operator.prototype = {
	lessPrecedentTo:function(o) {
		return this.value < o.value;
	}
}

var createOperator = function(t) {
	switch (t) {
		case '+': return new Plus(t);
		case '-': return new Minus(t);
		case '/': return new Divide(t);
		case '*': return new Multiply(t);
		default: return null;
	}
}

function Plus(t) {
	Operator.call(this, t);
	this.value = 0;
	this.applyFunction = function(arg1,arg2) {
		return arg1 + arg2;
	}
}

Plus.prototype = Object.create(Operator.prototype);

function Minus(t) {
	Operator.call(this, t);
	this.value = 0;
	this.applyFunction = function(arg1,arg2) {
		return arg1 - arg2;
	}
}

Minus.prototype = Object.create(Operator.prototype);

function Divide(t) {
	Operator.call(this, t);
	this.value = 1;
	this.applyFunction = function(arg1,arg2) {
		return arg1 / arg2;
	}
}

Divide.prototype = Object.create(Operator.prototype);

function Multiply(t) {
	Operator.call(this, t);
	this.value = 1;
	this.applyFunction = function(arg1,arg2) {
		return arg1 * arg2;
	}
}

Multiply.prototype = Object.create(Operator.prototype);

function BinaryTreeNode(d) {
	this.data = d;
	this.left = null;
	this.right = null;
}

var infixToBinaryTree = function(input) {
	var result = null,
		outputStack = new Stack(),
		operatorStack = new Stack(),
		flag = false;

	var createSubtree = function() {
		if (result == null) {
			result = new BinaryTreeNode(operatorStack.pop());
			result.right = new BinaryTreeNode(outputStack.pop());
			result.left = new BinaryTreeNode(outputStack.pop());
		} else {
			var subresult = result;
			result = new BinaryTreeNode(operatorStack.pop());
			child = new BinaryTreeNode(outputStack.pop());
			if (flag) {
				result.left = subresult;
				result.right = child;
			} else {
				result.left = child;
				result.right = subresult;	
			}

		}
	}

	for (var s in input) {
		var token = input[s];
		if (!isNaN(token)) 
			outputStack.push(parseInt(token));
		else if (token == '(') {
			operatorStack.push(token);
		} else if (token == ')') {
			while(operatorStack.peek() != '(') {
				createSubtree();
			}
			operatorStack.pop();
		} else {
			var operator = createOperator(token);
			while (!operatorStack.isEmpty() && operator.lessPrecedentTo(operatorStack.peek())) {
				flag=false;
				createSubtree();
				flag=true;
			}
			operatorStack.push(operator);
		}
	}

	while (!operatorStack.isEmpty()) {
		createSubtree();
		flag = false;
	}

	return result;
}

var evaluate = function(node) {
	var token = node.data;
	if (token instanceof Operator) {
		return token.applyFunction(evaluate(node.left), evaluate(node.right));
	} else {
		return node.data;
	}
}