《数据结构与数据库》
实验报告
实验题目
算术表达式求值
学 院：化学与材料科学学院
专业班级：09级材料科学与工程系 PB0920603
姓 名：李维谷
学 号：PB09206285
邮 箱：liwg@mail.ustc.edu.cn
指导教师：贾伯琪
实验时间：2010年10月10日
一、 需要分析
问题描述：
表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。
问题分析：
在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。
设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。
在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。
算法规定：
输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。
输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。
程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。
测试数据：正确输入：12*（3.6/3+4^2-1）#
输出结果：194.4
无定义运算：12*（3.6/（2^2-4）+1）#
输出结果：表达式出错，除数为0，无意义
错误输入：12+s#
输出结果：ERROR！
二、 概要设计
拟采用两种类型的展分别对操作数和操作符进行操作。程序中将涉及下列两个抽象数据类型：
1、设定“操作数”的栈的抽象数据类型定义：
ADT SqStack_f{
数据对象：D={
数据关系：R1={<
>|
,
,i=2,…，n}
约定
端为栈顶，端为栈底。
基本操作：
InitStack_f(&S)
操作结果：构造一个空栈S。
GetTop_f(&S,&e)
初始条件：栈S已存在。
操作结果：用e返回S的栈顶元素。
Push_f(&S，ch)
初始条件：栈S已存在。
操作结果：插入元素ch为新的栈顶元素。
Pop_f(&S,&e)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素，并以e返回其值。
}ADT SqStack_f
2、设定“操作符”的栈的抽象数据类型定义：
ADT SqStack_c{
数据对象：D={
数据关系：R1={<>|,,i=2,…，n}
约定端为栈顶，端为栈底。
基本操作：
InitStack_c(&S)
操作结果：构造一个空栈S。
GetTop_c(&S,&e)
初始条件：栈S已存在。
操作结果：用e返回S的栈顶元素。
Push_c(&S，ch)
初始条件：栈S已存在。
操作结果：插入元素ch为新的栈顶元素。
Pop_c(&S,&e)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素，并以e返回其值。
}ADT SqStack_c
3、本程序包含六个模块
1）主程序模块
void main( )
{
初始化；
while(命令==“继续”)
{
接受数据；
处理数据；
接受命令；
｝
｝
2）栈模块——实现栈抽象数据类型
3）判断运算符优先级模块——判断运算符的优先级别
4）后缀表达式转换模块——将中缀表达式转换为后缀表达式，方便操作
5）无括号表示式求值运算模块——根据后缀表达式求值，并输出中间和最终结果
6）运算结果输出模块——以正确形式输出表达式的值
三、 详细设计
1、主程序中需要的全程量
#define TTACK_INIT_SIZE 100 //初始分配最大空间量
#define STACKINCREMENT 10 //（默认）增补空间量
2、结点类型、指针类型
typedef struct{
float *base; //存储实型数据元素的一位数组
float *top; //栈顶指针
int stacksize; //栈数组容量
}SqStack_f; //有序存储实型的顺序表类型
typedef struct{
char *base; //存储字符数据元素的一位数组
char *top; //栈顶指针
int stacksize; //栈数组容量
}SqStack_c; //有序存储字符型的顺序表类型
void InitStack_f(SqStack_f *s)
void InitStack_f(SqStack_f *s)
//构造一个存储实型（字符型）的空栈，预设空间为100，分配失败就退出
void GetTop_f(SqStack_f *s,float *e)
void GetTop_c(SqStack_c *s,char *e)
//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序
void Push_f(SqStack_f *s,float e)
void Push_c(SqStack_c *s,char e)
//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间
void Pop_f(SqStack_f *s,float *e)
void Pop_c(SqStack_c *s,char *e)
//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
其中部分操作的伪码算法（由于比较类似，以浮点型的栈为例）
void InitStack_f(SqStack_f *s)
{//构造一个存储实型的空栈，预设空间为100，分配失败就退出
s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));
if(!s->base)
exit(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
void GetTop_f(SqStack_f *s,float *e)
{//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序
if(s->top==s->base)
{
printf("ERROR!\n");
exit(1);
}
*e=*(s->top-1);
}
void Push_f(SqStack_f *s,float e)
{//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间
if(s->top-s->base>=s->stacksize)
{
s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));
if(!s->base)
{
printf("OVERFLOW!\n");
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*s->top++=e;
}
void Pop_f(SqStack_f *s,float *e)
{//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
if(s->top==s->base)
exit(1);
*e=*--s->top;
}
3、判断运算符优先级的算法：
算符间的优先关系如下：
伪码算法：
int precede(char Top_char,char s1_char)
{//栈顶的运算符赋给Top_char，新读入的运算符赋给s1_char。判断它们的优先级
//若栈顶运算符优先级高，则返回1，否则返回0
int i,pre[2];
char op[2];
op[0]=Top_char; //栈顶的运算符赋给op[0]
op[1]=s1_char; //新读入的运算符赋给op[1]
for(i=0;i<2;i++)
switch(op[i])
{
case'(':case')':pre[i]=0;break; //将括号的优先级设为0
case'+':case'-':pre[i]=1;break; //将+ - 运算符的优先级设为1
case'*':case'/':pre[i]=2;break; //将* / 运算符的优先级设为2
case'^':pre[i]=3;break; //将^ 运算符的优先级设为3
}
if(pre[0]>=pre[1]) //栈顶元素优先级高返回1
return 1;
else
return 0; //否则返回0
}
4、中缀表达式转换为后缀表达式的算法：
算法过程描述：
1) 首先将左括号“(”压进栈，作为栈底元素；
2) 从左而右对算数表达式进行扫描，每次读入一个字符s1[i]；
3) 若遇到数字或小数点，则立即写入s2[i]，若遇算数运算符，将“ ”（空格）写入s2[i]；
4) 遇到左括号“(”则压栈；
5) 若遇算术运算符，如果它们的优先级比栈顶元素高，则直接进栈，否则弹出栈顶元素输出到s2[i]，直到新栈顶元素的优先级比它低，然后将它压栈；
6) 若遇到右括号“）”，则将栈顶元素输出到s2[i]，直到栈顶元素为“（”，然后相互抵消；
7) 当扫描到“#”符号，表明表达式串已全部输入，将栈中的运算符全部输出到s2[i]，并删除栈顶元素。
伪码算法：
void Translate(char *s1)
{ //中缀表达式转换为后缀表达式
char s2[80];
SqStack_c Optr;
int i=0,j=0;
char t;
InitStack_c(&Optr);//初始化一个存储字符型的空栈，便于存储运算符
Push_c(&Optr,'(');// 首先将左括号“(”压进栈，作为栈底元素
while(s1[i]!='#') //当扫描到的不是“#”，即表达式串没结束时
{
if(s1[i]>='0' && s1[i]<='9' || s1[i]=='.') //若果是数字或小数点则将其输出给s2[i]
{
s2[j++]=s1[i];
if((s1[i+1]<'0' || s1[i+1]>'9') && s1[i+1]!='.')
s2[j++]=' ';
}
else
switch(s1[i]) //扫描到的是运算符
{
case'(':Push_c(&Optr,s1[i]);break;// 遇到左括号“(”则压栈
case')':Pop_c(&Optr,&t); //若遇到右括号“）”，则将栈顶元素输出到s2[i]
while(t!='(') //直到栈顶元素为“（”，然后相互抵消
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
break;
default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))
{//遇到算数运算符则比较优先级
Pop_c(&Optr,&t);//栈顶元素优先级高，则弹出到s2[i]
s2[j++]=t;
}
Push_c(&Optr,s1[i]);//栈顶元素优先级低，直接压栈
}
i++;
}
Pop_c(&Optr,&t);
while(t!='(') //表达式串已结束，栈中的运算符全部输出到s2[i]，并删除栈顶元素
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
for(i=0;i<j;i++) //将s2复制给s1
s1[i]=s2[i];
s1[i]= '#';
s1[i+1]='\0';//为了方便打印后缀表达式，在字符串结尾加‘\0’
}
5、表示式求值运算的算法：
算法描述：
1） 读入无括号的后缀表达式；
2） 若为数值和小数点则将其联合转换为浮点型后进栈（存放操作数）；
3） 若为运算符，让栈顶元素和次顶元素与次运算符进行相应的运算，运算结果打印并进栈；
4） 重复2）3）步骤，直到输入为“#”，则此时栈中的结果便是所追求的表达式的值。
数值转换为实数的算法描述：
1） 若为数字，则将其减去'0'的ASCII码后就得到该数的数值，并暂存于一个变量m上；
2） 若继续为数字，也将其减去'0'的ASCII码后就得到该数的数值，并将其值加上已存的m*10后的值再存于m；
3） 重复2）步骤直到遇到小数点，从小数点后的数开始，在重复2）步骤的通知，也记下小数点后的位数n；
4） 当遇到“ ”（空格）后，即表示此轮需转换的数已读入完毕，则将m除以10的你次方，则此时的之记为转换后的实数。
伪码算法：
void Calculate(SqStack_f *s,char *s2)
{
float m,x,y,z;
int i=0,j=0;
while(s2[i]!='#')//读入后缀表达式直到“#”符号为止
{
if(s2[i]>='0' && s2[i]<='9' || s2[i]=='.') // 若为数值和小数点
//则将其联合转换为浮点型后进栈
{ //数值转换为实数
m=0;
while(s2[i]!=' ' && s2[i]!='.') //读入的只为数字
m=m*10+(float)(s2[i++]-'0');//转换为十进制的整数
if(s2[i]=='.')//遇到小数点后
{
j=0;i++;
while(s2[i]!=' ')
{
m=m*10+(float)(s2[i++]-'0');//转换为十进制的整数
j++; //记录小数点后的位数
}
while(j>0) //转换为实数
{
m/=10;
j--;
}
}
i++;
Push_f(s,m);
GetTop_f(s,&m);
printf("The result is:%g\n",m);
}
else //读入的为运算符
{
Pop_f(s,&x);//弹出栈顶元素
Pop_f(s,&y);//弹出次顶元素
switch(s2[i])
{//让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈
case '+':z=y+x;printf("The result is:%g\n",z);break;
case '-':z=y-x;printf("The result is:%g\n",z);break;
case '*':z=y*x;printf("The result is:%g\n",z);break;
case '/':if(x==0)
{//报错功能
printf("表达式出错，除数为‘0’，无意义\n");
exit(1);
}
else
{
z=y/x;
printf("The result is:%g\n",z);break;
}
case '^':z=1;for(j=1;j<=x;j++)
{//乘方的运算
z=z*y;
printf("The result is:%g\n",z);
}
}
Push_f(s,z);
i++;
}
}
}
6、结果输出的伪码算法：
void result(SqStack_f *s)
{
float v;
GetTop_f(s,&v);
printf("The final result is:%g\n",v);//以合适的形式输出结果，省去不必要的小数点
}
7、主程序的伪码算法：
void main()
{
SqStack_f stack;
char str[80],c='Y';
while(c=='y' || c=='Y')//判断是否继续本程序
{
printf("请输入算术表达式[本程序支持实数的加减乘除乘方运算]，结束前请输入‘#’号！\n");
gets(str);//输入表达式
InitStack_f(&stack);//初始化一个存储运算结果（实型）的栈
Translate(str);//调用“中缀表达式转换为后缀表达式函数”
printf("转化后的后缀表达式为：\n");//检验后缀表达式是否转换正确
puts(str);//输出后缀表达式
Calculate(&stack,str);//计算无括号表达式的值
result(&stack);//调用“结果输出函数”
printf("你想继续吗？'Y'或'y'为继续，其余为退出程序\n");//增加程序的连续输入功能
c=getchar();
getchar();//吞噬掉输入判断符后的‘\n’
}
}
8、函数的调用关系图
四、 调试分析
1、 在编程过程中，为了增加程序的实用性，将程序适用范围扩大到了实数型，并增加了连续输入功能；
2、 在编程过程中，为了增加程序的健壮性，在运算除法时，考虑到除数为“0”时的报错和及时退出；
3、 在调试过程中，最初一下子出来程序就出错，为了方便检查错误，故在主函数中增加了检查后缀表达式是否转换正确的函数，并在每一步计算都跟踪结果是否正确；
4、 从程序实验题的编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的栈的应用。本题中涉及两元素类型（字符型和浮点型）的栈，由于是面向过程的语言，故只能分别定义。
五、 用户使用说明
1、 本程序的运行环境为Windows7旗舰版操作系统，执行文件为：算术表达式求值.exe；
2、 进入程序后即显示提示信息：“请输入算术表达式[本程序支持实数的加减乘除乘方运算]，结束前请输入‘#’号！”以等待用户输入待求表达式，直到输入“#”为止，若用户输入的表达式为一个空字符串，则显示ERROR，程序结束；
3、 在用户正确输入表达式后，程序会自动将其转换为后缀表达式并输出“转化后的后缀表达式为：xxxxxxxx”，然后自动计算表达式的值并输出中间结果“The result is：xxxxx”和最终结果“The final result is:xxxx”；
4、 最终结果输出后，又有提示信息：“你想继续吗？'Y'或'y'为继续，其余为退出程序”，以等待用户输入是否继续运行本程序的命令符，若输入“y”或“Y”，则程序自动再次运行，重复2，3步，若输入其它，程序结束。
5、 本程序只对实数的加减乘除乘方运算进行求值，且只对“（）”这种形式的括号进行识别，“｛｝”或“[]”都不予以识别，表达式输入完后一定要加“#”表示输入结束。
六、 测试结果
1、 正确输入：12*（3.6/3+4^2-1）#
2、 无定义运算：12*（3.6/(2^2-4)+1）#
运行界面：
3、 错误输入：12+s#
运行界面：
以上结果与自己在进行程序概要分析时的余项结果一致
七、 心得体会
这次实验设计让我更加了解并更加灵活运用大一学到的C程序设计和这个学期学到的数据结构。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
这次实验设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上，或者将“i”打成“1”。就像我在写Calculate（）函数时，在进行数值转换时，一个“｝”放错了位置，让我纠结了很久。在写Translate（）函数时，switch（s1[i]）写成switch（s1[1]），很仔细的检查，花了一个多小时才发现次错误。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。
最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。
参考文献：
1.《数据结构(C语言版)》 严蔚敏 清华大学出版社
2.《C程序设计》 谭浩强 清华大学出版社
3.《数据结构题集（C语言版）》严蔚敏 吴伟民 米宁 清华大学出版社
4.《C程序设计学习指导与练习》贾伯琪 中国科学技术大学出版社
八、 附录
“表达式求值”源程序代码：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define TTACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
float *base;
float *top;
int stacksize;
}SqStack_f;
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack_c;
void InitStack_f(SqStack_f *s)
{
s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));
if(!s->base)
exit(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
void InitStack_c(SqStack_c *s)
{
s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char));
if(!s->base)
exit(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
void GetTop_f(SqStack_f *s,float *e)
{
if(s->top==s->base)
{
printf("ERROR!\n");
exit(1);
}
*e=*(s->top-1);
}
void GetTop_c(SqStack_c *s,char *e)
{
if(s->top==s->base)
{
printf("ERROR!\n");
exit(1);
}
*e=*(s->top-1);
}
void Push_f(SqStack_f *s,float e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));
if(!s->base)
{
printf("OVERFLOW!\n");
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*s->top++=e;
}
void Push_c(SqStack_c *s,char e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));
if(!s->base)
{
printf("OVERFLOW!\n");
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*s->top++=e;
}
void Pop_f(SqStack_f *s,float *e)
{
if(s->top==s->base)
exit(1);
*e=*--s->top;
}
void Pop_c(SqStack_c *s,char *e)
{
if(s->top==s->base)
exit(1);
*e=*--s->top;
}
int precede(char Top_char,char s1_char)
{
int i,pre[2];
char op[2];
op[0]=Top_char;
op[1]=s1_char;
for(i=0;i<2;i++)
switch(op[i])
{
case'(':case')':pre[i]=0;break;
case'+':case'-':pre[i]=1;break;
case'*':case'/':pre[i]=2;break;
case'^':pre[i]=3;break;
}
if(pre[0]>=pre[1])
return 1;
else
return 0;
}
void Translate(char *s1)
{
char s2[80];
SqStack_c Optr;
int i=0,j=0;
char t;
InitStack_c(&Optr);
Push_c(&Optr,'(');
while(s1[i]!='#')
{
if(s1[i]>='0' && s1[i]<='9' || s1[i]=='.')
{
s2[j++]=s1[i];
if((s1[i+1]<'0' || s1[i+1]>'9') && s1[i+1]!='.')
s2[j++]=' ';
}
else
switch(s1[i])
{
case'(':Push_c(&Optr,s1[i]);break;
case')':Pop_c(&Optr,&t);
while(t!='(')
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
break;
default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))
{
Pop_c(&Optr,&t);
s2[j++]=t;
}
Push_c(&Optr,s1[i]);
}
i++;
}
Pop_c(&Optr,&t);
while(t!='(')
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
for(i=0;i<j;i++)
s1[i]=s2[i];
s1[i]='#';s1[i+1]='\0';
}
void Calculate(SqStack_f *s,char *s2)
{
float m,x,y,z;
int i=0,j=0;
while(s2[i]!='#')
{
if(s2[i]>='0' && s2[i]<='9' || s2[i]=='.')
{
m=0;
while(s2[i]!=' ' && s2[i]!='.')
m=m*10+(float)(s2[i++]-'0');
if(s2[i]=='.')
{
j=0;i++;
while(s2[i]!=' ')
{
m=m*10+(float)(s2[i++]-'0');
j++;
}
while(j>0)
{
m/=10;
j--;
}
}
i++;
Push_f(s,m);
GetTop_f(s,&m);
printf("The result is:%g\n",m);
}
else
{
Pop_f(s,&x);
Pop_f(s,&y);
switch(s2[i])
{
case '+':z=y+x;printf("The result is:%g\n",z);break;
case '-':z=y-x;printf("The result is:%g\n",z);break;
case '*':z=y*x;printf("The result is:%g\n",z);break;
case '/':if(x==0)
{
printf("表达式出错，除数为‘0’，无意义\n");
exit(1);
}
else
{
z=y/x;
printf("The result is:%g\n",z);break;
}
case '^':z=1;for(j=1;j<=x;j++)
{
z=z*y;
printf("The result is:%g\n",z);
}
}
Push_f(s,z);
i++;
}
}
}
void result(SqStack_f *s)
{
float v;
GetTop_f(s,&v);
printf("The final result is:%g\n",v);
}
void main()
{
SqStack_f stack;
char str[80],c='Y';
while(c=='y' || c=='Y')
{
printf("请输入算术表达式[本程序支持实数的加减乘除乘方运算]，结束前请输入‘#’号！\n");
gets(str);
InitStack_f(&stack);
Translate(str);
printf("转化后的后缀表达式为：\n");
puts(str);
Calculate(&stack,str);
result(&stack);
printf("你想继续吗？'Y'或'y'为继续，其余为退出程序\n");
c=getchar();
getchar();
}
}