《数据结构》实验报告
一．实验题目
表达式求值
设计一个程序，演示用算符优先法对算术表达式求值的过程。
测试数据：
3*（7-2）
2*（6+2*（3+6*（6+6）））+（6+6）*3+2
8/（9-9）
(一) 需求分析
1.本程序需要编写这样一个程序：
（1）开始
（2）首先要建立两个栈：运算数栈和运算符栈；
（3）向运算符站中存入“\n”（也可以是#）这个优先级最低的元素；
（4）输入运算表达式；
（5）分析数据，如果输入的是运算数，则储存，如果输入的是运算符，则与运算符栈的栈顶元素比较：
（1）如果栈顶元素的优先级低于当前运算符，则将它读入运算符栈；
（2）在栈顶元素的优先级等于当前运算符时，则删除栈顶元素并返回其值，（这种情况只有输入结束或两个括号相遇时才会出现）分析下一个数据运算符；
（3）当栈顶元素的优先级小于当前运算符时，删除栈顶元素并返回其值，然后用栈顶元素与其前后的元素进行运算，并将运算后的结果储存在运算数栈中；
（6）输出运算结果；
（7）结束
(二) 概要设计
这个程序的核心是栈的应用。
1. 基本操作：
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack_Symbol;
操作结果：对运算符号栈进行定义；
typedef struct{
float *base;
float *top; //运算数栈
int stacksize;
}SqStack_Number;
操作结果：对运算数栈进行定义；
void InitStack_Symbol(SqStack_Symbol *S) 操作结果：创建运算符栈；
void InitStack_Number(SqStack_Number *S) 操作结果：创建运算数栈；
int GetTop_Symbol(SqStack_Symbol *S) 操作结果：返回栈顶运算符元素；
float GetTop_Number(SqStack_Number *S) 操作结果：返回栈顶运算数元素；
char Push_Symbol(SqStack_Symbol *S,char e) 操作结果：插入栈顶运算符元素；
float Push_Number(SqStack_Number *S,float e) 操作结果：插入栈顶运算数元素；
char Pop_Symbol(SqStack_Symbol *S)
操作结果：删除栈顶运算数元素，并返回其值；
float Pop_Number(SqStack_Number *S)
操作结果：删除栈顶运算数元素，并返回其值；
char T[8]="+-*/()\n";
操作结果：定义运算符号；
char Prior[7][7] =
{ // 运算符优先级表
// '+' '-' '*' '/' '(' ')' '\n' /*'+'*/'>','>','<','<','<','>','>', /*'-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>','>','<','>','>', /*'/'*/'>','>','>','>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*')'*/'>','>','>','>',' ','>','>', /*'\n'*/'<','<','<','<','<',' ','=',
};
操作结果：运算符优先级比较列表
char Precede(char a,char b)
操作结果：判断运算符优先级；
float Operate(float a,char optr,float b)
操作结果：计算两个操作数；
2.本程序包含五个模块：
主程序，操作数栈及相关函数，操作符栈及相关函数，运算符列表及优先级表，运算符优先级判断函数和计算函数。
（三）详细设计
1.结构体定义
typedef struct{
char *base; //运算符栈
char *top;
int stacksize;
}SqStack_Symbol;
typedef struct{
float *base;
float *top; //运算数栈
int stacksize;
}SqStack_Number;
2. 每个模块的分析：
（1）主程序模块：
int main(){
SqStack_Symbol OPTR;
SqStack_Number OPND;
float a,b,i,m,n;
char optr,c,x;
InitStack_Symbol(&OPTR); //创操作符栈
Push_Symbol(&OPTR,'\n'); //以“\n”开始
InitStack_Number(&OPND); //创建操作数栈
printf("输入表达式并以'回车'结尾:\n");
c=getchar();
if(c==35||(c>=40&&c<=43)||c==45||(c>=47&&c<=57)) //输入数据限定为“\n”“,+”,“-”,“*”,“/”“()”和“0-9”
{
while(c!='\n'||GetTop_Symbol(&OPTR)!='\n') //当输入不是‘\n’运算符时 {
if(c>=48&&c<=57)
while(c>=48&&c<=57)
{
i=i*10+(float)c-48;
c=getchar();
}
Push_Number(&OPND,i);
}
else
{
switch(Precede(GetTop_Symbol(&OPTR),c) ) //比较优先级 {
case'<':Push_Symbol(&OPTR,c); //栈顶元素的优先级低，则当前运算符进栈，读入下一字符
c=getchar();
break;
case'=':x=Pop_Symbol(&OPTR); //栈顶元素与当前运算符优先级相等，删除，并读入下一字符
c=getchar();
break;
case'>':optr=Pop_Symbol(&OPTR);
b=Pop_Number(&OPND); //栈顶元素优先级高，运算，结果进入运算数栈
a=Pop_Number(&OPND);
Push_Number(&OPND,Operate(a,optr,b));
break;
}
}
}
m=GetTop_Number(&OPND);
n=GetTop_Number(&OPND);
if(n==int(m))
printf("运算结果：%d\n",int(m)); //若是整数，则以整数输出
else printf("%f\n",n);
}
else printf("输入错误!\n");
return 0;
}
（2）运算符栈及相关函数
typedef struct{
char *base; //定义运算符栈
char *top;
int stacksize;
}SqStack_Symbol;
void InitStack_Symbol(SqStack_Symbol *S){ //创建运算符栈
(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
}
int GetTop_Symbol(SqStack_Symbol *S){ //返回栈顶运算符元素
char e;
if((*S).top==(*S).base) return ERROR;
e= *((*S).top-1);
return e;
}
char Push_Symbol(SqStack_Symbol *S,char e){ //插入栈顶元素
if((*S).top-(*S).base>=(*S).stacksize){
(*S).base= (char*) realloc ((*S).base , ((*S).stacksize + STACKINCREMENT)*sizeof(char)); //空间不足则增加空间分配
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
char Pop_Symbol(SqStack_Symbol *S){ //删除栈顶元素
char e;
if((*S).top==(*S).base) return ERROR;
e=*(--(*S).top);
return e;
}
（3）运算数栈及相关函数
typedef struct{
float *base;
float *top; //运算数栈
int stacksize;
}SqStack_Number;
void InitStack_Number(SqStack_Number *S){ //创建运算数栈
(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
}
float GetTop_Number(SqStack_Number *S){ //返回栈顶运算数元素
float e;
if((*S).top==(*S).base) return ERROR;
e=*((*S).top-1);
return e;
}
float Push_Number(SqStack_Number *S,float e){ //插入栈顶元素
if( (*S).top-(*S).base >= (*S).stacksize){
(*S).base= (float*) realloc ((*S).base , ((*S).stacksize STACKINCREMENT)*sizeof(float)); //空间不足则增加空间分配
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
float Pop_Number(SqStack_Number *S){ //删除栈顶元素，并返回其值 float e;
if((*S).top==(*S).base) return ERROR;
e=*(--(*S).top);
return e;
}
（4）运算符表及优先级表
char T[8]="+-*/()\n";
char Prior[7][7] =
{ // 运算符优先级表
// '+' '-' '*' '/' '(' ')' '\n'
/*'+'*/'>','>','<','<','<','>','>',
/*'-'*/'>','>','<','<','<','>','>',
/*'*'*/'>','>','>','>','<','>','>',
/*'/'*/'>','>','>','>','<','>','>',
/*'('*/'<','<','<','<','<','=',' ',
/*')'*/'>','>','>','>',' ','>','>', +
/*'\n'*/'<','<','<','<','<',' ','=',
};
（5）判断优先级并计算
har Precede(char a,char b){
int i=0,j=0; //判断运算符优先级
while(T[i]!=a)
i++;
while(T[j]!=b)
j++;
return(Prior[i][j]); //返回在运算符优先级表中的比较结果 }
float Operate(float a,char optr,float b){ //运算函数 float m;
switch(optr){
case'+':m=a+b;break;
case'-':m=a-b;break;
case'*':m=a*b;break;
case'/':if(b!=0) m=a/b;
else printf("输入错误!");
break;
}
return m;
}
（四）程序使用说明及测试结果
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
输入表达式并以回车结尾：
输入后显示：
运算结果：
2．测试结果
输入表达式：3*（7-2）
输出结果：15
输入表达式; 2*（6+2*（3+6*（6+6）））+（6+6）*3+2 输出结果：350
（五）、实验总结(实验心得)
1.你在编程过程中花时多少？
答：从周五实验课到周日晚完成实验报告，一共用了约八个小时。
2.多少时间在纸上设计？
答：两个小时
3.多少时间上机输入和调试？
答：编程与调试用的时间最长，大概六个小时。
4.多少时间在思考问题？
答：从编程到调试的八个小时里，面对对我来说困难的程序，和不断涌现的各种错误，我一直在思考怎样解绝这个问题。
5.遇到了哪些难题？你是怎么克服这些困难的？
答：在做这项作业时。我可以说自己遇到了无数难题，以为我的C语言成绩并不好，栈的熟悉度恐怕只有10%。因此完成这项作业的过程可谓艰辛。
首先遇到的困难就是设计程序。去年C语言学得很不扎实，我对链表的结构都不甚了解，更别说运用与之相关的算法了。在周五下午数据结构的实验课上，我花了半个小时重新回顾C语言教科书栈上的基础知识，好在数据结构书上有创建栈的程序。由于知识的匮乏，我只能先将书上的栈的定、创建、进栈、出栈函数敲到电脑上， 然后在纸上设计相应的流程。最后凭借自己脑海里仅存的知识，并利用同学的帮助，磕磕绊绊地编写了主函数。
接下来的困难，也就是最大，最麻烦，解决起来最耗费脑力，最枯燥乏味的问题——调试程序。最初的程序编译之后，问题触目惊心，我根据系统的提示，首先补上了缺失的间隔符，又定义了遗漏的变量，再次编译，错误有所减少，但依然多，我又重新修改。接下来的错误越来越“高级”，数据类型，返回类型，函数类型等有关。我便循环往复，不厌其烦地修改，每当减少一个错误，我都会有几分高兴，而有的时候，修改后会产生更多的错误。
就这样一遍又一遍，终于系统显示没有错误和警告了。我运行了程序。当我按照自己的设想将输入数据时，敲下回车键后结果却令我傻了眼。屏幕上没有任何显示。，原来许多错误是编译器没有检测出来。
知道第二天，我参考了网上的一些算法又请教了同学，才知道自己犯了哪些低级的错误。比如说指针的地址和指针所指向的对象的值没有区分清楚；函数的返回值应为链表的首结点，而不是函数中指向该链表的指针。后来又经过了几个小时的修改和编译调试，我最终才完成了完整地程序。
但后来更可怕的事发生了，我不知怎么竟然丢失了自己编写的程序！只能凭借记忆重新编写。知识掌握的不牢固，我又耗费了大量时间，还犯了许多低级错误，最终凭借努力终于完成了程序。
6．你的收获有哪些？
答：首先，我对栈不分的知识有了更多了解破除了错误的认识。
其次，通过这次作业，我掌握了几种与栈有关的算法。
最后，我还温习了有关C语言的许多知识。
附：完整程序
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
char *base; //运算符栈
char *top;
int stacksize;
}SqStack_Symbol;
typedef struct{
float *base;
float *top; //运算数栈
int stacksize;
}SqStack_Number;
void InitStack_Symbol(SqStack_Symbol *S){ //创建运算符栈 (*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
}
void InitStack_Number(SqStack_Number *S){ //创建运算数栈 (*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float)); if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
}
int GetTop_Symbol(SqStack_Symbol *S){ //返回栈顶运算符元素 char e;
if((*S).top==(*S).base) return ERROR;
e= *((*S).top-1);
return e;
}
float GetTop_Number(SqStack_Number *S){ //返回栈顶运算数元素 float e;
if((*S).top==(*S).base) return ERROR;
e=*((*S).top-1);
return e;
}
char Push_Symbol(SqStack_Symbol *S,char e){ //插入栈顶元素
if((*S).top-(*S).base>=(*S).stacksize){
(*S).base= (char*) realloc ((*S).base , ((*S).stacksize + STACKINCREMENT)*sizeof(char));
//空间不足则增加空间分配
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
float Push_Number(SqStack_Number *S,float e){ //插入栈顶元素 if( (*S).top-(*S).base >= (*S).stacksize){
(*S).base= (float*) realloc ((*S).base , STACKINCREMENT)*sizeof(float)); //空间不足则增加空间分配
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
char Pop_Symbol(SqStack_Symbol *S){ //删除栈顶元素
char e;
if((*S).top==(*S).base) return ERROR;
e=*(--(*S).top);
return e;
}
float Pop_Number(SqStack_Number *S){ //删除栈顶元素
float e;
if((*S).top==(*S).base) return ERROR;
e=*(--(*S).top);
return e;
}
char T[8]="+-*/()\n";
char Prior[7][7] =
{ // 运算符优先级表
// '+' '-' '*' '/' '(' ')' '\n'
/*'+'*/'>','>','<','<','<','>','>',
/*'-'*/'>','>','<','<','<','>','>',
/*'*'*/'>','>','>','>','<','>','>',
/*'/'*/'>','>','>','>','<','>','>',
/*'('*/'<','<','<','<','<','=',' ',
/*')'*/'>','>','>','>',' ','>','>',
/*'\n'*/'<','<','<','<','<',' ','='
((*S).stacksize +
};
char Precede(char a,char b){
int i=0,j=0; //判断运算符优先级
while(T[i]!=a)
i++;
while(T[j]!=b)
j++;
return(Prior[i][j]); //返回在运算符优先级表中的比较结果
}
float Operate(float a,char optr,float b){ //运算函数
float m;
switch(optr){
case'+':m=a+b;break;
case'-':m=a-b;break;
case'*':m=a*b;break;
case'/':if(b!=0) m=a/b;
else printf("输入错误!");
break;
}
return m;
}
int main(){
SqStack_Symbol OPTR;
SqStack_Number OPND;
float a,b,i=0,m,n;
char optr,c,x;
InitStack_Symbol(&OPTR); //创操作符栈
Push_Symbol(&OPTR,'\n'); //以“\n”开始
InitStack_Number(&OPND); //创建操作数栈
printf("输入表达式并以'回车'结尾:\n");
c=getchar();
if(c==35||(c>=40&&c<=43)||c==45||(c>=47&&c<=57)) //输入数据限定为“\n”“,+”,“-”,“*”,“/”“()”和“0-9”
{
while(c!='\n'||GetTop_Symbol(&OPTR)!='\n')
{
if(c>=48&&c<=57){
while(c>=48&&c<=57)
{
i=i*10+(float)c-48;
c=getchar();
}
Push_Number(&OPND,i);
}
else
{ i=0;
switch(Precede(GetTop_Symbol(&OPTR),c)) //比较优先级 {
case'<':Push_Symbol(&OPTR,c);
c=getchar();
break;
case'=':x=Pop_Symbol(&OPTR);
c=getchar();
break;
case'>':optr=Pop_Symbol(&OPTR);
b=Pop_Number(&OPND);
a=Pop_Number(&OPND);
Push_Number(&OPND,Operate(a,optr,b)); break;
}
}
}
m=GetTop_Number(&OPND);
n=GetTop_Number(&OPND);
if(n==int(m))
printf("运算结果：%d\n",int(m)); //若是整数，则以整数输出 else printf("%f\n",n);
}
else printf("输入错误!\n");
return 0；
}
参考文献：【1】严蔚敏?《数据结构?第三章》清华大学出版社