CS13002 Programming and Data Structures, Spring 2002--2003
(SECTION 1/A)

LAB TEST 3 -- Solutions

[ODD]    [EVEN]

For students with odd PC numbers

The program

#include <stdio.h>
#include <string.h>

#define MAXLEN 256

typedef struct {
   char element[MAXLEN][MAXLEN];
   int tos;
} stack;

void init ( stack *S )
{
   (*S).tos = -1;
}

void push ( stack *S , char *a )
{
   if (++(*S).tos == MAXLEN) {
      fprintf(stderr, "Error in push : Stack overflow...\n");
      exit(1);
   }
   strcpy((*S).element[(*S).tos],a);
}

void pop ( stack *S , char *a )
{
   if ((*S).tos < 0) {
      fprintf(stderr, "Error in pop : Stack underflow...\n");
      exit(1);
   }
   strcpy(a,(*S).element[(*S).tos]);
   (*S).tos--;
}

int isOperator ( char c )
{
   if ( (c=='+') || (c == '-') || (c == '*') || (c == '/') || (c == '%') )
      return(1);
   return(0);
}

void evaluate ( char expr[] )
{
   int i;
   stack S;
   char operand1[MAXLEN], operand2[MAXLEN], result[MAXLEN];

   init(&S);
   for (i=strlen(expr)-1;i>=0;i--) {
      if (isOperator(expr[i])) {
         pop(&S,operand1);
         pop(&S,operand2);
         sprintf(result,"(%s%c%s)",operand1,expr[i],operand2);
      } else sprintf(result,"%c",expr[i]);
      push(&S,result);
   }
   if (S.tos != 0) {
      fprintf(stderr, "Error in evaluate: ill-formed expression...\n");
      exit(1);
   }
   printf("The infix notation for this expression is :\n%s\n",S.element[0]);
}

int main ()
{
   char expr[MAXLEN];

   printf("Input an arithmetic expression in prefix notation :\n");
   scanf("%s",expr);
   evaluate(expr);
}

The output

Input an arithmetic expression in prefix notation :
+*5+*5+*5+*5+*5UVWXYZ
The infix notation for this expression is :
((5*((5*((5*((5*((5*U)+V))+W))+X))+Y))+Z)

Input an arithmetic expression in prefix notation :
/++*ac*bd*i-*bc*ad+*cc*dd
The infix notation for this expression is :
((((a*c)+(b*d))+(i*((b*c)-(a*d))))/((c*c)+(d*d)))

Input an arithmetic expression in prefix notation :
+++++abcd---efg**hi/jk
Error in pop : Stack underflow...

Input an arithmetic expression in prefix notation :
/ab**cde---fghi++++jklmn
Error in evaluate: ill-formed expression...

Input an arithmetic expression in prefix notation :
+a/1+b/1+c/1+d/1+e/1+f/1+h/1+i/1+j/1+k/1l
The infix notation for this expression is :
(a+(1/(b+(1/(c+(1/(d+(1/(e+(1/(f+(1/(h+(1/(i+(1/(j+(1/(k+(1/l))))))))))))))))))))

For students with even PC numbers

The program

#include <stdio.h>
#include <string.h>

#define MAXLEN 256

typedef struct {
   char element[MAXLEN][MAXLEN];
   int tos;
} stack;

void init ( stack *S )
{
   (*S).tos = -1;
}

void push ( stack *S , char *a )
{
   if (++(*S).tos == MAXLEN) {
      fprintf(stderr, "Error in push : Stack overflow...\n");
      exit(1);
   }
   strcpy((*S).element[(*S).tos],a);
}

void pop ( stack *S , char *a )
{
   if ((*S).tos < 0) {
      fprintf(stderr, "Error in pop : Stack underflow...\n");
      exit(1);
   }
   strcpy(a,(*S).element[(*S).tos]);
   (*S).tos--;
}

int isOperator ( char c )
{
   if ( (c=='+') || (c == '-') || (c == '*') || (c == '/') || (c == '%') )
      return(1);
   return(0);
}

void evaluate ( char expr[] )
{
   int i,l;
   stack S;
   char operand1[MAXLEN], operand2[MAXLEN], result[MAXLEN];

   init(&S);
   l = strlen(expr);
   for (i=0;i<l;i++) {
      if (isOperator(expr[i])) {
         pop(&S,operand2);
         pop(&S,operand1);
         sprintf(result,"(%s%c%s)",operand1,expr[i],operand2);
      } else sprintf(result,"%c",expr[i]);
      push(&S,result);
   }
   if (S.tos != 0) {
      fprintf(stderr, "Error in evaluate: ill-formed expression...\n");
      exit(1);
   }
   printf("The infix notation for this expression is :\n%s\n",S.element[0]);
}

int main ()
{
   char expr[MAXLEN];

   printf("Input an arithmetic expression in postfix notation :\n");
   scanf("%s",expr);
   evaluate(expr);
}

The output

Input an arithmetic expression in postfix notation :
77777a*b+*c+*d+*e+*f+
The infix notation for this expression is :
((7*((7*((7*((7*((7*a)+b))+c))+d))+e))+f)

Input an arithmetic expression in postfix notation :
AC*BD*+IBC*AD*-*+CC*DD*+/
The infix notation for this expression is :
((((A*C)+(B*D))+(I*((B*C)-(A*D))))/((C*C)+(D*D)))

Input an arithmetic expression in postfix notation :
abcde++++fghi---jkl**mn/
Error in evaluate: ill-formed expression...

Input an arithmetic expression in postfix notation :
ab/cd**efg---hijk+++++
Error in pop : Stack underflow...

Input an arithmetic expression in postfix notation :
a1b1c1d1e1f1g1h1j1k1l/+/+/+/+/+/+/+/+/+/+
The infix notation for this expression is :
(a+(1/(b+(1/(c+(1/(d+(1/(e+(1/(f+(1/(g+(1/(h+(1/(j+(1/(k+(1/l))))))))))))))))))))

[Course home] [Home]