Postfix Evaluator [Archive] - CodingForums.com

premshree

09-03-2002, 06:41 PM

This JavaScript evaluates a Postfix(Postorder) expression.

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


<script language="JavaScript">
/*
Postfix Evaluator
- Evaluates a Postfix(Postorder) expression
- For eg. '12*3+' results in 5
- Valid Operators are +,-,*,/
JavaScript Implementation
- © 2002 Premshree Pillai
See algorithm at
- http://www.qiksearch.com/articles/cs/postfix-evaluation/index.htm
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 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();
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>


<center><span class="header">Postfix Evaluator</span></center>


<center>
<form name="input_form">
<table class="form_in" cellspacing="0" cellpadding="3">
<tr bgcolor="#0066CC">
<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 :</font></td>
<td></td>
</tr>
<tr>
<td><input type="text" name="postfixVal" class="text_box" value=""></td>
<td><input type="text" name="resultVal" class="text_box" value=""></td>
<td align="bottom"><input type="button" onClick="document.input_form.resultVal.value=PostfixEval(document.input_form.postfixVal.value)" value="Evaluate Postfix" class="button"></td>
</tr>
</table>
</form>
</center>


<table width="485" align="center"><tr><td>
<font face="verdana,arial,helvetica" size="-1" color="#000000">
This JavaScript evaluates a Postfix(Postorder) expression.
<br><br><a href="http://www.qiksearch.com/articles/cs/postfix-evaluation/index.htm" class="link">Click here</a> for the algorithm used.
<hr style="color:#003366; height:1px">
© 2002 <a href="http://www.qiksearch.com" class="link" title="Click here to visit Qiksearch.com">Premshree Pillai</a>.
</font>
</td></tr></table>

</body>
</html>

:thumbsup:

beetle

09-06-2002, 05:29 PM

Cool, but what do you use Postfix for, anyhow?

premshree

09-06-2002, 08:54 PM

Well, this is more of a concept.

Here's one example :
Consider the built-in eval() function in JavaScript. Using eval(), you can evaluate any math expression. One way, the function could be implemented is converting that expression(Infix) --> Postfix expression--> Postfix Evaluation.

:thumbsup:

premshree

09-06-2002, 08:57 PM

Also see this post :

http://www.codingforums.com/showthread.php?threadid=5692

Its like "Eval without eval()"

:thumbsup:

beetle

09-06-2002, 09:58 PM

I think I see. But eval() is for more than just Math.

I'm still struggling to see a real-world application. (Got a tangible example?)

joh6nn

09-07-2002, 04:27 AM

yeah. i'm definitely not seeing a use for this.

premshree

09-07-2002, 07:48 AM

Yes, eval() is more than just for evaluating math expressions. I just used it as an example of where Postfix evaluation could be used.

As I said this is very fundamental to programming. It is how computer systems evaluate math expressions. This method of evaluating a math expression by first converting it to Postfix and then evaluating the Postfix expression was described by D.E Knuth in 1962. In JavaScript, you have the eval() function built-in. What if you don't have such a function in some other language?

I just wanted to implement the algorithm using JavaScript.

One example where it could be used is in evaluation of derivatives of any function.

What's more important is the algorithm and it definitely has *lots of use*

beetle

09-07-2002, 09:14 AM

I can see how having functions to handle heavy arithmetic are useful, but I don't really picture a case where somone would 1) need to use such functions and 2) would choose Javascript over many languages that are much better suited for the task (Why not use the algorithm in PHP or Java or something?)

I'm sure the computer's method for converting 1+2+3 to Postfix takes less CPU time than a client-side function run via the browser, so I doubt there's a speed advantage in 'preparing' the expression for the javascript engine.

I'm not trying to put you or the script down Premshree (it appears to work wonderfully), I just really don't know how this function would be useful to anyone coding w/Javascript, except maybe to help them in a math class or something (Don't some advanced arithmetic calculators use stacks?) But for a true web application? I just don't see it.

premshree

09-12-2002, 01:00 PM

Well, it would be more appropriate to use it in a server-side app since that's what ppl would normally use to create a good web-based app.

What I wanted to show was the JavaScript implementation of the algorithm. The algorithm holds more importance.

However, I wouldn't agree that it has no use to a person coding with JS.

jkd

09-12-2002, 04:08 PM

Kind of reminds me of False (http://wouter.fov120.com/false/index.html) :)