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;

}

Your comment:
Title:
Name:
Comment: *Allowed tags: blockquote, a, strong, em, p, u, strike, super, sub, code*

thanks

Can you publish a code to rewrite a polynomial in

postfix

Thank you (It's a very useful website)

you solved all my problems

I love your site

Your algorithm as well as the java program guided me with my PHP version. Thank you!

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;

}

}

A+B

token stack output

A - A

+ + A

B + AB+

how can we make it a program ??

there have first class Stack.

function have int operand(){

int operator(char op){

void priority(){

.

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.