Tuesday, October 20, 2009

Converting Infix Expression to Postfix

This is a pseudocode of the program that can covert an Infix expression to postfix expression. The same pseudocode is given in your course book as well, but I have written it in a way that it is more understandable. The code has a precedence() function that returns true or false, depending on the precedence of the operators. so if it is precedence('*', '+'), it will return true and also true for precedence('*', '*'). You must keep in mind that for precedence('$', '$'), the return value is false.

Get expression from user //Say A*B+C or A+B*C$D$E
initialize operatorStack as empty //A stack for only storing operators +,-,*,/,$
initialize postfixString //The created postfix string

char Symbol;
char topSymbol;

//While loop will run till the end is reached
while(!endOfExpression())
{
Symbol = getCharacterFromExpression()
if(SymbolIsOperand())
{
add Symbol to postfixString;
}
else
{
while(!operatorStack.isEmpty() && precedance(operatorStack.getTop(), Symbol))
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}
operatorStack.push(Symbol);
}
}

while(!operatorStack.isEmpty())
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}

No comments:

Post a Comment