// Chap 6, pp 275 - 280
// *********************************************************
// INFIX TO POSTFIX CONVERSION
// Input: One legal infix expression, which contains at
// most 30 characters and no embedded blanks,
// on one line of input.
// Output: The given infix expression and the equivalent
// postfix expression.
// Assumptions:
// 1. The input string is a legal infix expression,
// which can contain parentheses.
// 2. Only the binary operators +, -, *, / are allowed.
// 3. Every character that is not an operator or a
// parenthesis is a legal operand.
// 4. The class stackClass for a stack of characters
// is available.
// *********************************************************
#include
#include "StackP.cpp" // stack operations
#include // string operations
const int MAX_STRING = 30;
typedef char expressionType[MAX_STRING+1];
// categories of characters
enum category {Operand, Operator, OpenParen, CloseParen};
void ConvToPost(const char IEin[], char PEout[])
// --------------------------------------------------------
// Converts an infix expression to postfix form.
// Precondition: The input expression IEin is a string
// that represents a legal infix expression where:
// Operators are +, -, *, or /.
// Open and close parentheses are permitted.
// All other characters are operands.
// Postcondition: PEout is the equivalent postfix
// expression.
// Calls: TypeOfChar, ProcessOperand, ProcessCloseParen,
// ProcessOperator, and stack operations.
// --------------------------------------------------------
{
stackClass S;
char Ch, Top;
boolean Success;
// headers for functions that this function calls:
category TypeOfChar(char);
void ProcessOperand(char, char[]);
void ProcessCloseParen(stackClass&, char[]);
void ProcessOperator(stackClass&, char, char[]);
// prepare for conversion
strcpy(PEout,""); // output string is empty
// process each character in the input expression
for (int I = 0; I < strlen(IEin); ++I)
{ Ch = IEin[I];
switch (TypeOfChar(Ch))
{ // operand - concatenate to the output string
case Operand:
ProcessOperand(Ch, PEout);
break;
// open paren - push onto the stack
case OpenParen:
S.Push(Ch, Success);
break;
// close paren - pop operators, appending
// them to output string, until a matching
// open paren is found
case CloseParen:
ProcessCloseParen(S, PEout);
break;
// operator - pop operators of >= precedence
case Operator:
ProcessOperator(S, Ch, PEout);
} // end switch
} // end for
// move the rest of the stack to the output string
while (!S.StackIsEmpty())
{ S.GetStackTop(Top, Success);
S.Pop(Success);
strncat(PEout, &Top, 1); // concatenate
} // end while
} // end ConvToPost
int Prec(char Op)
// --------------------------------------------------------
// Computes the precedence of an operator.
// Precondition: Op is an operator.
// Postcondition: Returns 1 for + and -, 2 for * and /,
// and 0 for any other character.
// --------------------------------------------------------
{
enum precedence {LOWEST, MID, HIGHEST};
switch (Op)
{ case '+': case '-' :
return MID;
case '*': case '/' :
return HIGHEST;
default :
return LOWEST;
} // end switch
} // end Prec
category TypeOfChar(char Ch)
// --------------------------------------------------------
// Categorizes a character.
// Precondition: Ch is a legal character.
// Postcondition: Returns a value (Operand, Operator,
// OpenParen, CloseParen) according to the category of the
// character Ch.
// --------------------------------------------------------
{
switch (Ch)
{ case '+': case '-': case '*': case '/' :
return Operator;
case '(':
return OpenParen;
case ')':
return CloseParen;
default :
return Operand;
} // end switch
} // end TypeOfChar
void ProcessOperand(char Ch, char PEout[])
// --------------------------------------------------------
// Processes operands.
// Precondition: Ch is an operand. PEout is either empty
// or contains the first part of the postfix expression.
// Postcondition: Operand Ch is appended to the end of the
// postfix expression PEout.
// --------------------------------------------------------
{
strncat(PEout, &Ch, 1); // concatenate
} // end ProcessOperand
void ProcessCloseParen(stackClass& S, char PEout[])
// --------------------------------------------------------
// Processes right parentheses.
// Precondition: Stack S is not empty.
// Postcondition: Pops operators from stack S and appends
// them to the end of the postfix expression PEout until a
// matching open paren is found.
// Calls: Stack operations.
// --------------------------------------------------------
{
char Top;
boolean Success;
S.GetStackTop(Top, Success);
while (Top != '(')
{ strncat(PEout, &Top, 1); // concatenate
S.Pop(Success);
S.GetStackTop(Top, Success);
} // end while
S.Pop(Success);
} // end ProcessCloseParen
void ProcessOperator(stackClass& S, char Ch, char PEout[])
// --------------------------------------------------------
// Processes operators.
// Precondition: Stack S is not empty. Ch is an operator;
// PEout is either empty or contains the first part of
// the postfix expression.
// Postcondition: Pops operators from stack S whose
// precedence is >= present operator Ch and appends them
// to the end of the postfix expression PEout.
// Calls: Stack operations.
// --------------------------------------------------------
{
char Top;
boolean Success;
boolean Done = FALSE;
while (!S.StackIsEmpty() && !Done)
{ S.GetStackTop(Top, Success);
if ( (Top != '(') && (Prec(Top) >= Prec(Ch)) )
{ strncat(PEout, &Top, 1); // concatenate
S.Pop(Success);
}
else
Done = TRUE;
} // end while
S.Push(Ch, Success);
} // end ProcessOperator
void ReadExpr(char IEin[], int ExprLength)
// --------------------------------------------------------
// Reads an expression from standard input.
// Precondition: Exprlength is the maximum desired
// expression length.
// Postcondition: IEin contains the expression.
// --------------------------------------------------------
{
cout << "Enter infix expression of no more than "
<< ExprLength << " characters:\n";
cin.getline(IEin, ExprLength+1);
} // end ReadExpr
main() // demonstrate function ConvToPost
{
expressionType IEin; // infix expression - input
expressionType PEout; // postfix expression - output
cout << "Enter QUIT instead of an expression "
<< "to exit program.\n";
ReadExpr(IEin, MAX_STRING); // read infix expression
while (strcmp(IEin, "QUIT"))
{ ConvToPost(IEin, PEout); // convert to postfix form
// write out the infix and postfix expressions
cout << "\nInfix expression: " << IEin << "\n"
<< "\nPostfix expression: " << PEout << "\n";
ReadExpr(IEin, MAX_STRING); // read infix expression
} // end while
cout << "Done.\n";
return 0;
} // end main
(
geocities.com/siliconvalley/program/2864/ds) (
geocities.com/siliconvalley/program/2864) (
geocities.com/siliconvalley/program) (
geocities.com/siliconvalley)