
	ASP Shopping Cart, Forum & BBS - all for $20 from CodeToad Plus!

Home || ASP | ASP.Net | C++/C# | DHTML | HTML | Java | Javascript | Perl | VB | XML || CodeToad Plus! || RAM

Search Site:

Perl Infix~Postfix

Article by:

Premshree Pillai (9/22/2003)

	Add to Favourites
	Tell a friend

Summary:

This is the Perl implementation of converting an Infix expression to Postfix and vice-versa.

Viewed: 132185 times

Rating (256 votes):

4.7 out of 5

Rate this Article

Read Comments

Post Comments

Perl Infix~Postfix

This is the Perl implementation of converting an Infix expression to Postfix and vice-versa. First a bit of background info:

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression :

The Postfix(Postorder) form of the above expression is "23*45/-".

Infix to Postfix Conversion :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :

Scan the Infix string from left to right.
Initialise an empty stack.
If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.
- If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
Repeat this step till all the characters are scanned.
(After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
Return the Postfix string.

Example :

Let us see how the above algorithm will be imlemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack.

Stack

Postfix String

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack.

Stack

Postfix String

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.

Stack

Postfix String

Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :

Stack

Postfix String

End result :

Infix String : a+b*c-d
Postfix String : abc*+d-

Select All Code

#!/usr/bin/perl -T
#############################################################################
#
#    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.
#
############################################################################

use warnings;

print "Content-type: text/html\n\n";
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.html"><tr><td>';
print '<input type="text" name="expression" value="',$expression,'" class="ip" onClick="this.select();">';
print ' <select name="action"><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">',evalInfix($expression),'</span>';
        }
        print '</b>';
    }
}

print '<br><br><b>Algorithms used Â»</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 'Â© 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 "/index.html") || ($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 "/index.html"))
    {
        $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 "/index.html")
    {
        $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)));
}

Useful Links

CodeToad Experts

Can't find the answer?
Our Site experts are answering questions for free in the CodeToad forums

Rate this article: Poor Excellent

View highlighted Comments

User Comments on 'Perl Infix~Postfix '

Recent Forum Threads

•	Run a program both on windows and linux
•	VERO.SurfCAM.v2014
•	Schlumberger.Petrel.V2013.2
•	Petrel.V2013.2
•	Altair.HyperWorks.v12
•	VoluMill.v6.1
•	VoluMill.NEXION.6
•	VERO.SurfCAM.v2014
•	Schlumberger.Petrel.V2013.2

Recent Articles

	ASP GetTempName
	Decode and Encode UTF-8
	ASP GetFile
	ASP FolderExists
	ASP FileExists
	ASP OpenTextFile
	ASP FilesystemObject
	ASP CreateFolder
	ASP CreateTextFile
	Javascript Get Selected Text

privacy - contact - advertise - hot links - link to us - submit your article