Infix to Prefix Conversion


3. Convert Infix Expression to Prefix Expression

Problem:

Given an infix expression, output the expression in Prefix (Polish Notation) form.

For e.g.

Solution:

This implementation is done using C#.NET.

ALGORITHM:

This algorithm maintains two stacks. 1st stack for all operators and 2nd stack to store the operands.

1)  Validate the Infix Expression for correctness

a) ‘(‘ and ‘)’ are in pairs

b) Operator is in between 2 operands (Binary operators are considered only)

2)  If Infix Expression is Valid then

a)  Push ‘(‘ to Operator Stack and Append ‘)’ to Infix Expression

b)  Scan each character in the Infix expression

i)  If scanned character is ‘(‘

Then

Push it to Operator Stack

ii)  Else If scanned character is ‘)’

Then

(a)  Repeat the below steps until ‘(‘ is popped out from Operator Stack

(b)  Pop from Operator Stack into OPERATOR

(c)  If OPERATOR  != ‘(‘

(i)  Pop twice from Operand Stack into OPERAND2 and OPERAND1

(ii)  Push “OPERATOR OPERAND1 OPERAND2” in Operand Stack

iii)  Else If scanned character is an Operator

Then

(a) Repeat the below steps until Operator having low precedence than  Scanned character is popped out from Operator Stack

(b) Pop from Operator Stack into OPERATOR

(c)  If OPERATOR  has Higher or Equal Precedence than scanned character

(i)  Pop twice from Operand Stack into OPERAND2 and OPERAND1

(ii)  Push “OPERATOR OPERAND1 OPERAND2” in Operand Stack

(d) Otherwise,

(i) Push the last Popped operator back in Operator Stack

(ii) Push the scanned character in Operator Stack

iv) Otherwise, Scanned character is an operand. Thus, Push it in Operand Stack

c) Pop from Operand Stack which is the final expression and return;


public void ConvertInfixToPrefix(string infixExpression)
{

try
{

ValidateInfixExpression(ref infixExpression);

}
catch (Exception ex)
{

Console.WriteLine("Invalid infix expression. Error Details:{0}", ex.Message);
return null;

}

Stack<char> operatorStack = new Stack<char>();
Stack<string> operandStack = new Stack<string>();

operatorStack.Push('(');
infixExpression += ')';

foreach (char ch in infixExpression)
{

if (ch == '(')
{

operatorStack.Push(ch);

}
else if (ch == ')')
{

// Pop from operator Stack until '(' is encountered
char poppedOperator = operatorStack.Pop();

while (poppedOperator != '(')
{

operandStack.Push(PrefixExpressionBuilder(operandStack, poppedOperator));

poppedOperator = operatorStack.Pop();

}

}
else if (IsOperator(ch))
{

// Pop all operators from Operator Stack which have same or higher precedence
char poppedOperator = operatorStack.Pop();

bool sameOrHighPrecedence = CheckSameOrHighPrecedence(poppedOperator, ch);

while (sameOrHighPrecedence)
{

operandStack.Push(PrefixExpressionBuilder(operandStack, poppedOperator));

poppedOperator = operatorStack.Pop();

sameOrHighPrecedence = CheckSameOrHighPrecedence(poppedOperator, ch);

}

operatorStack.Push(poppedOperator);

operatorStack.Push(ch);

}
else
{

operandStack.Push(ch.ToString());

}

}

return operandStack.Pop();

}

/// <summary>
/// Validates the infix expression for correctness
/// </summary>
/// <param name="expression">Infix expression to be validated</param>
/// <returns>True if expression is valid</returns>
private static void ValidateInfixExpression(ref string expression)
{

expression = expression.Replace(" ", string.Empty);
// Rule 1: '(' and ')' pair
// Rule 2: Every two operands must have one operator in between

}

/// <summary>
/// Checks if character is a listed operator or not
/// </summary>
/// <param name="character">Charaxter to be tested</param>
/// <returns>False if not otherwise True</returns>
private static bool IsOperator(char character)
{

if ((character == '+') || (character == '-') || (character == '*') || (character == '/'))
{
  return true;
}

return false;

}

/// <summary>
/// Checks if popped operator has same or higher precedence than Current operator
/// </summary>
/// <param name="elementToTest">Popped operator</param>
/// <param name="checkAgainst">Current operator in the expression</param>
/// <returns>True if equal or higher precedence</returns>
private static bool CheckSameOrHighPrecedence(char elementToTest, char checkAgainst)
{

bool flag = false;

switch (elementToTest)
{

case '/':
case  '*':

flag = true;
break;

case '+':
case '-':

if ((checkAgainst == '+') || (checkAgainst == '-'))
{

flag = true;

}
break;

default: // for any other popped element

flag = false;
break;

}

return flag;

}

private static string PrefixExpressionBuilder(Stack<string> operandStack, char operatorChar)
{

string operand2 = operandStack.Pop();
string operand1 = operandStack.Pop();

string infixExpression = string.Format("{0}{1}{2}", operatorChar, operand1, operand2);

return infixExpression;

}

Advertisements

About Sunil Singhal

A human being whose dreams are tied to a Horse that will never tire
This entry was posted in Algorithms and tagged , , , , , , , , . Bookmark the permalink.

11 Responses to Infix to Prefix Conversion

  1. Thanks, it was rather educative. I’ve pasted it into visual studio and everything works correct.

    Like

  2. Aditya says:

    This algorithm is completely messed up how you can commute when you encounter an operand and an operator from operand stack.e.g. take expression ((5+2)*3) then it’s prefix form should be (*3+52) =21.
    while this algorithm will give(*+352)=16

    Like

  3. MO Na says:

    can you please explain me 3rd example of infix to prefix?? please

    Like

  4. The algorithm seems to be wrong. The solution is generated in the operandstack. Now look at step 3 : You pop always the 2 operands from the top of the operandstack and push it back with an operator in prefix mode. How does this solution ever provide any operator to end up on the bottom of the operandstack – its just a simple a prefix swapping on the stack top to my eyes!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s