1. Purpose

The purpose of this exercise is to make the students familiar with:

(1) the array based implementation of stack;

(2) the linked list based implementation of stack;

(3) the basic application of stack;


2. Grading Policy

（1） The full mark is 100, which is equivalent to 5 points in the final score of this course.

（2） The assessment is based on the correctness and quality of the code, the ability demonstrated in debugging and answering related questions raised by the lecturer and teaching assistants.

（3） The exercises should be completed individually and independently.

（4） Some reference codes are provided at the end of this document, only for the purpose of helping those students who really have difficulties in programing. It is allowed to use the reference codes. However, straight copy from the reference codes or with minor modification can only guarantee you to get a pass score. Therefore, the students are encouraged to write their own codes to get a higher score.


3. Contents of Exercises


3.1 Array Based Implementation of Stack


Exercise 4.1 (40 points)

Create a stack with some data elements, and finish such operations as initialization, Push, Pop, etc.

All operations should be implemented as independent functions, which can be called by the main function.

(1) Create a stack by entering some positive integer data elements, and end the process by entering -1, and output all the elements;

(2) Get the length of the stack;

(3) Delete a data element from the stack, and output the data value.


3.2 Linked List Based Implementation of Stack


Exercise 4.2 (30 points)

Create a stack with some data elements, and finish such operations as initialization, Push, Pop, etc.

All operations should be implemented as independent functions, which can be called by the main function.

(1) data elements, and end the process by entering -1, and output all the elements;

(2) Get the length of the stack

(3) Add a new data element into the stack;

(4) Delete a data element from the stack, and output the data value


3.3 Application of stack


Exercise 4.3 (10 points)

Write an algorithm to convert a non-negative decimal number to its equivalent octal number


Exercise 4.4(10 points)

Use letter I and O to represent PUSH and POP operation respectively. The initial state and end state of stack should both be empty, a sequence of PUSH and POP operation is represented by the sequence composed of I and O only. Such a sequence is legal only when it is operable, otherwise it is illegal. Write an algorithm to judge whether the following sequences are legal or not.

S1：I O O I I O I O O

S2：I O O I O I I O

S3：I I I O I O I O

S4：I I I O O I O O


Exercise 4.5 (10 points)

Write an program to receive a character string from the keyboard(the maximum length is 100),  and test whether the brackets ()，[]，{} in the string are matching.



4. Reference Code


Exercise 4.1



#include
#include
#include

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int SElemType;
typedef int Status;

// definition of array based stack
#define STACK_INIT_SIZE   100          //Initial size for memory allocation
#define STACKINCREMENT  10          //incremental size
typedef struct{
SElemType  *base;    //base pointer
SElemType  *top;      //top pointer
int        stacksize;     //current size
}SqStack;

//==========================================
// initialization of array-based stack
//===========================================
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

//========================================
//Test empty stack
//========================================
Status StackEmpty (SqStack S){
add some codes here
}

//===============================================
// Get the length of a stack
//==============================================
int StackLength (SqStack S){
add some codes here
}

//=====================================
// Get top item of a stack
//====================================
Status GetTop(SqStack S, SElemType &e){
add some codes here }

//===================================================
// Delete an item from the stack
//====================================================
Status Pop(SqStack &S,SElemType &e){
add some codes here }

//======================================
// Insert an item into the stack
//=======================================
Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize){      //stack is full, increase the size
S.base=(SElemType *)realloc(S.base,(S.stacksize+
STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
add some codes here
return OK;
}

//======================================
// Print the elements in a stack
//=======================================
void PrintStack (SqStack S){
SElemType *p;
printf(“\n the data element in the stack is\n”)
for(p=S.base; p




Exercise 4.2





#include
#include
#include

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

typedef int SElemType;
typedef int Status;

typedef struct L_node{
SElemType     data;  //data field
struct L_node  *next;   //pointer field
}LNode, *LinkList;

typedef struct{
LinkList  Head;  //head pointer
int  length;  //length
}LinkStack;

//==========================================
// initialization of linked list based stack
//===========================================
Status InitStack(LinkStack &S){
S.Head=(LinkList)malloc(sizeof(LNode));
if(!S.Head) return ERROR;
S.Head=NULL;
return OK;
}

//========================================
//Test empty stack
//========================================
Status StackEmpty (LinkStack S){
add some codes here
}

//===============================================
// Get the length of a stack
//==============================================
int StackLength (LinkStack S){
add some codes here

}

//=====================================
// Get top item of a stack
//====================================
Status GetTop(LinkStack S, SElemType &e){
if(S.Head->next==NULL) return ERROR;
add some codes here
}

//===================================================
// Delete an item from the stack
//====================================================
Status Pop(LinkStack &S, SElemType &e){
add some codes here
}

//======================================
// Insert an item into the stack
//=======================================
Status Push(LinkStack &S, SElemType e){
add some codes here
}

//======================================
// Print the elements in a stack
//=======================================
void PrintStack (LinkStack S){
LinkList p;
p=L->next;
printf(“\nThe elements of the stack are:”);
while(p){
printf(“%d,  ”, p->data) ;
p=p->next;
}
printf(“\n”);
}

int main()
{
LinkStack S1;
int e;
int len;

InitStack(S1);

printf(“please enter the data item\n”);
scanf(“%d”, &e)
while(e!=-1)
{
Push(S1, e);
scanf(“%d”, &e)
}

PrintStack(S1);

len=StackLength(S1);
printf(“the length of the stack is %d\n”, len);

Pop(S1, e);
printf(“the top element is %d\n”, e);

return OK;
}




Exercise 4.3



Note: reusable codes in Exercise 4.1 are not repeated here.





void Conversion (){
//for a non-negative decimal number, print out its equivalent octal number
SqStack S;
int N;
int e;

InitStack(S);
scanf("%d",N);

add some codes here

while(!StackEmpty(S)){
Pop(S, e);
printf("%d", e);
}
}

int main()
{
Conversion();
}

Exercise 4.4

Note: reusable codes in Exercise 4.1 are not repeated here.

typedef char SElemType;

Status JudgeLegal(char s[])
{
SqStack S;
char c;
char e;

InitStack(S);
for(i=0, c=s[i]; c!=’\0’; ++i, c=s[i])
{
add some codes here
}

if(StackEmpty (S)
return TURE;
else
return FALSE;

}


char S1[]=“IOOIIOIOO”;
char S2[]=“IOOIOIIO”;
char S3[]=” IIIOIOIO”;
char S4[]=” IIIOOIOO”;

int main()
{
if(JudgeLegal(S1)==TRUE)
printf(“the string %s is legal\n”, S1);
else
printf(“the string %s is illegal\n”, S1);

add some codes here

}


Exercise 4.5

Note: reusable codes in Exercise 4.1 are not repeated here.

typedef char SElemType;


Status BracketsMatching(char s[])
{
SqStack S;
char c;
char e;

InitStack(S);
for(i=0, c=s[i]; c!=’\0’; ++i, c=s[i])
{
if(c==’(’ || c==’[’ || c ==’{’)
Push(S, c);
elseif (c==’)’ || c==’]’ || c ==’}’)
{
add some codes here
}
}
}

int main()
{
char c;
char s[100];
int len=0;
c=getchar();
while(c!=’#’) // ‘#’ means the end of string
{
s[len++]=c;
c=getchar();
}
s[len]=’\0’;

if(BracketsMatching(s)==TRUE)
printf(“the brackets in the string are matching”);
else
printf(“the brackets in the string are not matching”);
}