《判断算术表达式中的括号是否配对》由会员分享，可在线阅读，更多相关《判断算术表达式中的括号是否配对（9页珍藏版）》请在金锄头文库上搜索。
1、南京信息工程大学数据结构实验（实习）报告实验（实习）名称 顺序表、单链表 实验（实习）日期 2015-10-11 得分 指导教师 顾韵华 系 计软院 专业 计科 年级 2014 级 班次 2 一、 实验目的1、掌握栈的顺序实现、栈的基本应用二、 实验内容1、给出栈的顺序存储的定义及程序实现。2、应用顺序栈，编程实现由十进制到十六进制的转换。3、设计一个算法，编写程序实现：判断一个算术表达式中的括号是否配对，并求出括号的最大嵌套层数。三、 数据结构设计和实现1.进制转换#include#include#define STACK_INIT_SIZE 100#define STACKINCREMEN
2、T 10/常量定义#define OK 1#define ERROR 0#define OVERFLOW -2#define True 1#define False 0/函数返回值定义typedef int Status;typedef int SElemType;typedef structSElemType * base;SElemType * top;int stacksize;SqStack;Status InitStack(SqStack /构造一个空栈Status DestroyStack(SqStack /销毁栈Status ClearStack(SqStack /把 s 置为空
3、栈Status StackEmpty(SqStack s);int StackLength(SqStack s);/返回栈的元素个数Status GetTop(SqStack s,SElemType /返回栈顶元素Status Push(SqStack /插入元素为新的栈顶元素Status Pop(SqStack /取出栈顶元素Status StackTraverse(SqStack s,Status(*vist)();void conversion(int x);/十进制转换十六进制int fun(int y);/判断栈内元素/函数实现#includestack.h#includestdio
4、.hStatus InitStack(SqStack &s)/创建一个空栈s.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack s,SElemType &e)/读取栈顶元素if(s.top=s.base) return ERROR;e=*(s.top-1);return OK;Status Push(SqStack &s,SE
5、lemType e)/压栈if(s.top-s.base=s.stacksize)s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status Pop(SqStack &s,SElemType &e)/删除栈顶元素if(s.top=s.base) return ERROR;e=*-s.
6、top;return OK;void conversion(int x)/进制转换SqStack s;int e;InitStack(s);while(x)Push(s,x%16);x=x/16;while(!StackEmpty(s)Pop(s,e);fun(e);printf(n);int fun(int y)if(y=10&y#include#includeint main()int n;while(printf(请输入要转换的数字 :)!=EOF)scanf(%d,conversion(n);return 0;2.括号配对#include#include#define STACK_IN
7、IT_SIZE 100#define STACKINCREMENT 10/常量定义#define OK 1#define ERROR 0#define OVERFLOW -2#define True 1#define False 0/函数返回值定义typedef int Status;typedef char SElemType;typedef structSElemType * base;SElemType * top;int stacksize;SqStack;Status InitStack(SqStack /构造一个空栈Status DestroyStack(SqStack /销毁栈S
8、tatus ClearStack(SqStack /把 s 置为空栈Status StackEmpty(SqStack s);int StackLength(SqStack s);/返回栈的元素个数Status GetTop(SqStack s,SElemType /返回栈顶元素Status Push(SqStack /插入元素为新的栈顶元素Status Pop(SqStack /取出栈顶元素Status StackTraverse(SqStack s,Status(*vist)();void matching(char *exp);/判断是否配对/函数实现#includematching.h
9、#includestdio.hStatus InitStack(SqStack &s)s.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack s,SElemType &e)if(s.top=s.base) return ERROR;e=*(s.top-1);return OK;Status Push(SqStack &s,SEl
10、emType e)if(s.top-s.base=s.stacksize)s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status Pop(SqStack &s,SElemType &e)if(s.top=s.base) return ERROR;e=*-s.top;return
11、OK;Status StackEmpty(SqStack s)return s.base=s.top;void matching(char *exp) / 检验表达式中所含括弧是否正确嵌套，若是，则返回 OK，否/ 则返回 ERROR;表达式存放于字符数组exp 中int state=1;/状态变量SqStack s;InitStack(s);/建一个空栈char *p;p=exp;/定义一个指针指向字符数组char e;int n=0,max=0;while (*p!=0&state)/表达式未结束且未判断出不匹配switch (*p) /依当前字符进行处理case :case (: Pus
12、h(s,*p);/左括号压栈n+;/计数变量增加if(nmax)max=n;p+;break; case : if (StackEmpty(s)/如果栈空state=0;printf(右括号比左括号多!n);exit(0); /不匹配elseGetTop(s,e); /读取栈顶元素至 eif (e=()Pop(s,e);n-;p+; /左括号出栈else state=0;printf(括号顺序不对!n);exit(0);break;case ): if (StackEmpty(s)/如果栈空state=0;printf(右括号比左括号多!n); exit(0); /不匹配elseGetTop(
13、s,e); /读取栈顶元素至 eif (e=()Pop(s,e);n-;p+; /左括号出栈else state=0;printf(括号顺序不对!n);exit(0);break;default: p+;if (state&StackEmpty(s)printf(括号配对!n);printf(最大嵌套层数为：%dn,max);elseprintf(左括号比右括号多!n);/主函数#includematching.h#include#include#includeint main()int i=0;char line100;printf(请输入字符串：);scanf(%s,line);matching(line);return 0;四、程序调试1、进制转换操作结果：2、括号配对操作结果；3、实验过程中遇到的问题：（1）进制转换时不能把大于 10 的数字转换成字母解决方法：重新写了一个判断函数（2）括号配对时不能结束循环，break 的位置加不正确解决方法：认真阅读程序，判断到底要在哪里结束循环5、实验总结通过这次实验，我对栈的理解更加透彻，也学会了进制转换和括号配对的方法。在写进制转换的程序的时候我在调用函数的时候出现了错误，我在主函数中输出最终结果就不可以，然后我把输出写在了被调函数里，运行正确了。在写括号配对的时候一开始只能输出正确配对的情况，然后我改了判断条件就运行正确了。
