*******************************
实验题目:栈的基本运算
实验者信息:
班级 13007102,姓名 庞文正,学号 1300710226
实验完成的时间 3:00
******************************
一、 实验目的
1,掌握栈的各种存储结构及基本运算的实现。
2,掌握堆栈后进先出的运算原则在解决实际问题中的应用。 3,复习c 语言中相关语句及函数的用法。
二、 实验内容
括号配对检查。试设计一个程序对任意输入的语句或数学表达式,判断其括号是否匹配。若匹配,则返回1,否则返回0。调试程序并对相应的输出作出分析;修改输入数据,预期输出并验证输出的结果。加深对算法的理解。
三、 算法设计与编码
1. 本实验用到的理论知识
总结本实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关,最好能加上自己的解释。
2. 算法概要设计
给出实验的数据结构描述,程序模块、功能及调用关系
首先建立一个栈结构,且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式,同时将它们保存在一个字符型数组exps[]中。扫描表达式exps, 当遇到“(”、“[”、“{”时,将其入栈。遇到“)”、“]”、“}”时,判断栈顶是否有相匹配的括号。若没有,则退出扫描过程,返回0,否则直到exps 扫描完毕为止。若top 为0,则返回1。
#include
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
typedef int datatype;
typedef struct //顺序栈的结构体定义
{
datatype stack[MAXSIZE]; int top;
}seqstack;
void setnull(seqstack *s) //置空栈-由于c 语言的数组下标是从0开始的,所以置
{s->top=-1;} // {s->top=-1;} 空栈操作时将栈顶指针放在下标为0之前,即-1处。
int empty(seqstack *s) /*判断当前栈是否为空栈*/
{
if(s->top
return TRUE;
else
return FALSE;
}
int push(seqstack *s,datatype x) /*把元素x 压入栈s 中*/ {
if(s->top>=MAXSIZE-1)
{
printf("stack overflow!\n"); /*发生上溢*/
return FALSE;
}
else
{
s->stack[++s->top]=x; /*栈顶指针上移,数据元素入栈*/ return TRUE;
}
}
datatype pop(seqstack *s) /*弹出当前栈s 的栈顶元素*/ {
if(s->top
{
printf("stack empty!\n"); /*栈空,返回空值*/
return -1;
}
else
{
s->top--;
return(s->stack[s->top+1]);
}//由于return 语句的特点,必须先使top 减1,然后再执行return 语句。而此
} // 时栈顶元素的表示应该为s->top+1.
int judge(seqstack *s) //括号匹配检查算法。--遇到"("、"["、"{"时,
{ // 将其压 栈s 中。
datatype symb,ch,store;
push(s,'#');
symb=getchar();/*从键盘接受字符*/
while(symb!='#')
{
switch(symb)
{
case '(':
case '[':
case '{':
push(s,symb);break;
case ')':
ch=pop(s); if(ch!='(') return FALSE; break;
case ']':
ch=pop(s); if(ch!='[') return FALSE; break;
case '}':
ch=pop(s); if(ch!='{') return FALSE; break;
default: ;
}
symb=getchar();
}
if(pop(s)=='#') return TRUE;
else return FALSE;
}
int jinzhishuchu(seqstack *s)
{
int x,symb;
scanf("%d",&symb);/*从键盘接受字符*/ while(symb!=0)
{
push(s,symb%8);
symb=symb/8;
}
while (!empty(s))
{
x=pop(s); //出栈操作
printf("%d",x); //依次输出出栈结果
}
printf("\n");
}
main()
{
seqstack q;
setnull(&q);
printf("please input an express end with symbol '#':\n"); if(judge(&q))
printf("yes\n"); /*括号匹配,则输出yes*/ else
printf("no\n"); /*括号不匹配,则输出no*/
jinzhishuchu(&q);
}
四、 运行与测试
(1) 在调试程序的过程中遇到什么问题,是如何解决的?
答:遇到很多括号不匹配
(2) 设计了那些测试数据?测试结果是什么?
(3) 程序运行的结果如何?
成功运行!
1、 预习思考题
调试好上述程序后,试着完成以下拓展内容:
(1) 假定表达式不是通过getchar()函数一个个传送的,而
是存放在一个字符数组A[n]中,程序需要做哪些改变? 将while 改为for (i=0;i
switch(A[i])
{
case '(':
case '[':
case '{':
push(s,symb);break;
case ')':
ch=pop(s);
if(ch!='(') return FALSE; break;
case ']':
ch=pop(s);
if(ch!='[') return FALSE; break;
case '}':
ch=pop(s);
if(ch!='{') return FALSE; break;
default: ;
}
}
(2) 在judge()函数中,如果不用switch()函数,你会怎
么处理?
用if 替代
if(symb=='(' || symb=='{' || symb=='[') {
push(s,symb);
}
if(symb==')')
{
ch=pop(s);
if(ch!='(') return FALSE;
}
if(symb=='}')
{
ch=pop(s);
if(ch!='{') return FALSE;
}
if(symb==']')
{
ch=pop(s);
if(ch!='[') return FALSE;
}
2、 分析讨论题:
数制转换问题是栈应用的一个典型实例。将十进制数转换成其它进制的数有一种简单的方法:例:十进制转换成八进制:(66)10=(102)8
66/8=8 余 2
8/8=1 余 0
1/8=0 余 1
结果为余数的逆序:102 。如果用栈的算法来实现,怎样实现?其基本原理是什么?
int jinzhishuchu(seqstack *s) //括号匹配检查算法。--遇到"("、"["、"{"时,
{
int x,symb;
scanf("%d",&symb);/*从键盘接受字符*/ while(symb!=0)
{
push(s,symb%8);
symb=symb/8;
}
while (!empty(s))
{
x=pop(s); //出栈操作
printf("%d",x); //依次输出出栈结果 }
printf("\n");
}
五、 总结和心得
实验完成后的总结和思考。
此次实验很顺利!