#############################################################################
#
#	Script:		infix-postfix.pl
#	Author:		Premshree Pillai
#	Description:	Using this script you can :
#			- Convert an Infix expression to Postfix
#			- Convert a Postfix expression to Infix
#			- Evaluate a Postfix expression
#			- Evaluate an Infix expression
#	Web:		http://www.qiksearch.com
#	E-mail:		qiksearch@rediffmail.com
#	Created:	23/09/02 (dd/mm/yy)
#
#	� 2002 Premshree Pillai. All rights reserved.
#
############################################################################

sub init
{
	@string=split(/&/,$ENV{QUERY_STRING});
	@exp=split(/=/,$string[0]);
	$expression=$exp[1];
	# Convert the HTML encoding
	$expression =~ tr/+/ /;
	$expression =~ s/%([a-fA-F0-9][a-fA-F0-9])/pack("C", hex($1))/eg;
	$expression =~ s/<!--(.|\n)*-->//g;
	# Convert HTML stuff as necessary.
	$expression =~ s/<([^>]|\n)*>//g;
	@act=split(/=/,$string[1]);
	$action=$act[1];
}
init();

print '<html><head><title>Infix-Postfix</title>';
print '<style type="text/css">';
print '.header{font-family:Courier New,Times New Roman,verdana,arial,helvetica; font-size:30pt; font-weight:bold; font-style:italic}';
print '.main{border:#000000 solid 1px; background:#EEEEEE}';
print '.ip{border:#000000 solid 1px; height:22px}';
print '.slct{border:#000000 solid 1px; height:22px}';
print '.btn{border:#000000 solid 1px; height:22px; cursor:hand}';
print '.op{font-family:verdana,arial,helvetica; font-size:10pt; font-weight:bold; background:#EEEEEE; border:#000000 solid 1px; padding:3px}';
print '.content{font-family:verdana,arial,helvetica; font-size:10pt}';
print '.link{font-family:verdana,arial,helvetica; font-size:8pt; color:#000000}';
print '.link:hover{font-family:verdana,arial,helvetica; font-size:8pt; color:#666666}';
print '</style>';
print '</head><body bgcolor="#FFFFFF">';
print '<table align="center"><tr><td>';
print '<span class="header">Infix-Postfix</span><table><tr><td></td></tr></table>';
print '<table class="main"><form method="get" action="infix-postfix.pl"><tr><td>';
print '<input type="text" name="expression" value="',$expression,'" class="ip" onClick="this.select();">';
print ' <select name="action" class="slct"><option value="0">Infix to Postfix</option><option value="1">Postfix to Infix</option><option value="2">Evaluate Postfix</option><option value="3">Evaluate Infix</option></select>';
print ' <input type="submit" class="btn">';
print '</td></tr></form></table><br>';

print '<script languge="JavaScript">document.forms[0].action.selectedIndex="',$action,'";</script>';

print '<span class="content">';

if(($exp[0] ne 'expression') || ($act[0] ne 'action'))
{
	print "<i>Please use the above form!</i>";
}
else
{
	if(!(($action eq '0') || ($action eq '1') || ($action eq '2') || ($action eq '3')))
	{
		print "<i>Invalid Argument for Action";
	}
	else
	{
		print '<b>';
		if($action eq '0')
		{
			print 'Postfix Expression : <span class="op">',InfixToPostfix($expression),'</span>';
		}
		if($action eq '1')
		{
			print 'Infix Expression : <span class="op">',PostfixToInfix($expression),'</span>';
		}
		if($action eq '2')
		{
			print 'Postfix Eval : <span class="op">',PostfixEval($expression),'</span>';
		}
		if($action eq '3')
		{
			print 'Infix Eval : <span class="op">',eval($expression),'</span>';
		}
		print '</b>';
	}
}

print '<br><br><b>Algorithms used &raquo;</b><ul type="square"><li><a href="http://www.qiksearch.com/articles/cs/infix-postfix/index.htm" class="link">Infix to Postfix Conversion</a></li><li><a href="http://www.qiksearch.com/articles/cs/postfix-evaluation/index.htm" class="link">Postfix Evaluation</a></li></ul>';
print '&#169; 2002 Premshree Pillai.';
print '<br><a href="http://pub.alxnet.com/guestbook?id=2395118" class="link">Sign my Guestbook</a> | <a href="http://www.qiksearch.com" class="link">Qiksearch.com</a>';
print '</span>';
print '</td></tr></table>';
print '</body></html>';

sub isOperand
{
	($who)=@_;
	if((!isOperator($who)) && ($who ne "(") && ($who ne ")"))
	{
		return 1;
	}
	else
	{
		return;
	}
}

sub isOperator
{
	($who)=@_;
	if(($who eq "+") || ($who eq "-") || ($who eq "*") || ($who eq "/") || ($who eq "^"))
	{
		return 1;
	}
	else
	{
		return;
	}
}

sub topStack
{
	(@arr)=@_;
	my $arr_len=@arr;
	return($arr[$arr_len-1]);
}

sub isEmpty
{
	(@arr)=@_;
	my $arr_len=@arr;
	if(($arr_len)==0)
	{
		return 1;
	}
	else
	{
		return;
	}
}

sub prcd
{
	($who)=@_;
	my $retVal;
	if($who eq "^")
	{
		$retVal="5";
	}
	elsif(($who eq "*") || ($who eq "/"))
	{
		$retVal="4";
	}
	elsif(($who eq "+") || ($who eq "-"))
	{
		$retVal="3";
	}
	elsif($who eq "(")
	{
		$retVal="2";
	}
	else
	{
		$retVal="1";
	}
	return($retVal);
}

sub genArr
{
	($who)=@_;
	my @whoArr;
	for($i=0; $i<length($who); $i++)
	{
		$whoArr[$i]=substr($who,$i,1);
	}
	return(@whoArr);
}

sub InfixToPostfix
{
	($infixStr)=@_;
	my @infixArr=genArr($infixStr);
	my @postfixArr;
	my @stackArr;
	my $postfixPtr=0;
	for($i=0; $i<length($infixStr); $i++)
	{
		if(isOperand($infixArr[$i]))
		{
			$postfixArr[$postfixPtr]=$infixArr[$i];
			$postfixPtr++;
		}
		if(isOperator($infixArr[$i]))
		{
			if($infixArr[$i] ne "^")
			{
				while((!isEmpty(@stackArr)) && (prcd($infixArr[$i])<=prcd(topStack(@stackArr))))
				{
					$postfixArr[$postfixPtr]=topStack(@stackArr);
					pop(@stackArr);
					$postfixPtr++;
				}
			}
			else
			{
				while((!isEmpty(@stackArr)) && (prcd($infixArr[$i])<prcd(topStack(@stackArr))))
				{
					$postfixArr[$postfixPtr]=topStack(@stackArr);
					pop(@stackArr);
					$postfixPtr++;
				}
			}
			push(@stackArr,$infixArr[$i]);
		}
		if($infixArr[$i] eq "(")
		{
			push(@stackArr,$infixArr[$i])
		}
		if($infixArr[$i] eq ")")
		{
			while(topStack(@stackArr) ne "(")
			{
				$postfixArr[$postfixPtr]=pop(@stackArr);
				$postfixPtr++;
			}
			pop(@stackArr);
		}
	}
	while(!isEmpty(@stackArr))
	{
		if(topStack(@stackArr) eq "(")
		{
			pop(@stackArr)
		}
		else
		{
			$temp=@postfixArr;
			$postfixArr[$temp]=pop(@stackArr);
		}
	}
	return(@postfixArr);
}

sub PostfixToInfix
{
	($postfixStr)=@_;
	my @stackArr;
	my @postfixArr=genArr($postfixStr);
	for($i=0; $i<length($postfixStr); $i++)
	{
		if(isOperand($postfixArr[$i]))
		{
			push(@stackArr,$postfixArr[$i]);
		}
		else
		{
			$temp=topStack(@stackArr);
			pop(@stackArr);
			$pushVal=topStack(@stackArr).$postfixArr[$i].$temp;
			pop(@stackArr);
			push(@stackArr,$pushVal);
		}
	}
	return((@stackArr));
}

sub PostfixEval
{
	($postfixStr)=@_;
	my @stackArr;
	my @postfixArr=genArr($postfixStr);
	for($i=0; $i<length($postfixStr); $i++)
	{
		if(isOperand($postfixArr[$i]))
		{
			push(@stackArr,$postfixArr[$i]);
		}
		else
		{
			$temp=topStack(@stackArr);
			pop(@stackArr);
			$pushVal=PostfixSubEval(topStack(@stackArr),$temp,$postfixArr[$i]);
			pop(@stackArr);
			push(@stackArr,$pushVal);
		}
	}
	return(topStack(@stackArr));
}

sub PostfixSubEval
{
	($num1,$num2,$sym)=@_;
	my $returnVal;
	if($sym eq "+")
	{
		$returnVal=$num1+$num2;
	}
	if($sym eq "-")
	{
		$returnVal=$num1-$num2;
	}
	if($sym eq "*")
	{
		$returnVal=$num1*$num2;
	}
	if($sym eq "/")
	{
		$returnVal=$num1/$num2;
	}
	if($sym eq "^")
	{
		$returnVal=$num1**$num2;
	}
	return($returnVal);
}

sub joinArr
{
	(@who)=@_;
	my $who_len=@who;
	my $retVal;
	for($i=0; $i<$who_len; $i++)
	{
		$retVal.=$who[$i];
	}
	return $retVal;
}

sub evalInfix
{
	($exp)=@_;
	return PostfixEval(joinArr(InfixToPostfix($exp)));
}