p.81 3.19
Write a program to evaluate a postfix expression.
/* declarations for this problem only */
#define Max_Elements 100 /* maximum stack size */
#define Max_Expr 100 /*max size of expression */
typedef enum { plus, minus, times, divide, power, eos, operand } Precedence;
/* declarations and implementations for a standard stack are omitted */
/* Convert a string to ElementType. The implementation is omitted */
ElementType ConvertToElementType( char *opr_str );
/* Check the next token in the given expression */
Precedence GetToken( ElementType *opr, int *cnt, char *expr );
ElementType EvalPostfix( char *expr )
{
/* Evaluate a postfix expression, expr, maintained as a string.
There is exactly one space between any two operators or operands.
GetToken is used to get the token type and, if the token is
an operand, the operand. */
Stack S = CreateStack( Max_Elements ); /* initialize a stack */
Precedence token;
ElementType opr, op1, op2; /* operands */
int cnt = 0; /* counter for the expression string */
token = GetToken( &opr, &cnt, expr );
while ( token != eos ) {
if ( token == operand )
Push( opr, S );
else {
/* remove two operands */
op2 = TopAndPop( S );
op1 = TopAndPop( S );
/* perform operation and return result to the stack */
switch ( token ) {
case plus: Push( op1 + op2, S ); break;
case minus: Push( op1 − op2, S ); break;
case times: Push( op1 * op2, S ); break;
case divide: Push( op1 / op2, S ); break;
case power: Push( pow( op1, op2 ), S ); break;
} /* end - switch */
} /* end - else */
评论2