括号匹配课程设计报告
- 格式:doc
- 大小:96.50 KB
- 文档页数:6
题目:括号匹配检验
一、问题描述:
假设一个算术表达式可以包含3种括号:圆括号“(”和“)”,方括号“[”和“]”,和花括号“{”和“}”且这三种括号可按照任意次序嵌套使用(如:…[…{…}…[…]…]…[…]…(…)…)。设计一个程序,判别所给定表达式中所含括号是否匹配。
二、要求:
1.将算术表达式保存在带头结点的单链表中;
2.在1中建立的单链表上实现括号匹配问题的求解。
三、解决问题思路:
1、首先建立带头结点的单链表,单链表的数据域存储字符数据,指针域为结
点型指针。设立字符型数组先将算术表达式输入到数组当中,通过插入节
点函数将数组中字符全部插入到单链中1中。
2、建立单链表2,通过switch,case语句将单链表1中的括号字符全部插入到
单链表2中。
3、调用括号匹配函数将,单链表2的头节点调入函数当中,设立标志位has。
当has取1时,说明找到一组匹配括号;当has取0时,当前一组括号不匹配。设立temp指向当前所要判断节点,将temp所指节点的值与temp-〉next节点的值相比较,利用匹配括号ASCII值相差1或2,相同则相差0;
或不相同差值不为1、2或0。当temp与temp-〉next的差值为1或2时,说明找到一组匹配括号。Temp=temp-〉next;进行新的判断。当temp与
temp-〉next的差值不为1或2时,将temp赋为temp-〉next;进行新一轮的判断。若temp-〉next-〉next与temp-〉next-〉next-〉next匹配时,此时将temp-〉next-〉next与temp-〉next-〉next-〉-〉next全部值为空值。
且temp-〉next未找到匹配字符时将temp重新赋为temp->next,进行新的判断。
4、最后,若单链表p为空则则说明表达式中括号匹配;若p不为空,则说明
算术表达式中括号不匹配。
四、运行环境:
1、编辑主要环境为microsoft visualC++6.0。
2、调试运行环境为Turbo C2.0。
五、源代码及注释:
括号匹配源程序代码及注释
kuohaopipei.c#include
#include
#include
#define LEN 80
typedef struct list
{
char node; /*数据域*/
struct list *next; /*指针域*/
}list,*linklist; /*节点类型*/
void initlist(linklist); /*函数声明*/
int isempty(linklist);
int creatlist_node(linklist,char);
Textlist(linklist);
void main() /*主函数*/
{
char test[LEN];
int i;
list a,b;
linklist p,q=&b; /*设立P为list结点指针*/
p=&a; /*使P指向头结点a*/
initlist(p); /*使p为第一个节点*/
printf("Pliease input the expression:\n");
scanf("%80s",test);
for(i=0;i creatlist_node(q,test[i]); /*将数组中算术表达式存入单链表q中*/ for(i=0;i { switch(q->node) { case '[': case ']': case '{': case '}': case '(': case ')': creatlist_node(p,q->node);/*将q中括号插入单链表p中*/ break; default : continue; /*若节点中字符不为括号则进入下一次循环*/ } } Testlist(p); /*调用判断括号匹配函数,用P链表作为实参*/ if(isempty(p)) /*判断P是否为空,p为空则表达式中括号匹配*/ { printf("True\n"); printf("the kuo hao in expression is pipei\n"); } else /*P不为空,则表达式中括号不匹配*/ { printf("False\n"); printf("the kuo hao in expression is not pipei\n"); } } void initlist(linklist aplist) /*构造头结点函数*/ { struct list *next; aplist->next=NULL; aplist->node='\0'; } int isempty(linklist aplist) /*判断头结点是否为空函数*/ { linklist next; return aplist->next==NULL?1:0; /*头结点不为空侧返回0*/ } int creatlist_node(linklist aplist,char a) /*插入字符节点函数*/ /*建立list型anode节点,将字符a插入*/ { linklist bplist=aplist,anode; /*设立bplist作为中间变量用于添加节点*/ while(bplist->next) { bplist=bplist->next; } anode=(linklist)malloc(sizeof(list)); /*构造一个list型节点并分配空间*/ if(!anode) exit(-1);