实验三顺序栈实现括号匹配

实验三顺序栈实现括号匹配 顺序栈实现括号匹配 一、需求分析

1、数据存储结构为栈
2、输入形式为键盘
3、输出形式为打印形式
4、包含栈的基本 *** 作
5、能够完成指定要求的括号匹配 *** 作

二、概要设计 一、抽象数据类型定义

ADT Stack {
数据对象：D = {ai | ai ∈ ElemSet，i = 1,2,3,…,n, n ≥ 0}
数据关系： R1={ | ai-1 , ai∈D，i=2，…，n} // ai-1为前驱，ai为后继，约定 an 端为栈顶，a1 端为栈底
基本 *** 作：
InitStack（&S）初始化 *** 作
*** 作结果：构造一个空栈 S

DestroyStack（&S）销毁栈 *** 作
初始条件：栈S已存在
*** 作结果：栈S被销毁

StackEmpty（S）判定栈是否为空栈
初始条件：栈S已存在
*** 作结果：若栈S为空栈，则返回TRUE，
若栈S为非空，则返回FALSE。

StackLength（S）求栈的长度
初始条件：栈S已存在
*** 作结果：返回栈S的元素个数，即栈的长度

GetTop（S，&e）取栈顶元素
初始条件：栈S已存在且非空
*** 作结果：用e返回S的栈顶元素

ClearStack（&S）栈指控 *** 作
初始条件：栈S已存在
*** 作结果：将S清为空栈

Push（&S，e）入栈 *** 作
初始条件：栈S已存在
*** 作结果：插入元素e为新的栈顶元素

Pop（&S，&e）出栈 *** 作
初始条件：栈S存在且非空
*** 作结果：删除栈SD栈顶元素an，并用e返回其值
} ADT Stack

二、宏定义部分

#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100 //顺序空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

三、主程序流程图

四、程序结构图

三、详细设计 一、数据类型设计

Status InitStack(SqStack &S)
{ // *** 作结果：构造一个空栈 S
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!(S.base))
exit(-1); // 存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}

Status DestroyStack(SqStack &S)
{ // 初始条件：栈 S 已经存在
// *** 作结果：销毁栈 S，S 不再存在
if(&S==NULL)
return ERROR;
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize = 0;
return OK;

}

Status ClearStack(SqStack &S)
{ // 初始条件：栈存在
// *** 作结果：把 S 置为空栈
if(&S==NULL)
return ERROR;
if (S.base)
S.top = S.base;
return OK;
}

Status StackEmpty(SqStack S)
{ // 初始条件：栈 S 已经存在
// *** 作结果：若栈 S 为空栈，则返回 TRUE，否则返回 FALSE
if (S.top == S.base)
return TRUE;
else
return FALSE;
}

int StackLength(SqStack S)
{ // 初始条件：栈 S 已经存在
// *** 作结果：返回 S 的元素个数，即栈的长度
return S.top - S.base;
}

Status GetTop(SqStack S, SElemType &e)
{ // 初始条件：栈 S 已经存在
// *** 作结果： 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR
if(S.top == S.base)
return ERROR;
if (S.top > S.base)
{
e = *(S.top - 1);
return OK;
}
else
{
return ERROR;
}
}

Status Push(SqStack &S, SElemType e)
{ // 初始条件：栈 S 已经存在
// *** 作结果：插入元素 e 为新的栈顶元素
if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间
{
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!(S.base))
exit(-1); // 存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*(S.top)++ = e;
}

Status Pop(SqStack &S, SElemType &e)
{ // 初始条件：栈 S 已经存在
// *** 作结果： 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR
if (S.top == S.base)
return ERROR;
e = *–(S.top);
return OK;
}

void StackTraverse(SqStack S, void (*visit)(SElemType))
{ // 初始条件：栈 S 已经存在
// *** 作结果：从栈底到栈顶依次对栈中每个元素调用函数 visit()
while (S.top > S.base)
visit(*S.base++);
printf("n");
}

三、主程序

int main(){
SqStack OPTR;
InitStack(OPTR);
char input = ‘0’;
while (input != ‘n’)
{
scanf("%c", &input);
if(input == ‘(’ || input == ‘[’ || input == ‘{’)
{
Push(OPTR, input);
}
if (input == ‘)’ || input == ‘]’ || input == ‘}’)
{
SElemType e;
GetTop(OPTR, e);
switch (input)
{
case ‘)’:
if(e==’(’)
break;
case ‘]’:
if(e==’[’)
break;
case ‘}’:
if(e==’{’)
break;
default:
printf(“ERROR”);
system(“exit”);
}
}
}
if(!StackEmpty(OPTR))
{
printf(“ERROR”);
system(“exit”);
}
input = ‘0’;
DestroyStack(OPTR);
return 0;
}

四、调试分析

一、主要问题与解决方案
1、发现括号匹配出现问题，调试后发现主要是出入栈问题。

五、用户使用说明

一、本程序运行环境为Windows *** 作系统下的Microsoft Visual C++ 6.0。
二、在VC环境下打开程序后，输入字符，并敲击“回车符”输入，即可以显示要求的结果。
三、按下任意键以继续。
六、测试结果

七、附录

#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100	//顺序空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

typedef int Status;	 
typedef char SElemType;

typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
} SqStack;

Status InitStack(SqStack &S);
	//构造一个空栈
Status DestroyStack(SqStack &S);
	//销毁栈S,S不再存在
Status ClearStack(SqStack &S);
	//把S置为空栈
Status StackEmpty(SqStack S);
	//判断是否为空栈
int StackLength(SqStack S);
	//返回S的元素个数，即栈的长度
Status GetTop(SqStack S, SElemType &e);
	//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR；
Status Push(SqStack &S, SElemType e);
	//插入元素e为新的栈顶元素
Status Pop(SqStack &S, SElemType &e);
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR；
Status StackTraver(SqStack S, Status (*visit)());
	//从栈低到栈顶依次对栈中每个函数调用visit（），一旦失败返回ERROR；






int main(){

	SqStack OPTR;
	InitStack(OPTR);
	char input = '0';
	while (input != 'n')
	{
		scanf("%c", &input);
		if(input == '(' || input == '[' || input == '{')
		{
			Push(OPTR, input);
		}
		
		if (input == ')' || input == ']' || input == '}')
		{
			SElemType e;
			GetTop(OPTR, e);
			switch (input)
			{
			case ')':
				if(e=='(')
				break;
			case ']':
				if(e=='[')
				break;
			case '}':
				if(e=='{')
				break;
			
			default:
				printf("ERROR");
				system("exit");
			}
		}
		
	}
	if(!StackEmpty(OPTR))
	{
		printf("ERROR");
		system("exit");
	}
	input = '0';
	DestroyStack(OPTR);
	
	return 0;
}


 
// 顺序栈的基本 *** 作(9个)
 

Status InitStack(SqStack &S)
{ //  *** 作结果：构造一个空栈 S
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!(S.base))
        exit(-1); // 存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
 
    return OK;
}
 

Status DestroyStack(SqStack &S)
{ // 初始条件：栈 S 已经存在
    //  *** 作结果：销毁栈 S，S 不再存在
	if(&S==NULL)
		return ERROR;
	free(S.base);
    S.base = NULL;
    S.top = NULL;
    S.stacksize = 0;
 
    return OK;
}
 

Status ClearStack(SqStack &S)
{ // 初始条件：栈存在
    //  *** 作结果：把 S 置为空栈
	if(&S==NULL)
		return ERROR;
    if (S.base)
        S.top = S.base;
 
    return OK;
}
 

Status StackEmpty(SqStack S)
{ // 初始条件：栈 S 已经存在
    //  *** 作结果：若栈 S 为空栈，则返回 TRUE，否则返回 FALSE
    if (S.top == S.base)
        return TRUE;
    else
        return FALSE;
}
 

int StackLength(SqStack S)
{ // 初始条件：栈 S 已经存在
    //  *** 作结果：返回 S 的元素个数，即栈的长度
    return S.top - S.base;
}
 

Status GetTop(SqStack S, SElemType &e)
{ // 初始条件：栈 S 已经存在
    //  *** 作结果： 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR
	if(S.top == S.base)
		return ERROR;
    if (S.top > S.base)
    {
        e = *(S.top - 1);
        return OK;
    }
    else
    {
        return ERROR;
    }
}
 

Status Push(SqStack &S, SElemType e)
{ // 初始条件：栈 S 已经存在
    //  *** 作结果：插入元素 e 为新的栈顶元素
    if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间
    {
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!(S.base))
            exit(-1); // 存储分配失败
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *(S.top)++ = e;
}
 

Status Pop(SqStack &S, SElemType &e)
{ // 初始条件：栈 S 已经存在
    //  *** 作结果： 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR
    if (S.top == S.base)
        return ERROR;
    e = *--(S.top);
    return OK;
}
 

void StackTraverse(SqStack S, void (*visit)(SElemType))
{ // 初始条件：栈 S 已经存在
    //  *** 作结果：从栈底到栈顶依次对栈中每个元素调用函数 visit()
    while (S.top > S.base)
        visit(*S.base++);
    printf("n");
}