Geeks With Blogs
Venky's Tech Writings

Algorithm for Infix to Postfix

One of the applications of stack is in the evaluation of arithmetic expressions. To evaluate any arithmetic expression we convert the infix expression to postfix. Then evaluate the postfix expression using a stack. In this article I would define the standard algorithm for this.

Define a stack
Go through each character in the string
If it is between 0 to 9, append it to output string.
If it is left brace push to stack
If it is operator *+-/ then
          If the stack is empty push it to the stack
          If the stack is not empty then start a loop:
                             If the top of the stack has higher precedence
                             Then pop and append to output string
                             Else break
                     Push to the stack

If it is right brace then
            While stack not empty and top not equal to left brace
            Pop from stack and append to output string
            Finally pop out the left brace.

If there is any input in the stack pop and append to the output string.

Here is the code for conversion from infix to postfix.

public static string ConvertInfixToPostfix(string infix)

{

    int length = infix.Length;

    Stack<char> stack = new Stack<char>();

    StringBuilder postfix = new StringBuilder();

 

    for (int i = 0; i < length; i++)

    {

        if ((infix[i] >= '0') && (infix[i] <= '9'))

        {

            postfix.Append(infix[i]);

        }

        else if (infix[i] == '(')

        {

            stack.Push(infix[i]);

        }

        else if ((infix[i] == '*') || (infix[i] == '+') || (infix[i] == '-') || (infix[i] == '/'))

        {

            while ((stack.Count > 0) && (stack.Peek() != '('))

            {

                if (ComparePrecedence(stack.Peek(), infix[i]))

                {

                    postfix.Append(stack.Pop());

                }

                else

                {

                    break;

                }

            }

            stack.Push(infix[i]);

        }

        else if (infix[i] == ')')

        {

            while ((stack.Count > 0) && (stack.Peek() != '('))

            {

                postfix.Append(stack.Pop());

            }

            if (stack.Count > 0)

                stack.Pop(); // popping out the left brace '('

        }

        else

        {

        }

    }

    while (stack.Count > 0)

    {

        postfix.Append(stack.Pop());

    }

    return postfix.ToString();

}

 

private static bool ComparePrecedence(char top, char p_2)

{

    if (top == '+' && p_2 == '*') // + has lower precedence than *

        return false;

 

    if (top == '*' && p_2 == '-') // * has higher precedence over -

        return true;

 

    if (top == '+' && p_2 == '-') // + has same precedence over +

        return true;

 

    return true;

}

 

public static int EvaluatePostFix(string postfix)

{

    Stack<int> resultStack = new Stack<int>();

    int length = postfix.Length;

    for (int i = 0; i < length; i++)

    {

        if ((postfix[i] == '*') || (postfix[i] == '+') || (postfix[i] == '-') || (postfix[i] == ''))

        {

            int result = ApplyOperator(resultStack.Pop(), resultStack.Pop(), postfix[i]);

            resultStack.Push(result);

        }

        else if ((postfix[i] >= '0') || (postfix[i] <= '9'))

        {

            resultStack.Push((int)(postfix[i] - '0'));

        }

        else

        {

        }

    }

    return resultStack.Pop();

}

 

private static int ApplyOperator(int p, int p_2, char p_3)

{

    switch (p_3)

    {

        case '+':

            return p_2 + p;

        case '-':

            return p_2 - p;

        case '*':

            return p_2 * p;

        case '/':

            return p_2 / p;

        default:

            return -1;

    }

    return -1;

}

 

 

Posted on Friday, July 9, 2010 9:02 AM | Back to top


Comments on this post: Algorithm for Infix to Postfix

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
i have a project similar to this, i am just wondring can you help me. i have a problem?
Left by soofi on Dec 01, 2010 4:02 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
hi.. can you give me a correct program in converting infix expression to postfix expression using string?? example is. infix: 1+2----> postfix: 12+..
thanks
Left by wyeth on Feb 02, 2011 1:27 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
Is there an algorithm or a ideal code for infix to postfix
Can you publish a code to rewrite a polynomial in
postfix

Thank you (It's a very useful website)
Left by Wesam .Nm on Mar 06, 2011 2:59 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
thank you for every thing
you solved all my problems
I love your site
Left by Nahid on Mar 08, 2011 1:36 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
boosting up the knowledge.
Left by komal on Aug 17, 2011 10:06 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
nice..keep up the good work
Left by mary ann abaring on Sep 01, 2011 11:43 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
thank you very much for your effort
Left by Mohammad walid on Nov 02, 2011 9:03 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
Thanks so much! I was trying to understand my textbook version of this and it was NOT clear! Thanks for a really thorough explanation!
Left by Shana on Nov 10, 2011 6:00 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
hi. can u give me a algo and program for infix to prefix in c without using pointer
Left by vivek on Feb 04, 2012 10:40 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
Thank you very much for this gem.
Your algorithm as well as the java program guided me with my PHP version. Thank you!
Left by Troy on Mar 18, 2012 7:23 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
SUPER ALGORITHM
Left by ranjith on May 25, 2012 1:39 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
babal ka algo hai lekin lga hai?????????
Left by manish on Sep 15, 2012 6:01 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
i think there is some problem in the algo. as the postfix string is not having ')'.
Left by Rishabh on Oct 01, 2012 8:54 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
where is the main class????
Left by AHED on Nov 10, 2012 10:00 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
char globalArr[100];
int count = 0;

int _tmain(int argc, _TCHAR* argv[])
{
char x[] = "a+(b-c*d)^e-f^g^(h/!i*k)";
Infix_To_Prefix(x,strlen(x));
for(int i = 0; i < count; i++)
cout<<globalArr[i];
cout<<endl;
return 0;
}

int Priority(char ch)
{
char opArr[] = {'(','!','^','*','/','+','-'};
int prioArr[] = {10,9,8,7,7,6,6};
for(int i = 0; i < strlen(opArr); i++)
{
if(opArr[i] == ch)
return prioArr[i];
}
return -1;
}

void Infix_To_Prefix(char a[],int length)
{
char poped;
for(int i = 0; i < length; i++)
{
if(a[i] >= 'a' && a[i] <= 'z')
globalArr[count++] = a[i];
else if(a[i] == ')')
{
poped = CStack::Pop();
while(poped != '(')
{
globalArr[count++] = poped;
poped = CStack::Pop();
}
}
else
{
if(CStack::Top() == NULL || Priority(a[i]) > Priority(CStack::Top()) || CStack::Top() == '(')
CStack::Push(a[i]);
else
{

while(!(Priority(a[i]) > Priority(CStack::Top())) && CStack::Top() != '(')
{
poped = CStack::Pop();
globalArr[count++] = poped;
}
CStack::Push(a[i]);
}
}
}
while(CStack::Top() != NULL)
{
poped = CStack::Pop();
globalArr[count++] = poped;
}
}
Left by Pooria on Nov 22, 2012 10:31 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
yow wazap azik
Left by spangka on Jan 05, 2013 6:32 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
i want to change infix to postfix
Left by desta tekle on Jan 08, 2013 7:18 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
the output of our question program is like this
A+B
token stack output
A - A
+ + A
B + AB+
how can we make it a program ??
Left by ian on Feb 07, 2013 10:18 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
how can i cr8 a program of postfix to infix with a comment ???
Left by alberto lim on Feb 11, 2013 9:24 AM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
i want to full code infix to postfixes.
there have first class Stack.
function have int operand(){
int operator(char op){
void priority(){
.
Left by MD RONY on Mar 24, 2013 6:53 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
This algorithm doesn't work correctly; the operator precedence is not preserved as it should be:

For example: 4+6/2+8*3 should correctly evaluate to 31 with the expected output as: 462/83*++ whereas this implementation produces the result of: 46+2/83*+ evaluating to a total of 23.

Left by Steve on Jul 01, 2013 8:30 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
FYI: The fault lies in the ComparePrecedence() method which fails to account for all the evaluation rules. For example given the operators * and / the method should return false (because * has a lower precedence than /) but this method will return true causing evaluation errors.
Left by Steve on Jul 01, 2013 8:55 PM

# re: Algorithm for Infix to Postfix
Requesting Gravatar...
im jazper guzman im web tech in UC and im an IT student i am handsome AKA pogi and full of beutiful talent , you are useless
Left by jazper deguzman pogi on Mar 26, 2014 11:50 AM

Your comment:
 (will show your gravatar)
 


Copyright © venknar | Powered by: GeeksWithBlogs.net | Join free