...

View Full Version : Infix <> Postfix (Complete)



premshree
09-06-2002, 08:38 PM
This is the "JavaScript" Implementation of converting an Infix(Inorder) expression to Postfix(Postorder) expression and vice-versa. It also evaluates the Postfix expression.

The algorithm for converting Infix to Postfix :
http://www.qiksearch.com/articles/cs/infix-postfix/index.htm

The algorithm for Postfix evaluation :
http://www.qiksearch.com/articles/cs/postfix-evaluation/index.htm

Find it at :
http://www.qiksearch.com/javascripts/infix-postfix.htm

OR See attachment



<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Infix <> Postfix</title>
<style type="text/css">
.header{font-family:verdana,arial,helvetica; font-weight:bold; font-size:22pt; color:#003399; filter:DropShadow(color=#DDDDFF, offX=2, offY=2, positive=1); width:100%}
.form_in{background:#FCFCFF; border:#003399 solid 1px}
.text_box{font-weight:bold; background:#EFEFF5; border:#003399 solid 1px; height:20px}
.button{background:#DDDDEE; font-weight:bold; color:#003399; width:100%; height:22px; cursor:hand}
.link{color:#003399}
.link:hover{color:#0033FF}
</style>
</head>
<body bgcolor="#FFFFFF">

<!--BEGIN INFIX-POSTFIX JAVASCRIPT-->
<script language="JavaScript">
/*
Infix <> Postfix Conversion
- Converts an Infix(Inorder) expression to Postfix(Postorder) and vice-versa
- Valid Operators are +,-,*,/
JavaScript Implementation
- 2002 Premshree Pillai
Created : 03/08/02 (dd/mm/yy)
Web : http://www.qiksearch.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)? true : false);
}

function isOperator(who)
{
return((who=="+" || 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(char1,char2)
{
var char1_index,char2_index;
var _def_prcd="-+*/";
for(var i=0; i<_def_prcd.length; i++)
{
if(char1==_def_prcd.charAt(i)) char1_index=i;
if(char2==_def_prcd.charAt(i)) char2_index=i;
}
if(((char1_index==0)||(char1_index==1)) && (char2_index>1)) return false;
else return true;
}

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

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 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;
return(returnVal);
}

function PostfixEval(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=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));
}
</script>
<!--END INFIX-POSTFIX JAVASCRIPT-->

<center><span class="header">Infix &lt;&gt; Postfix</span></center>

<!--BEGIN FORM-->
<center>
<form name="input_form">
<table class="form_in" cellspacing="0" cellpadding="3">
<tr bgcolor="#003399">
<td><font face="verdana,arial,helvetica" size="-2" color="#FFFFFF">Infix Expression :</font></td>
<td><font face="verdana,arial,helvetica" size="-2" color="#FFFFFF">Postfix Expression :</font></td>
<td><font face="verdana,arial,helvetica" size="-2" color="#FFFFFF">Result (Postfix Eval) :</font></td>
</tr>
<tr>
<td><input type="text" name="infixVal" class="text_box" value=""></td>
<td><input type="text" name="postfixVal" class="text_box" value=""></td>
<td><input type="text" name="resultVal" class="text_box" value=""></td>
</tr>
<tr>
<td><input type="button" onClick="document.input_form.postfixVal.value=InfixToPostfix(document.input_form.infixVal.value,'arr');docume nt.input_form.resultVal.value=PostfixEval(document.input_form.postfixVal.value)" value="Infix to Postfix >>>" class="button"></td>
<td><input type="button" onClick="document.input_form.infixVal.value=PostfixToInfix(document.input_form.postfixVal.value);document.inp ut_form.resultVal.value=PostfixEval(document.input_form.postfixVal.value)" value="<<< Postfix to Infix" class="button"></td>
</tr>
</table>
</form>
</center>
<!--END FORM-->

</body>
</html>


:thumbsup:

premshree
09-15-2002, 12:02 PM
Just updated the "Infix~Postfix" JavaScript I had posted earlier.
Now, it supports parenthesis in the 'Infix Expression'.

Find it at :
http://www24.brinkster.com/premshree/infix-postfix/index.htm
OR see attachment.

:thumbsup:

premshree
09-25-2002, 09:14 AM
Just wrote 'Infix-Postfix' in Perl :
http://www24.brinkster.com/premshree/perl/infix-postfix.htm

:)

premshree
09-27-2002, 07:21 PM
Just got the Perl version of 'Infix~Postfix' working on the web (with some help from the Perl/CGI Forum) :)

Check it at :
http://qiksearch1.tripod.com/cgi-bin/infix-postfix.cgi

:thumbsup:

premshree
10-07-2002, 07:38 PM
Just modified the "Infix-Postfix" Parser.
Earlier, the parser would evaluate infix expression expressions with single digit. Now, you can evaluate expressions with numbers of any length.

I added a function strToTokens() that converts the expression and returns an array containing the tokens.

Here's the function :



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);
}


Check out the complete modified code here:
http://www24.brinkster.com/premshree/infix-postfix_mul.htm

:thumbsup:

premshree
10-24-2002, 08:38 AM
Just removed a minor bug in converting postfix to infix :

Here's the complete code :



<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Infix ~ Postfix</title>
<style type="text/css">
.header{font-family:verdana,arial,helvetica; font-weight:bold; font-size:22pt; color:#003399; filter:DropShadow(color=#DDDDFF, offX=2, offY=2, positive=1); width:100%}
.form_in{background:#FCFCFF; border:#003399 solid 1px}
.text_box{font-weight:bold; background:#EFEFF5; border:#003399 solid 1px; height:20px}
.button{background:#DDDDEE; font-weight:bold; color:#003399; width:100%; height:22px; cursor:hand}
.link{color:#003399}
.link:hover{color:#0033FF}
</style>
</head>
<body bgcolor="#FFFFFF">

<!--BEGIN INFIX-POSTFIX JAVASCRIPT-->
<script language="JavaScript">
/*
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
*/

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));
}
</script>
<!--END INFIX-POSTFIX JAVASCRIPT-->

<center><span class="header">Infix ~ Postfix</span></center>

<!--BEGIN FORM-->
<center>
<form name="input_form">
<table class="form_in" cellspacing="0" cellpadding="3">
<tr bgcolor="#003399">
<td><font face="verdana,arial,helvetica" size="-2" color="#FFFFFF">Infix Expression :</font></td>
<td><font face="verdana,arial,helvetica" size="-2" color="#FFFFFF">Postfix Expression :</font></td>
<td><font face="verdana,arial,helvetica" size="-2" color="#FFFFFF">Result (Postfix Eval) :</font></td>
</tr>
<tr>
<td><input type="text" name="infixVal" class="text_box" value=""></td>
<td><input type="text" name="postfixVal" class="text_box" value=""></td>
<td><input type="text" name="resultVal" class="text_box" value=""></td>
</tr>
<tr>
<td><input type="button" onClick="document.input_form.postfixVal.value=InfixToPostfix(document.input_form.infixVal.value,'arr',0);docu ment.input_form.resultVal.value=PostfixEval(InfixToPostfix(document.input_form.infixVal.value,'arr', 1))" value="Infix to Postfix >>>" class="button"></td>
<td><input type="button" onClick="document.input_form.infixVal.value=PostfixToInfix(document.input_form.postfixVal.value);document.inp ut_form.resultVal.value=PostfixEval(InfixToPostfix(document.input_form.infixVal.value,'arr',1))" value="<<< Postfix to Infix" class="button"></td>
</tr>
</table>
</form>
</center>
<!--END FORM-->

</body>
</html>



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum