*******************************
实验题目：栈的基本运算
实验者信息：
班级 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");
}
五、 总结和心得
实验完成后的总结和思考。
此次实验很顺利！
