/*
  Infix ~ Postfix Conversion
  - Converts an Infix(Inorder) expression to Postfix(Postorder) and vice-versa
  - Valid Operators are +,-,*,/,^,()
  - No Error Handling in this version
  JavaScript Implementation
  - © 2002 Premshree Pillai
  See algorithms at
  -http://www.qiksearch.com/articles/cs/infix-postfix/index.htm
  -http://www.qiksearch.com/articles/cs/postfix-evaluation/index.htm
  Created : 03/08/02 (dd/mm/yy)
  Modified : 23/10/02 (dd/mm/yy)
  Web : http://www.qiksearch.com
  E-mail : qiksearch@rediffmail.com
*/

function push_stack(stackArr,ele)
{
	stackArr[stackArr.length]=ele;
}

function pop_stack(stackArr)
{
	var _temp=stackArr[stackArr.length-1];
	delete stackArr[stackArr.length-1];
	stackArr.length--;
	return(_temp);
}

function isOperand(who)
{
	return((!isOperator(who) && (who!="(") && (who!=")"))? true : false);
}

function isOperator(who)
{
	return((who=="+" || who=="-" || who=="*" || who=="/" || who=="^")? true : false);
}

function topStack(stackArr)
{
	return(stackArr[stackArr.length-1]);
}

function isEmpty(stackArr)
{
	return((stackArr.length==0)? true : false);
}

/* Check for Precedence */
function prcd(who)
{
	if(who=="^")
		return(5);
	if((who=="*")||(who=="/"))
		return(4);
	if((who=="+")||(who=="-"))
		return(3);
	if(who=="(")
		return(2);
	if(who==")")
		return(1);
}

function InfixToPostfix(infixStr,postfixStr,retType)
{
	var postfixStr=new Array();
	var stackArr=new Array();
	var postfixPtr=0;
	infixStr=strToTokens(infixStr);
	for(var i=0; i<infixStr.length; i++)
	{
		if(isOperand(infixStr[i]))
		{
			postfixStr[postfixPtr]=infixStr[i];
			postfixPtr++;
		}
		if(isOperator(infixStr[i]))
		{
			if(infixStr[i]!="^")
			{
				while((!isEmpty(stackArr)) && (prcd(infixStr[i])<=prcd(topStack(stackArr))))
				{
					postfixStr[postfixPtr]=topStack(stackArr);
					pop_stack(stackArr);
					postfixPtr++;
				}
			}
			else
			{
				while((!isEmpty(stackArr)) && (prcd(infixStr[i])<prcd(topStack(stackArr))))
				{
					postfixStr[postfixPtr]=topStack(stackArr);
					pop_stack(stackArr);
					postfixPtr++;
				}
			}
			push_stack(stackArr,infixStr[i]);
		}
		if(infixStr[i]=="(")
			push_stack(stackArr,infixStr[i]);
		if(infixStr[i]==")")
		{
			while(topStack(stackArr)!="(")
			{
				postfixStr[postfixPtr]=pop_stack(stackArr);
				postfixPtr++;
			}
			pop_stack(stackArr);
		}
	}
	while(!isEmpty(stackArr))
	{
		if(topStack(stackArr)=="(")
			pop_stack(stackArr)
		else
			postfixStr[postfixStr.length]=pop_stack(stackArr);
	}
	var returnVal='';
	for(var i=0; i<postfixStr.length; i++)
	{
		returnVal+=postfixStr[i];
	}
	if(retType==0)
		return(returnVal);
	else
		return(postfixStr);
}

function PostfixToInfix(postfixStr)
{
	var stackArr=new Array();
	postfixStr=postfixStr.split('');
	for(var i=0; i<postfixStr.length; i++)
	{
		if(isOperand(postfixStr[i]))
			push_stack(stackArr,postfixStr[i]);
		else
		{
			var temp=topStack(stackArr);
			pop_stack(stackArr);
			var pushVal='('+topStack(stackArr)+postfixStr[i]+temp+')';
			pop_stack(stackArr);
			push_stack(stackArr,pushVal);
		}
	}
	return(topStack(stackArr));
}

function strToTokens(str)
{
	var strArr=str.split("");
	var tempStr=new String("");	
	var tokens=new Array();
	var tokens_index=0;
	for(var i=0; i<strArr.length; i++)
	{
		if(isOperand(strArr[i]))
		{
			tempStr+=strArr[i];
		}
		if(isOperator(strArr[i]) || strArr[i]==")" || strArr[i]=="(")
		{
			if(tempStr!="")
			{
				tokens[tokens_index]=tempStr;
				tokens_index++;
			}
			tempStr="";
			tokens[tokens_index]=strArr[i];
			tokens_index++;
		}
		if(i==strArr.length-1)
			if(tempStr!="")
				tokens[tokens_index]=tempStr;
	}
	return(tokens);
}

function PostfixSubEval(num1,num2,sym)
{
	var returnVal;
	if(sym=="+")
		returnVal=num1+num2;
	if(sym=="-")
		returnVal=num1-num2;
	if(sym=="*")
		returnVal=num1*num2;
	if(sym=="/")
		returnVal=num1/num2;
	if(sym=="^")
		returnVal=Math.pow(num1,num2);
	return(returnVal);
}

function PostfixEval(postfixStr)
{
	var stackArr=new Array();
	for(var i=0; i<postfixStr.length; i++)
	{
		if(isOperand(postfixStr[i]))
			push_stack(stackArr,postfixStr[i]);
		else
		{
			var temp=parseFloat(topStack(stackArr));
			pop_stack(stackArr);
			var pushVal=PostfixSubEval(parseFloat(topStack(stackArr)),temp,postfixStr[i]);
			pop_stack(stackArr);
			push_stack(stackArr,pushVal);
		}
	}
	return(topStack(stackArr));
}