括号匹配问题的堆栈操作.doc

《算法与数据结构》实验报告

实验名称: 堆栈操作
系 别:计算机 专业:计算机科学与技术 班级:
姓 名: 学号:
实验日期: 年 月 日
教师审批签字:

⒈ 实验名称: 堆栈操作

⒉ 实验题目: 用链栈表实现堆栈的基本操作，编写实现堆栈的下列四种操作的函数并用这个堆栈实现书上的括号匹配问题
（1） stack_Initial(S)：将堆栈S初始化；
（2） Stack_Not_Empty(S):判断堆栈是否为空；
（3） Stack_Push(S,x)：将元素x压入堆栈S的栈顶；
（4） Stack_Pop(S,data)：弹出堆栈S的栈顶元素；
（5） Stack_Top(S,data)：取堆栈S的栈顶元素。

⒊ 实验目的: 通过实验使学生掌握堆栈的基本知识和基本操作，并通过程序实现链堆栈的最基本和最主要的操作。

⒋ 定义的数据结构:

typedef struct node
{
DataType data;
struct node *next;

}LsNode;

⒌ 算法思想或算法步骤:在算数表达式中，右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。

⒍ 算法分析:括号匹配共有以下四种情况：
（1） 左右括号配对次序不正确；
（2） 右括号多于左括号；
（3） 左括号多于右括号；
（4） 左右括号配对正确。
具体方法为：顺序扫描算数表达式，当遇到3种类型括号的左括号时，让该括号进栈。当扫描到某一类型类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配，则退栈继续进行判断：如当前栈顶括号与当前扫描的括号不同，则左右括号匹配次序不正确；若字符串当前为某种类型的右括号而堆栈已空，则说明右括号多于左括号；字符串循环扫描结束时，若堆栈非空，则说明左括号多于右括号；如果未出现上述3种情况，则说明左右括号匹配正确。

⒎ 实验程序:
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef char DataType;

typedef struct node
{
DataType data;
struct node *next;

}LsNode;

void stack_Initial(LsNode **head)
{
*head =(LsNode*)malloc(sizeof(LsNode));
(*head)->next = NULL;
}

int Stack_Not_Empty(LsNode *head)
{
if(head->next == NULL) return 0;
else return 1;
}

int Stack_Push(LsNode *head,DataType x)
{
LsNode *p = (LsNode*)malloc(sizeof(LsNode));
if(p == NULL)
{
printf("申请内存不成功！");
return 0;
}
p->data = x;
p->next = head->next;
head->next = p;
return 1;
}

int Stack_Pop(LsNode *head,DataType *d)
{
LsNode *p=NULL;
if(!Stack_Not_Empty(head))
{
printf("堆栈已为空！");
return 0;
}
*d = (head->next)->data;
p = head->next;
head->next = p->next;
free(p);
return 1;
}

int Stack_Top(LsNode *head,DataType *d)
{
LsNode *p=NULL;
if(!Stack_Not_Empty(head))
{
printf("堆栈已为空！");
return 0;
}
*d = (head->next)->data;
return 1;
}

void ExIsCorrect(char exp[],int n)
//判断有n个字符的字符串括号匹配
{
LsNode *head;
int i;
char c;
stack_Initial(&head);
for(i=0;i<n;i++)
{
if((exp[i] == '(') || (exp[i] == '{') || (exp[i] == '['))
Stack_Push(head,exp[i]);
else if(exp[i]==')' && Stack_Not_Empty(head) &&
Stack_Top(head,&c) && c== '(')
Stack_Pop(head,&c);
else if(exp[i]==')' && Stack_Not_Empty(head) &&
Stack_Top(head,&c) && c != '(')
{
printf("左右括号配对次序不正确！\n");
return;
}
else if(exp[i]==']' && Stack_Not_Empty(head) &&
Stack_Top(head,&c) && c == '[')
Stack_Pop(head,&c);
else if(exp[i]==']' && Stack_Not_Empty(head) &&
Stack_Top(head,&c) && c != '[')
{
printf("左右括号配对次序不正确！\n");
return;
}
else if(exp[i]=='}' && Stack_Not_Empty(head) &&
Stack_Top(head,&c) && c== '{')
Stack_Pop(head,&c);
else if(exp[i]=='}' && Stack_Not_Empty(head) &&
Stack_Top(head,&c) && c != '{')
{
printf("左右括号配对次序不正确！\n");
return;
}
else if(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}'))&&
!Stack_Not_Empty(head))
{
printf("右括号多于左括号！\n");
return ;
}
}

if(Stack_Not_Empty(head))
{
printf("左括号多于右括号！\n");
}
else
{
printf("左右括号匹配正确！\n");
}
}

void main(void)
{
char a[]="(())abc{[]()}";
char b[]="(()))abc{[]}";
char c[]="()()([])({})";
int n1 = strlen(a);
int n2 = strlen(b);
int n3 = strlen(c);

ExIsCorrect(a,n1);
ExIsCorrect(b,n2);
ExIsCorrect(c,n3);
}

⒏ 问题与总结:括号匹配问题主要是围绕括号匹配出现的情况来实现的，并且利用堆栈先进后出的特点来进行括号匹配的判断。其中要注意若当前字符串的字符与栈顶元素匹配，则要把该元素出栈。