算术表达式求值-数据结构实验报告

1、word word 文档 可自由复制编辑清华大学数据结构课程实验报告（ 20 -20 学年 第 学期）报告题目：算术表达式求值任课老师： TOC o 1-5 h z 专业：学号：姓名：0一 年 月 日摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作。 栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值。关键字： 算符优先法；算术表达式；数据结构；栈一、课题概述1

2、、问题描述一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/ ”四种二元运算符，界限符有左括号“ （” 、右括号“） ”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。2、设计目的通过该算法的设计思想，熟悉栈的特点和应用方法；通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。通过程序设计，进一步熟悉栈的基本运算函数；通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力。3、基本要求：1）使用栈的顺序存储表示方式；2）使用算符优先法；3）用C语言实现；4）从键盘输入一个符合要

3、求的算术表达式，输出正确的结果。、编程实现平台Microsoft Visual C+ 6.0二、设计思路及采取方案1、设计思路：为了实现算符优先法，可以使用两个工作栈。一个称做OPTR，用以寄存运word 文档 可自由复制编辑word word 文档 可自由复制编辑算符；另一个称做OPN，用以寄存操作数或运算结果。D算法的基本思想是：( 1)首先置操作数栈为空栈，表达式起始符“#”作为运算符栈的栈底元素；( 2)依次读入表达式中每个字符，若是操作数则进入OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#

4、”) 。算法中还调用了两个函数。其中函数Precede是判定运算符栈顶运算符1与读入的运算符2 之间优先关系的函数；函数Operate 为进行二元运算a b 的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。2、方案设计( 1)抽象数据类型定义ADT Stack数据对象：D= ai | ai ElemSet,i=1,2, ,n, n 0数据对象：R1= | ai , ai 1 D， i=2, ,n约定 an 端为栈顶，ai 端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。GetTop

5、(S)初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push(&S, e)初始条件：栈S已存在。操作结果：插入元素e 为新的栈顶元素。Pop(&S, e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并用e 返回其值。Precede( c1 , c2)初始条件：c1 , c2为运算符。操作结果：判断运算符优先权，返回表示优先权高低关系的“”的字符。Operate（a, OP, b）初始条件：a, b 为整数，OP为运算符。操作结果：a 与 b 进行运算，OP为二元运算符，返回其值。ADT Stack（ 2）符号之间的优先权关系比较1 2 ：1 的优先权高于221+-*/()#+-*

6、/(#=（ 3）顺序栈的定义typedef structSElemType *base;SElemType *top;int stacksize;SqStack;( 4)调用函数：构造空栈用 e 构造空栈用 e 返回栈顶元素/ 插入 e为新的栈顶元素SElemType GetTop(SqStack *S)/SElemType Push(SqStack *S, SElemType e)SElemType Pop(SqStack *S) int jiancha1(char e) / void jiancha2(char e) /SElemType Precede(char g, char h)/删

7、除栈顶元素判断/删除栈顶元素判断e 是运算符还是运算数判断e 是否为合法的运算符或运算数/ 优先权比较/ 返回二元运算结果三、实验结果测试表达式及对应运行结果2、“（ 7-5） *3#” 结果为 63、2、“（ 7-5） *3#” 结果为 63、“ 8/4# ” 结果为 2.、 算符优先法是教材上有关栈的应用的一个具体实例，考虑到算符优先法中对于运算符的操作是先入先出的，正好符合栈这种结构的存储使用规则，于是我们便可以利用栈来实现算法由于教材上给出的存储结构定义、函数等都是伪码，不是可执行的程序代码，故需要从程序语言（C 语言）角度考虑，将伪码转换成程序代码。而这是不是一个简单的工作。编写程序

8、的过程需要非常的小心仔细，任何一个细小的错误，都会导致程序的运行失败。在写好程序第一次编译时，我的程序出现了将近 80 条错误， 经过两天的检查、调试以及和同学的讨论，我的程序才最终通过编译，成功运行。比如在定义字符常量时，#define STACK_INIT_SIZE1 00和 #define STACKINCREMENT 这两个语句的句末是不能加分号的，这个问题10我花了两个多小时才发现。经过自己动手编写这个有关栈的程序，我发现自己对栈的理解更加完全、更加深刻了。对于栈的逻辑结构、存储结构、操作函数、应用以及具体实现，我有一种豁然开朗的感觉。 TOC o 1-5 h z 此算法只能进行个位

9、数的加减乘除运算，对两位及以上数不能操作，。因此算符优先法对算术表达式求值存在很大的局限性。若要完善算术表达式求值，应该完善算法，或者换用其它算法来实现。五、参考文献1 】严蔚敏，吴伟民. 数据结构（C 语言版）. 北京：清华大学出版社，20072】 李春葆 . 数据结构教程（第 3 版） 上机实验指导. 北京： 清华大学出版社，20093】谭浩强. C 程序设计（第四版）. 北京：清华大学出版社六、附录C语言程序代码及部分注释#include#include#define ERROR 0;#define STACKINITSIZE 100#define STACKINCREMENT 10in

10、t flag=0;/flag标记输入字符是否合法int flag=0;/flag标记输入字符是否合法typedef structfloat *base;float *top;int stacksize;typedef structfloat *base;float *top;int stacksize;SqStack; / typedef struct char *base;char *top;int stacksize;sqStack; /存放运算数的栈的顺序存储表示存放运算符的栈的顺序存储表示void InitStack(SqStack *S)/构造空栈(运算数栈)S-base=(floa

11、t*)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)/用 float GetTop(SqStack *S)/用 e 返回栈顶元素（运算数）float e;if(S-top=S-bas

12、e) return ERROR;e=*(S-top-1);return e;用 e 返回栈顶元素（运算符）用 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+STACKINCREMEN T)*sizeof(float);S-top=S-base+S-stacks

13、ize;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 *

14、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

15、) /判断 e 是否为合法的运算符或运算数if(e=48|e=49|e=50|e=51|e=52|e=53|e=54|e=55|e=56|e=57) flag=1;elseif(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;break;case-:if(q=*)|(q=/)|(q=()return;break; case*:if(q=() return ;break;case/:if(q=()

16、return ;break;case(:if(q=) return =; else 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) /二元运算操作word 文档 可自由复制编辑word word 文档 可自由复制编辑float r;switch(yunsuanfu)case+:r=s+t;break;cas

17、e-: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( 输入一个以“#”结束的算数表达式:nn);c=getchar();jiancha2(c);while(flag&(c!=#|getTop(&OPTR)!=#)if(jiancha1(c)float cc;