CS1101C Lab 4 (Even Week)

Postfix Stack Arithmetic

The name of your C program file must be called postfix.c, files with any other name will not be marked.

Preliminary

Stack Data Structure

There are two main operations for the stack, namely push and pop. We can push an item to the top of the stack; this is like placing a tray on the top of the stack of trays. We can also pop an item from the top of the stack; this is like taking the top tray from the top of the stack of trays. In this lab, you will realize a stack for storing integers. Since there is no stack data structure readily available, we shall implement one using an array. The details of the implementation is left to the individual student. You can design the stack in anyway you wish, as long as you adhere to the specifications of the following four functions.

int isEmpty(int stack[]);

void printStack(int stack[]);

{ [top item] [next item] ... [bottom item] }

{ }

void pushStack(int stack[], int item);

int popStack(int stack[]);

#include <limits.h>

#define EMPTY INT_MIN

Testing your functions

You should test that the above functions work before carrying on to the next part. A sample main method is given below.

#include <stdio.h>
#include <limits.h>

#define MAX 100
#define EMPTY INT_MIN

/* Function prototypes and function definitions skipped... */

int main(void)
{
   //Declare your stack array.

   printf("\nPrint the initial stack...\n");
   printStack(stack);

   printf("\nPush 50 onto the stack...\n");
   pushStack(stack,50);
   printStack(stack);

   printf("\nPush -60 onto the stack...\n");
   pushStack(stack,-60);
   printStack(stack);

   printf("\nPop from the stack...%d\n", popStack(stack));
   printStack(stack);

   printf("\nPush 70 onto the stack...\n");
   pushStack(stack,70);
   printStack(stack);

   printf("\nPop from the stack...%d\n", popStack(stack));
   printStack(stack);

   printf("\nPop from the stack...%d\n", popStack(stack));
   printStack(stack);

   printf("\nPop from the stack...%d\n", popStack(stack));
   printStack(stack);
}

The output of the above main function is given below.

Print the initial stack...
{ }

Push 50 onto the stack...
{ [50] }

Push -60 onto the stack...
{ [-60] [50] }

Pop from the stack...-60
{ [50] }

Push 70 onto the stack...
{ [70] [50] }

Pop from the stack...70
{ [50] }

Pop from the stack...50
{ }

Pop from the stack...-2147483648
{ }

Postfix Expression Evaluation

It is very common to write mathematical expressions as infix expressions where parentheses are vital to ensure the ordering of various operations. Examples of infix expressions are 4*3 and (4*3)+(5-2). However, parenthesis can be removed if we rewrite the above using postfix expressions. For the above example, the postfix expressions are 4 3 * and 4 3 * 5 2 - + respectively. Here you will need to use your deductive and inference skills again to determine how valid postfix expressions can be written.

Postfix expression evaluation can be implemented using a stack. An example is given for the expression 4 3 * 5 2 - +.

1. Push 4 onto the stack.
   Stack contents: { [4] }
2. Push 3 onto the stack.
   Stack contents: { [3] [4] }
3. Since * involves two operands, pop the top two values out of the stack, perform the multiplication and push the result 12 onto the stack.
   Stack contents: { [12] }
4. Push 5 onto the stack.
   Stack contents: { [5] [12] }
5. Push 2 onto the stack.
   Stack contents: { [2] [5] [12] }
6. Since - involves two operands, pop the top two values out of the stack, perform the subtraction and push the result 3 onto the stack.
   Stack contents: { [3] [12] }
7. Since + involves two operands, pop the top two values out of the stack, perform the addition and push the result 15 onto the stack.
   Stack contents: { [15] }

Your task is to write a function postfix that takes in a stack data structure and a character string containing the expression to be evaluated and return the answer. The prototype of the postfix function is given below

int postfix(int stack[], char *str);

int postfix(int stack[], char str[]);

• Addition operator: +
• Subtraction operator: -
• Multiplication operator: *
• Division operator: /
• Modulus operator: %
• Unary minus operator: ~

The following main method is provided for you in which the user will repeatedly enter a postfix expression (a valid expression can include blank spaces) for evaluation. The program terminates only if the user enters an expression starting with a 'q' or 'Q'. Do not modify the main method.

int main(void)
{
   //Declare your stack array.
   char str[100] = {'\0'};

   printf("Enter a postfix expression: ");
   fgets(str, 100, stdin);
   while (tolower(*str) != 'q')  // uses ctype function tolower
   {
      printf("The answer is %d.\n\n", postfix(stack,str));
      printf("Enter a postfix expression: ");
      fgets(str, 100, stdin);
   }

   return 0;
}

Sample Run

A sample run of the program is as follows.

$ gcc -Wall postfix.c -o postfix
$ ./postfix
Enter a postfix expression: 43*
The answer is 12.

Enter a postfix expression: 4 3 * 5 2 - +
The answer is 15.

Enter a postfix expression: 43*         52 -+
The answer is 15.

Enter a postfix expression: 8 5 * 2 + ~ 5 ~ /
The answer is 8.

Enter a postfix expression: 85*2+~5~/
The answer is 8.

Enter a postfix expression: 96%2%
The answer is 1.

Enter a postfix expression: Quit.

$

Note and Ponder

1. Assume that all user input is valid. No error checking is required.

2. Assume that division by zero error will not occur.

3. To print the % symbol, use the %% format specifier in your printf statement.

4. If your program does not work as you expect (logical errors), use extra printf statements to print out all the values of your variables to aid in your debugging.

5. Most importantly, have lots of fun programming!

A total of 27 different hosts have accessed this document in the last 445 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 8 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.