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