清华大学数据结构课程实验报告
(20 -20 学年 第 学期)
报告题目: 算术表达式求值
任课老师:
专 业:
学 号:
姓 名:
二0一 年 月 日
摘要:现代科学技术高速发展,各种高科技产品频频问世,而各种技术的基础都离不开基本的表达式求值,它虽然简单,但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构,从数据结构的角度看,它是一种特殊的线性表,具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构,利用算符优先法,来实现简单算术表达式的求值。
关键字:算符优先法;算术表达式;数据结构;栈
一、课题概述
1、问题描述
一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数,运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符,界限符有左括号“(”、右括号“)”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。
2、设计目的
(1)通过该算法的设计思想,熟悉栈的特点和应用方法;
(2)通过对算符优先法对算术表达式求值的算法执行过程的演示,理解在执行相应栈的操作时的变化过程。
(3)通过程序设计,进一步熟悉栈的基本运算函数;
(4)通过自己动手实现算法,加强从伪码算法到C语言程序的实现能力。
3、基本要求:
(1)使用栈的顺序存储表示方式;
(2)使用算符优先法;
(3)用C语言实现;
(4)从键盘输入一个符合要求的算术表达式,输出正确的结果。
4、编程实现平台
Microsoft Visual C++ 6.0
二、设计思路及采取方案
1、设计思路:
为了实现算符优先法,可以使用两个工作栈。一个称做OPTR,用以寄存运算符;另一个称做OPND,用以寄存操作数或运算结果。
算法的基本思想是:
(1)首先置操作数栈为空栈,表达式起始符“#”作为运算符栈的栈底元素;
(2)依次读入表达式中每个字符,若是操作数则进入OPND栈,若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#”)。
算法中还调用了两个函数。其中函数Precede是判定运算符栈顶运算符与读入的运算符之间优先关系的函数;函数Operate为进行二元运算的函数,如果是编译表达式,则产生这个运算的一组相应指令并返回存放结果的中间变量名;如果是解释执行表达式,则直接进行该运算,并返回运算结果。
2、方案设计
(1)抽象数据类型定义
ADT Stack{
数据对象:D={ | ∈ElemSet,i=1,2,…,n,, n≧0}
数据对象:R1={<, > | , ∈D,i=2,…,n}
约定端为栈顶,端为栈底。
基本操作:
InitStack(&S)
操作结果:构造一个空栈S。
GetTop(S)
初始条件:栈S已存在。
操作结果:用P返回S的栈顶元素。
Push(&S, e)
初始条件:栈S已存在。
操作结果:插入元素e为新的栈顶元素。
Pop(&S, e)
初始条件:栈S已存在。
操作结果:删除S的栈顶元素,并用e返回其值。
Precede(,)
初始条件:,为运算符。
操作结果:判断运算符优先权,返回表示优先权高低关系的“<”、“=”或“>”的字符。
Operate(a, OP, b)
初始条件:a, b为整数,OP为运算符。
操作结果:a与b进行运算,OP为二元运算符,返回其值。
}ADT Stack
(2)符号之间的优先权关系比较
<:的优先权低于:
=:的优先权等于
>:的优先权高于
(3)顺序栈的定义
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
(4)调用函数:
void InitStack(SqStack *S) //构造空栈
SElemType GetTop(SqStack *S) //用e返回栈顶元素
SElemType Push(SqStack *S, SElemType e) //插入e为新的栈顶元素
SElemType Pop(SqStack *S) //删除栈顶元素
int jiancha1(char e) //判断e是运算符还是运算数
void jiancha2(char e) //判断e是否为合法的运算符或运算数
SElemType Precede(char g, char h) //优先权比较
float Operate(float s,char yunsuanfu,float t) //返回二元运算结果
三、实验结果
测试表达式及对应运行结果
1、 “3+6#” 结果为9
2、 “(7-5)*3#” 结果为6
3、 “8/4#” 结果为2.
四、心得体会
1、算符优先法是教材上有关栈的应用的一个具体实例,考虑到算符优先法中对于运算符的操作是先入先出的,正好符合栈这种结构的存储使用规则,于是我们便可以利用栈来实现算法
2、由于教材上给出的存储结构定义、函数等都是伪码,不是可执行的程序代码,故需要从程序语言(C语言)角度考虑,将伪码转换成程序代码。而这是不是一个简单的工作。编写程序的过程需要非常的小心仔细,任何一个细小的错误,都会导致程序的运行失败。在写好程序第一次编译时,我的程序出现了将近80条错误,经过两天的检查、调试以及和同学的讨论,我的程序才最终通过编译,成功运行。比如在定义字符常量时,#define STACK_INIT_SIZE 100和#define STACKINCREMENT 10这两个语句的句末是不能加分号的,这个问题我花了两个多小时才发现。
3、经过自己动手编写这个有关栈的程序,我发现自己对栈的理解更加完全、更加深刻了。对于栈的逻辑结构、存储结构、操作函数、应用以及具体实现,我有一种豁然开朗的感觉。
4、此算法只能进行个位数的加减乘除运算,对两位及以上数不能操作,。因此算符优先法对算术表达式求值存在很大的局限性。若要完善算术表达式求值,应该完善算法,或者换用其它算法来实现。
五、参考文献
【1】严蔚敏,吴伟民. 数据结构(C语言版). 北京:清华大学出版社,2007
【2】李春葆. 数据结构教程(第3版)上机实验指导. 北京:清华大学出版社,2009
【3】谭浩强. C程序设计(第四版).北京:清华大学出版社
六、附录
C语言程序代码及部分注释
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
int flag=0; //flag标记输入字符是否合法
typedef struct
{
float *base;
float *top;
int stacksize;
}SqStack; //存放运算数的栈的顺序存储表示
typedef struct
{
char *base;
char *top;
int stacksize;
}sqStack; //存放运算符的栈的顺序存储表示
void InitStack(SqStack *S) //构造空栈(运算数栈)
{
S->base=(float*)malloc((STACK_INIT_SIZE)*sizeof(float));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void initStack(sqStack *S) //构造空栈(运算符栈)
{
S->base=(char*)malloc((STACK_INIT_SIZE)*sizeof(char));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
float GetTop(SqStack *S) //用e返回栈顶元素(运算数)
{
float e;
if(S->top==S->base) return ERROR;
e=*(S->top-1);
return e;
}
char getTop(sqStack *S) //用e返回栈顶元素(运算符)
{
char e;
if(S->top==S->base) return ERROR;
e=*(S->top-1);
return e;
}
float Push(SqStack *S,float e) //插入e为新的栈顶元素(运算数)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(float*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(float));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return e;
}
char push(sqStack *S,char e) //插入e为新的栈顶元素(运算符)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(char*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(char));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
(S->top)++;
return e;
}
float Pop(SqStack *S) //删除栈顶元素(运算数)
{
float e;
if(S->top==S->base) return ERROR;
(S->top)--;
e=*(S->top);
return e;
}
char pop(sqStack *S) //删除栈顶元素(运算符)
{
char e;
if(S->top==S->base) return ERROR;
(S->top)--;
e=*(S->top);
return e;
}
int jiancha1(char e) //判断e是运算符还是运算数
{
if(e!='+'&&e!='-'&&e!='*'&&e!='/'&&e!='('&&e!=')'&&e!='#')
return 1;
else return 0;
}
void jiancha2(char e) //判断e是否为合法的运算符或运算数
{
if(e==48||e==49||e==50||e==51||e==52||e==53||e==54||e==55||e==56||e==57) flag=1;
else if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#') flag=1;
else flag=0;
}
char Precede(char p,char q) //优先级比较函数
{
switch(p)
{
case'+':if((q=='*')||(q=='/')||(q=='(')) return'<';else return '>';break;
case'-':if((q=='*')||(q=='/')||(q=='(')) return'<';else return '>';break;
case'*':if(q=='(') return '<'; else return '>';break;
case'/':if(q=='(') return '<'; else return '>';break;
case'(':if(q==')') return '='; else if(q=='#') return ' '; else return '<';break;
case')':if(q=='(') return ' '; else return '>';break;
case'#':if(q=='#') return '='; else if(q==')') return ' '; else return '<';break;
default: printf("你的输入非法\n");
}
}
float Operate(float s,char yunsuanfu,float t) //二元运算操作
{
float r;
switch(yunsuanfu)
{
case'+':r=s+t;break;
case'-':r=s-t;break;
case'*':r=s*t;break;
case'/':if(t!=0)r=s/t;else printf("分母不能为零!");break;
default:printf("Sorry,您的输入有误!");
}
return r;
}
void main() //主函数部分
{
char c,x,theta;
float a,b;
sqStack OPTR;
SqStack OPND;
initStack(&OPTR);
push(&OPTR,'#');
InitStack(&OPND);
printf("输入一个以“#”结束的算数表达式:\n\n");
c=getchar();
jiancha2(c);
while(flag&&(c!='#'||getTop(&OPTR)!='#'))
{
if(jiancha1(c))
{
float cc;
cc=(float)(c-48);
Push(&OPND,cc);
c=getchar();
jiancha2(c);
}
else
{
x=Precede(getTop(&OPTR),c);
switch(x)
{
case'<':
push(&OPTR,c);
c=getchar();
jiancha2(c);
break;
case'=':
pop(&OPTR);
c=getchar();
jiancha2(c);
break;
case'>':
theta=pop(&OPTR);
b=Pop(&OPND);
a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
break;
}
}
}
if(flag==1) printf("\n计算所得结果是: %f\n",GetTop(&OPND));
else if(flag==0) printf("\nSorry,您的输入有错误!\n");
}