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

1、北京理工大学珠海学院数据结构课程设计报告题目算术表达式求值所在学院:专业班级:学生姓名:指导教师:2010年05月26日目录1 前 言12 概要设计 12.1数据结构设计12.2 算法设计12.3 ADT 描述22.4 功能模块分析 23 .详细设计 33.1数据存储结构设计 33.2主要算法流程图（或算法伪代码） 34 .软件测试 65.心得体会 8参考文献 8附录 8北京理工大学珠海学院计算机科学技术学院1 .前言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级， 又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实

2、现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为 +、-*、/,用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。2. 概要设计2.1数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置

3、，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1,删除栈顶元素时，指针 top减1。2.2算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。1. 首先置操作数栈为空栈，表达式起始符”# ”为运算符栈的栈底元素；2. 依次读入表达式，若是操作符即进OPND栈，若是运算符则和 OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即 OPTR栈的栈顶元素和当前读入的字符均为”#”）。2.3 ADT描述ADT Stack数据对象

4、：D= ai |ai ElemSet,i=1,2, , , n, n 仝 0数据对象：R仁< ai ,ai J>|aiJ,a D ,i=2, , n约定an端为栈顶，ai端为栈底。基本操作：Ini tStack(&S)操作结果：构造一个空栈SoGetTop(S)初始条件：栈S已存在。操作结果：用 P返回S的栈顶元素。Push(&S, ch)初始条件：栈S已存在。操作结果：插入元素 ch为新的栈顶元素。Pop(&S)初始条件：栈S已存在。操作结果：删除 S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1, c2)初始

5、条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。nu m( n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。ADT Stack2.4功能模块分析1栈的基本功能。InitStack(Stack *s)和 InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(Stack *s,charch)运算符栈插入 ch为新的栈顶元素，Push2(Stack2 *s,int ch)

6、操作数栈插入 ch为新的栈顶元素，Pop(Stack *s)删除运算符栈s的栈顶元素，用p返回其值，Pop2(Stack2 *s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stack s)用p返回运算符栈s的栈顶元素，GetTop2(Stack2 s)用p返回操作数栈 s的栈顶元素。2其它功能分析。(1) In (char ch)判断字符是否是运算符功能，运算符即返回1,该功能只需简单的一条语句即可实 现，return(ch='+'|ch='-'|ch='*'|ch=7'|ch='('|ch=')

7、9;|ch='#')。(2) Precede(char c1,char c2)判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。(3) Operate。nt a,char op,int b)操作数用对应的运算符进行运算功能。运算结果直接返回。(4) num(int n)求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。(5) EvalExpr()主要操作函数运算功能。分析详细见“3详细设计，3.2”。3. 详细设计char类型栈，不能满足2位以3.1数据存储结构设计因为表达式是由操作符，运算符和界限符组成

8、的。如果只用一个上的整数，所以还需要定义一个int类型的栈用来寄存操作数。/*定义字符类型栈*/typedef structint stacksize;char *base;char *top; Stack;/*定义整型栈 */typedef structint stacksize;int *base;int *top; Stack2;3.2主要算法流程图(或算法伪代码)1. Precede(char c1,char c2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+><<<<>>->><<<&

9、gt;>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=表1算法伪代码如下：char Precede(char c1,char c2)static char array49=>'5'>'5'<'5'<'5'<','>'1 !'>'15>

10、'5'>'5'<'5'<'5'<','>'1 !'>'1 5>'5'>'5'>'5'>'5'<','>'1 !'>'1 5>'5'>'5'>'5'>'5'<','>'1 !'>

11、'1 5<'5'<'5'<'5'<'5'<',1 _ !'!'1 ，>'5'>'5'>'5'>'5'!''>'5'>'5<'5'<'5'<'5'<'5'<','!'1 ，'=' /用一维数组存储49种

12、情况switch(cl)/* i为下面array的横标*/case '+' : i=O;break;case '-' : i=1;break;case '*' : i=2;break;case T : i=3;break;case '(' : i=4;break;case ')' : i=5;break;case '#' : i=6;break;switch(c2)/* j为下面array的纵标*/case '+' : j=0;break;case '-' : j=1

13、;break;case '*' : j=2;break;case T : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#' : j=6;break;return (array7*i+j); /*返回运算符 array7*i+j为对应的 c1,c2 优先关系 */2. int EvalExpr()主要操作函数。算法概要流程图:char匚三表达式首字符a第7页北京理工大学珠海学院计算机科学技术学院case 4 进操作符栈c =中屮+;case心进操作符栈尸*ptr

14、+；进操作数栈C-*第#页北京理工大学珠海学院计算机科学技术学院IretumGetTop2(OPND) 操作数栈头2个数进行 运算4第#页北京理工大学珠海学院计算机科学技术学院第#页北京理工大学珠海学院计算机科学技术学院利用该算法对算术表达式3*(7-2)求值操作过程如下:步骤OPTR 栈OPND 栈输入字符主要操作1#3*(7-2)#PushQPND,''2#3*(7-2)#Push(OPTR,''3#*3(7-2)#Push(OPNR,'(')4#*(37-2)#PushQPND,''5#*(3 7-2)#Push(OPNR,

15、'-')6#*(-3 72)#PushQPND,''7#*(-3 7 2)#Operate( 7','-',''8#*(3 5)#Pop(OPTR)9#*3 5#Operate( 3',' ',5')10#15#Return(GetTop2(OPND)表2算法伪代码如下：int EvalExpr()主要操作函数 c = *ptr+;while(c!='#'|GetTop(OPTR)!='#')if(!In(c) /不是运算符即进栈 if(!I n(*(ptr-

16、1) ptr=ptr-1; m=atoi(ptr);取字符串前面的数字段 n=num (m);Push2(&OPND,m);ptr=ptr+ n;c=*ptr+;elseswitch(Precede(GetTop(OPTR),c)case '<': 栈顶元素优先权底Push(&OPTR,c);c = *ptr+;break;case '=': 脱括号并接收下一字符x=Pop(&OPTR);c = *ptr+;break;case '>':/退栈并将运算结果入栈theta=Pop(&OPTR);b=Pop

17、2(&OPND); a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b);break;4. 软件测试运行成功后界面。第#页北京理工大学珠海学院计算机科学技术学院第9页北京理工大学珠海学院计算机科学技术学院2.输入正确的表达式后。S3農惠鑼麴譬式叹”结尾Press any key to continue3.更改表达式，输入有 2位数的整数调试。第#页北京理工大学珠海学院计算机科学技术学院5. 心得体会这次课程设计让我更加了解大一学到的 C和这个学期学到的数据结构。课设题目要 求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的

18、思维和动手能力和 更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写 EvalExpr()函数时，忘了指针的地址符值不用加*号，这一点小小的 错误也耽误了我几十分钟，所以说细节很重要。程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到 C语言具有的语句简洁，使用灵活，执

19、行效率高等特点。发现上机的重要作用，特别算术 表达式有了深刻的理解。这个程序是我们3个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致导致整项 工作的失败。实习中只有一个人知道原理是远远不够的， 必须让每个人都知道，否则一个 人的错误，就有可能导致整个工作失败。团结协作是我们成功的一项非常重要的保证。而 这次课程设计也正好锻炼我们这一点，这也是非常宝贵的最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。参考文献：1数据结构(C语言版)严蔚敏 清华大学出版社1. C语言程序设计 丁峻岭中国铁道出版社2.

20、 C程序设计谭浩强清华大学出版社附录程序源代码:#in elude <stdio.h>#in elude <stdlib.h>#in elude <stri ng.h>#defi ne NULL 0#defi ne OK 1#defi ne ERROR -1#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 20/*定义字符类型栈*/typedef structint stacksize;char *base;char *top; Stack;/*定义整型栈 */typedef structint stac

21、ksize;int *base;int *top; Stack2;/* 全局变量*/Stack OPTR;/*定义运算符栈*/Stack2 OPND; /*定义操作数栈 */char expr255 = "" /*存放表达式串*/char *ptr = expr;int InitStack(Stack *s) / 构造运算符栈s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!s->base) return ERROR;s->top=s->base;s->stacksize=STACK

22、_INIT_SIZE;return OK;int InitStack2(Stack2 *s) / 构造操作数栈s->base=(i nt *)malloc(STACK_INIT_SIZE*sizeof(i nt);if(!s->base) return ERROR;s->stacksize=STACK_INIT_SIZE;s->top=s->base;return OK;int ln(char ch) /判断字符是否是运算符，运算符即返回1return(ch='+'|ch='-'|ch='*'|ch=7'|c

23、h='('|ch=')'|ch='#');int Push(Stack *s,char ch) /运算符栈插入 ch为新的栈顶元素*s_>top=ch;s_>top+;return 0;int Push2(Stack2 *s,int ch)/操作数栈插入 ch为新的栈顶元素*s->top=ch;s->top+;return 0;char Pop(Stack *s) /删除运算符栈s的栈顶元素，用p返回其值char p;s->top-;p=*s->top;return p;int Pop2(Stack2 *s)/

24、删除操作数栈s的栈顶元素，用p返回其值int p;第15页北京理工大学珠海学院计算机科学技术学院第#页北京理工大学珠海学院计算机科学技术学院s->top-;p=*s->top;return p;char GetTop(Stack s)用p返回运算符栈char p=*(s.top-1);return p;int GetTop2(Stack2 s) / 用 p 返回操作数栈int p=*(s.top-1);return p;/*判断运算符优先权，返回优先权高的char Precede(char c1,char c2)int i=O,j=O;static char array49=

25、9;>', '>', '<', '<', '<', '>', '>','>', '>', '<', '<', '<', '>', '>','>', '>', '>', '>', '<', &

26、#39;>', '>',s的栈顶元素s的栈顶元素*/第17页北京理工大学珠海学院计算机科学技术学院5555555555555 55555 555?J，switch(cl)/* i为下面array的横标*/case '+' : i=O;break;case '-' : i=1;break;case '*' : i=2;break;case '/' : i=3;break;case '(' : i=4;break;case ')' : i=5;break;case &

27、#39;#' : i=6;break;switch(c2)/* j为下面array的纵标*/case '+' : j=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#' : j=6;break;return (array7*i+j); /*返回运算符*/*操作函数*/int Operate(i nt a,char op,i nt b)switch(op)case '+' : retur n (a+b);case '-' : return (a-b);case '*' : return (a*b);case '/' : return (a/b);return 0;int num(int n)返回操作数的长