Home     Mosaic     CLIP     Octave     R Project     Processing     Contact  
Search
<http://cnfolio.com/IntroComputingPractical12>
Introduction to Computing – B142L

B142L Computing practical – Stack data structures

Academic year 2009/10


Learning outcomes

  1. Become familiar with the concept of stacks as a data structures.
  2. Practice implementation of C structures and enumerations.
  3. Practice using pseudo code and D structures to document program design.



Concept of a stack


A stack is a data structure to hold one or more items such that the last item added is the first item taken out. The effect is that the most recently added item is always at the very top. A common acronym for this property is Last In First Out (LIFO).

There are 2 operations that define the behaviour of a stack:

Main stack operations



Helper functions for a stack


These 2 operations help make it easier to use a stack:

Helper stack operations



Basic implementation of a stack


The following source code is a basic implementation of a stack with a fixed size. In the example, the stack size is fixed to 15.

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE  15

struct stack
{
   int     currentStackSize;
   double  currentStackItems[ MAX_STACK_SIZE ];
};

struct stack numbers;  /* Stack currently in use by program */

void    push( double );  /* Adds a number to the top of the stack */
double  pop();  /* Remove a number from the top of the stack */
double  top();  /* Look at the number currently at the top of the stack */
int     size();  /* Count the numbers currently in the stack */


int main( void )
{
/* Add your source code here */
}


void push( double input )
{
   if ( numbers.currentStackSize >= MAX_STACK_SIZE ) return;

   numbers.currentStackItems[ numbers.currentStackSize ] = input;
   numbers.currentStackSize++;
}

double pop()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   numbers.currentStackSize--;
   return numbers.currentStackItems[ numbers.currentStackSize ];
}

double top()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   return numbers.currentStackItems[ numbers.currentStackSize - 1 ];
}

int size()
{
   return numbers.currentStackSize;
}




Incremental program to push and pop 4 numbers


Following is source code for the main() function of a program which provides a partial solution for Exercise 1. The stack functions are still required outside of the main() function.

int main( void )
{
   double input;
   int counter = 0;

   do
   {   
      scanf( "%lf", &input );
      push( input );
      counter++;
   }
   while( counter < 4 );
   
   printf( "Done reading\n" );

   counter = 0;
   do
   {   
      printf( "Saved: %.2lf", pop() );
      counter++;
   } while ( counter < 4 );
}




Incremental program that stops when a specific character is found


Following is source code for the main() function of a program which provides a partial solution for all the exercises. The stack functions are still required outside of the main() function.

int main( void )
{
   double input;
   char   text[ 64 ];

   do
   {   
      scanf( "%s", text );

      if ( text[ 0 ] == '.' )
      {
          break;
      }
 
      input = strtod( text, NULL );
      push( input );
   }
   while( 1 );
   
   printf( "Done reading\n" );
}




Exercise 1: Reverse numbers


Write a program that:
  1. Accepts input numbers. Use double as the data type to match the stack data type.
  2. Store the numbers into the stack.
  3. Stops reading input numbers when it finds a period by itself, e.g. .
  4. When the input ends, then read back and display all the numbers currently in the stack.

The program above will reverse the order of the input numbers.

For example, if the input is:
5 3.0 2 1 .


The output display would be:
1.00 2.00 3.00 5.00

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE  15

struct stack
{
   int     currentStackSize;
   double  currentStackItems[ MAX_STACK_SIZE ];
};

struct stack numbers;  /* Stack currently in use by program */

void    push( double );  /* Adds a number to the top of the stack */
double  pop();  /* Remove a number from the top of the stack */
double  top();  /* Look at the number currently at the top of the stack */
int     size();  /* Count the numbers currently in the stack */


int main( void )
{
   char token[ 64 ];
   char operator;
   double result = 0.0;

   do
   {
      scanf( "%s", token );
      operator = token[ 0 ];
      
      if ( operator == '.' )
         break;

      push( strtod( token, NULL ) );
   } while ( 1 );

   while ( size() > 0 )
      printf( "%.2lf ", pop() );
}


void push( double input )
{
   if ( numbers.currentStackSize >= MAX_STACK_SIZE ) return;

   numbers.currentStackItems[ numbers.currentStackSize ] = input;
   numbers.currentStackSize++;
}

double pop()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   numbers.currentStackSize--;
   return numbers.currentStackItems[ numbers.currentStackSize ];
}

double top()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   return numbers.currentStackItems[ numbers.currentStackSize - 1 ];
}

int size()
{
   return numbers.currentStackSize;
}



Exercise 2: Calculator for addition operation using Postfix notation


The stack data structure is ideal for implementing a calculator using Postfix notation, which does not require the use of parentheses. This format is also called Reverse Polish Notation (RPN). Read the description here:

Write a program that:
  1. Accepts input numbers and the addition operator. Use double as the data type to match the stack data type.
  2. Performs addition calculations as received from the standard input.
  3. Stops reading input numbers when it finds a period by itself, e.g. .
  4. When the input ends, then display the result of the calculations.

The function strtod() will be useful for writing the program:

For example, if the input is:
5 3.0 + .


The output display would be:
8.00

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE  15

struct stack
{
   int     currentStackSize;
   double  currentStackItems[ MAX_STACK_SIZE ];
};

struct stack numbers;  /* Stack currently in use by program */

void    push( double );  /* Adds a number to the top of the stack */
double  pop();  /* Remove a number from the top of the stack */
double  top();  /* Look at the number currently at the top of the stack */
int     size();  /* Count the numbers currently in the stack */


int main( void )
{
   char token[ 64 ];
   char operator;
   double operand1, operand2, sum, result = 0.0;
   
   do
   {
      scanf( "%s", token );
      operator = token[ 0 ];
      
      if ( operator == '.' )
      {
         result = top();
         break;
      }
      
      if ( operator == '+' )
      {
         operand2 = pop();
         operand1 = pop();
         sum = operand1 + operand2;
         push( sum );
         continue;
      }
      
      push( strtod( token, NULL ) );
   } while ( 1 );
   
   printf( "The result is %.2lf", result );
}


void push( double input )
{
   if ( numbers.currentStackSize >= MAX_STACK_SIZE ) return;

   numbers.currentStackItems[ numbers.currentStackSize ] = input;
   numbers.currentStackSize++;
}

double pop()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   numbers.currentStackSize--;
   return numbers.currentStackItems[ numbers.currentStackSize ];
}

double top()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   return numbers.currentStackItems[ numbers.currentStackSize - 1 ];
}

int size()
{
   return numbers.currentStackSize;
}



Exercise 3: Calculator using Postfix notation with 4 basic operations


Add source code to the program from Exercise 2 for implementing the remaining basic algebraic operations:

Be careful about the order of the operands!

For example, if the input is:
5 1 2 + 4 * + 3 - .


The output display would be:
-14.00

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE  15

struct stack
{
   int     currentStackSize;
   double  currentStackItems[ MAX_STACK_SIZE ];
};

struct stack numbers;  /* Stack currently in use by program */

void    push( double );  /* Adds a number to the top of the stack */
double  pop();  /* Remove a number from the top of the stack */
double  top();  /* Look at the number currently at the top of the stack */
int     size();  /* Count the numbers currently in the stack */


int main( void )
{
   char token[ 64 ];
   char operator;
   double operand1, operand2, result, calculation = 0.0;
   
   do
   {
      scanf( "%s", token );
      operator = token[ 0 ];
      
      if ( operator == '.' )
      {
         calculation = top();
         break;
      }
      
      if ( operator == '+' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 + operand2;
         push( result );
         continue;
      }
      
      if ( operator == '-' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 - operand2;
         push( result );
         continue;
      }

      if ( operator == '*' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 * operand2;
         push( result );
         continue;
      }

      if ( operator == '/' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 / operand2;
         push( result );
         continue;
      }

      push( strtod( token, NULL ) );
   } while ( 1 );
   
   printf( "The result is %.2lf", result );
}


void push( double input )
{
   if ( numbers.currentStackSize >= MAX_STACK_SIZE ) return;

   numbers.currentStackItems[ numbers.currentStackSize ] = input;
   numbers.currentStackSize++;
}

double pop()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   numbers.currentStackSize--;
   return numbers.currentStackItems[ numbers.currentStackSize ];
}

double top()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   return numbers.currentStackItems[ numbers.currentStackSize - 1 ];
}

int size()
{
   return numbers.currentStackSize;
}



Optional challenge problem: Advanced operations for calculator using Postfix notation


Add source code to the program from Exercise 3 for implementing these operations:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_STACK_SIZE  15

struct stack
{
   int     currentStackSize;
   double  currentStackItems[ MAX_STACK_SIZE ];
};

struct stack numbers;  /* Stack currently in use by program */

void    push( double );  /* Adds a number to the top of the stack */
double  pop();  /* Remove a number from the top of the stack */
double  top();  /* Look at the number currently at the top of the stack */
int     size();  /* Count the numbers currently in the stack */


int main( void )
{
   char token[ 64 ];
   char operator;
   double operand1, operand2, result, calculation = 0.0;
   long iOperand1, iOperand2, iResult;
   
   do
   {
      scanf( "%s", token );
      operator = token[ 0 ];
      
      if ( operator == '.' )
      {
         calculation = top();
         break;
      }
      
      if ( operator == '+' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 + operand2;
         push( result );
         continue;
      }
      
      if ( operator == '-' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 - operand2;
         push( result );
         continue;
      }

      if ( operator == '*' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 * operand2;
         push( result );
         continue;
      }

      if ( operator == '/' )
      {
         operand1 = pop();
         operand2 = pop();
         result = operand1 / operand2;
         push( result );
         continue;
      }

      if ( operator == '%' )
      {
         iOperand1 = (long) pop();
         iOperand2 = (long) pop();
         iResult = iOperand1 % iOperand2;
             result = (double) iResult;
         push( result );
         continue;
      }

      if ( operator == '^' )
      {
         operand1 = pop();
         operand2 = pop();
         result = pow( operand1, operand2 );
         push( result );
         continue;
      }

      push( strtod( token, NULL ) );
   } while ( 1 );
   
   printf( "The result is %.2lf", result );
}


void push( double input )
{
   if ( numbers.currentStackSize >= MAX_STACK_SIZE ) return;

   numbers.currentStackItems[ numbers.currentStackSize ] = input;
   numbers.currentStackSize++;
}

double pop()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   numbers.currentStackSize--;
   return numbers.currentStackItems[ numbers.currentStackSize ];
}

double top()
{
   if ( numbers.currentStackSize < 1 ) return 0.0;
   
   return numbers.currentStackItems[ numbers.currentStackSize - 1 ];
}

int size()
{
   return numbers.currentStackSize;
}
This website uses wikkawiki.org software.