stack.c

C语言编写的栈操作模板。包含栈的9种基本操作

/*********
 *                  A Template of Stack
 *
 * - Create stack using an array
 * - All safe check are commented. Uncomment if you need
 *
 *                                     -- Copyright (C) =iEDi=
 **************************************************************/

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

#define EmptyTOS -1
#define MinStackSize 5

struct StackRecord;
typedef struct StackRecord *Stack;

////// Declare your own element's type here //////
typedef char ElementType;
//////////////////////////////////////////////////

struct StackRecord
{
	int Capacity;
	int TopOfStack;
	ElementType *Array;
};

int IsEmpty(Stack S);
int IsFull(Stack S);
void MakeEmpty(Stack S);
Stack CreateStack(int MaxElements);
void FreeStack(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);

/* Return true if S is empty */
int IsEmpty(Stack S)
{
	return S->TopOfStack == EmptyTOS;
}

/* Return true if S is full */
int IsFull(Stack S)
{
	return S->TopOfStack >= (S->Capacity - 1);
}

/* Initialize stack S */
void MakeEmpty(Stack S)
{
	S->TopOfStack = EmptyTOS;
}

/* Create a stack */
Stack CreateStack(int MaxElements)
{
	Stack S;

//	if(MaxElements < MinStackSize)
//		printf("Error: Stack size is too small\n");

	S = malloc(sizeof(struct StackRecord));
	/***** Error Handler ******/
//	if(S == NULL)
//		printf("Runtime Error: Out of memory!\n");

	S->Array = malloc(sizeof(ElementType) * MaxElements);
	/***** Error Handler ******/
//	if(S->Array == NULL)
//		printf("Runtime Error: Out of memory!\n");

	S->Capacity = MaxElements;
	MakeEmpty(S);

	return S;
}

/* Delete stack S */
void FreeStack(Stack S)
{
	if (S != NULL) {
		free(S->Array);
		free(S);
	}
}

void Push(ElementType X, Stack S)
{
//	if(IsFull(S))
//		printf("Error: Stack Full!\n");
//	else
	S->Array[++S->TopOfStack] = X;
}

ElementType Top(Stack S)
{
//	if(!IsEmpty(S))
	return S->Array[S->TopOfStack];
//	printf("Error: Stack Empty!\n");
//	return -1;	// return value used to avoid warning
}

void Pop(Stack S)
{
//	if(IsEmpty(S))
//		printf("Error: Stack Empty!\n");
//	else
	S->TopOfStack--;
}

ElementType TopAndPop(Stack S)
{
//	if(!IsEmpty(S))
	return S->Array[S->TopOfStack--];
//	printf("Error: Stack Empty!\n");
//	return -1;	// return value used to avoid warning
}



/******************** Sample Code ********************/
// This sample scans if {, [, (, ), ], } are in right order.

int main()
{
	Stack S;	// declare a stack
	char c, popc;
	int mark_yes;
//	int mark_in;

	mark_yes = 1;	// we assume it in right order firstly
//	mark_in = 0;	// we will check if input contains any of {, [, (, ), ], }
	S = CreateStack(1000);

	while ((c = getchar()) != '\n') {
		if (c == '{' || c == '[' || c == '(') {
//			mark_in = 1;
			Push(c, S);
		} else if (c == '}' || c == ']' || c == ')') {
//			mark_in = 1;
			if (IsEmpty(S)) {
				mark_yes = 0;
				break;
			} else {
				popc = TopAndPop(S);
				if ((c == '}' && popc != '{') ||
				        (c == ']' && popc != '[') ||
				        (c == ')' && popc != '(')
				   ) {
					mark_yes = 0;
					break;
				}
			}
		}
	}

//	if (mark_in == 0) {
//		printf("Your input is not expected.\n");
//		return 0;
//	}
	if (mark_yes == 0 || !IsEmpty(S))
		printf("Wrong order.\n");
	else
		printf("Right order.\n");

	FreeStack(S);
	return 0;
}