数据结构程序设计---求解算术表达式

1、数据结构课程设计题 目 求解算术表达式 姓 名 吴楚杰 汤友松 杨基长 徐涛 杨剑学 号 33 30 36 35 37 系 别 计算机系 专 业 网络工程 级 别 2008 班 级 二班 2009年 12 月 30日 一、问题描述：设计一个程序，求解算术表达式。【基本要求】以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。二、问题分析：1）   数据结构描述1、为了实现算符优先算法使用两个工作栈，一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。2、在操作数和操作符入栈前，通过一个函数来判别，输入的

2、是操作数还是操作符，操作数入OPND，操作符入OPTR。3、 开始将#入操作符栈，通过一个函数来判别算术运算符的优先级。且规定#的优先级最低。在输入表达式的最后输入#，代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈。遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。 4、通过字符型数组的比较 确定进入工作界面的密码。原始密码已经定了，但是注册的密码

3、由一个数组来保存。再次登录的时候就可以通过比较原始密码和注册码来决定是否进入。而且登陆次数限定在三次，错误次数也限定在三次。这样就人性化的允许犯错，但是又可以防止不法分子的偷盗行为。2）主要算法流程描述：1、栈的节构体形式typedef struct Sqstack/计算数的结构体 elemtype *top;/栈顶指针 elemtype *base;/栈底指针 elemtype stacksize;/栈的大小Sqstack,*Linklist;/机构体名和结构体指针typedef struct Sqstack1/计算符的结构体 char *top; char *base; elemtype

4、stacksize;Sqstack1,*Linklist1;2、栈的初始化elemtype initstack(Linklist s)/初始化栈 s->base=(elemtype*)malloc(stack_size*sizeof(elemtype); if(!s->base) return ERROR ; s->top=s->base; s->stacksize=stack_size; return OK;elemtype initstack1(Linklist1 s)/初始化栈 s->base=(char*)malloc(stack_size*size

5、of(char); if(!s->base) return ERROR ; s->top=s->base; s->stacksize=stack_size; return OK;3、入栈elemtype push(Linklist s,elemtype e)/进栈 if(s->top-s->base>=s->stacksize) s->base=(elemtype*)realloc(s->base,(s->stacksize+stack_increasement)*sizeof(elemtype); if(!(s->bas

6、e) return 0; s->top=s->base+s->stacksize; s->stacksize+=stack_increasement; *(+s->top)=e; return 1;elemtype push1(Linklist1 s,char e)/进栈if(s->top-s->base>=s->stacksize) s->base=(char*)realloc(s->base,(s->stacksize+stack_increasement)*sizeof(char); if(!(s->base)

7、 return 0; s->top=s->base+s->stacksize; s->stacksize+=stack_increasement; *(+s->top)=e; return 1;4、取栈顶元素elemtype gettop(Sqstack s)/取栈顶元素 elemtype e; if(s.top=s.base) printf("No number left !"); return ERROR; e=*s.top; return e; char gettop1(Sqstack1 s)/取字符栈顶元素 char e; if(s.t

8、op=s.base)/判断有无字符 printf("No number left !"); return ERROR; e=*s.top; return e; 5、栈的优先级判断及其函数 +        -        *         /         

9、60;    (         )        #   +   -   *   /     (   )  #>        >    

10、0;   <        <       <         <        >       >>        >&

11、#160;       <        <       <         <        >       >>   

12、60;    >        >        >       <         <        >       &g

13、t;>        >        >        >       <         <        >  

14、     >>        >        >        >       >         <     &#

15、160;  >       ><        <        <        <       <         < 

16、;       =>        >        >        >        >           

17、60;     >       ><        <        <        <        <      

18、;  <                =运算符的优先级判断函数：char precede(char top,char c)/top为操作符的栈顶元素，c为当前输入操作符，若c的优先级大于top返回'<',c的优先级小于top'>'，c与top构成括号匹配返回'=' char result; switch(c) case '#':result='&

19、gt;'break; case '+': case '-':if(top='#'|top='(') result='<' else result='>'break; case '*': case '/':if(top='*'|top='/')result='>' else result='<'break; case ')':if(top='('

20、;)result='=' else result='>'break; case '(': result='<'break; default: printf("the operater is out of band.n"); / switchreturn result;6、具体运算函数elemtype operate(elemtype a,char theta,elemtype b)/计算式的计算 elemtype result; switch(theta) case '+': res

21、ult=a+b;break; case '-': result=a-b;break; case '*': result=a*b;break; case '/':if(b=0)/特殊计算特殊处理 printf("分母为0,the result is errorn"); result=0; else result=a/b;break;default: printf("nThe operater is wrong.n"); return result;7、运算主函数elemtype evaluate(Linkli

22、st opnd,Linklist1 optr) elemtype flag=0;/当flag为0时表示上一个输入的是字符符号，当其为1时表示上一个输入的是数字字符 elemtype a,l,f; char theta,c,e; c=getchar(); while(c!='#'|gettop1(*optr)!='#')/当不是终止符或者是开始符时继续 if(!In(c)/c若为操作数则入opnd栈 if(flag=1)/将连续输入的字符数字转换成相应的int类型 f=pop(opnd); push(opnd,(f*10+(c-48); else push(opn

23、d,c-48);/将单个的字符数字转换生相应的int类型 flag=1; c=getchar(); else flag=0; switch(precede(gettop1(*optr),c) case '<': push1(optr,c); c=getchar();break; case '=': e=pop1(optr); c=getchar();break; case '>': theta=pop1(optr); l=pop(opnd); a=pop(opnd);/从栈中取得计算元素 push(opnd,operate(a,the

24、ta,l);/将元素计算后压入栈中 break;/switch/if/while return pop(opnd);8、为了更加丰富本课程设计特增加注册与登录函数（1）登录函数，其中包含原始密码“xnxy2008”elemtype denglu( )/登录(以一个比较函数来核对其身份)elemtype i, g=3;while(g) printf("Please enter your password .n"); for(i=0;i<9;i+) di=getch(); if(di!='r') printf("*"); else di

25、='0'break; if(strcmp(b,d)=0|(k=1&&strcmp(c,d)=0) return 1; break; g-; return 0;(2)注册函数elemtype zhuce( )/注册以一个比较函数来确定密码elemtype i; printf("tttPlesae enter you uername!n");scanf("%s",h);do printf("tttPlease enter your password:n"); /输入密码被函数getch吸收到数组以*号形式显

26、示出来 for(i=0;i<9;i+) ci=getch(); if(ci!='r') printf("*"); else ci='0' break; printf("ntttPlease enter your password again!n"); for(i=0;i<9;i+) di=getch(); if(di!='r') printf("*"); else di='0' break; if(strcmp(c,d)=0) printf("ntt

27、tCongratulations!nWelcome %s !n",h); k=1; return 1; break; else printf("tttPlesae try again!n");while(1);三、程序源代码：#include "stdio.h"#include"stdlib.h"#include"malloc.h"#include"conio.h"#include"string.h"#define stack_size 100#define sta

28、ck_increasement 10 #define OK 1#define ERROR 0typedef int elemtype ;char b9="xnxy2008",r9,d9,h20;elemtype k=0;typedef struct Sqstack/计算数的结构体 elemtype *top; elemtype *base; elemtype stacksize;Sqstack,*Linklist;typedef struct Sqstack1/计算符的结构体 char *top; char *base; elemtype stacksize;Sqstack

29、1,*Linklist1;elemtype initstack(Linklist s)/初始化栈 s->base=(elemtype*)malloc(stack_size*sizeof(elemtype); if(!s->base) return ERROR ; s->top=s->base; s->stacksize=stack_size; return OK;elemtype initstack1(Linklist1 s)/初始化栈 s->base=(char*)malloc(stack_size*sizeof(char); if(!s->base

30、) return ERROR ; s->top=s->base; s->stacksize=stack_size; return OK;elemtype gettop(Sqstack s)/取栈顶元素 elemtype e; if(s.top=s.base) printf("No number left !"); return ERROR; e=*s.top; return e; char gettop1(Sqstack1 s)/取栈顶元素 char e; if(s.top=s.base) printf("No number left !&quo

31、t;); return ERROR; e=*s.top; return e; elemtype push(Linklist s,elemtype e)/进栈 if(s->top-s->base>=s->stacksize) s->base=(elemtype*)realloc(s->base,(s->stacksize+stack_increasement)*sizeof(elemtype); if(!(s->base) return 0; s->top=s->base+s->stacksize; s->stacksize

32、+=stack_increasement; *(+s->top)=e; return 1;elemtype push1(Linklist1 s,char e)/进栈 if(s->top-s->base>=s->stacksize) s->base=(char*)realloc(s->base,(s->stacksize+stack_increasement)*sizeof(char); if(!(s->base) return 0; s->top=s->base+s->stacksize; s->stacksize+

33、=stack_increasement; *(+s->top)=e; return 1;elemtype pop(Linklist s)/去栈顶元素 elemtype e; if(s->top=s->base) return ERROR; else e=*s->top; s->top-; return e;char pop1(Linklist1 s)/去栈顶元素 char e; if(s->top=s->base) return ERROR; else e=*s->top; s->top-; return e;char precede(ch

34、ar top,char c)/top为操作符的栈顶元素，c为当前输入操作符，若c的优先级大于top返回'<',c的优先级小于top'>'，c与top构成括号匹配返回'=' char result; switch(c) case '#':result='>'break; case '+': case '-':if(top='#'|top='(') result='<' else result='>&#

35、39;break; case '*': case '/':if(top='*'|top='/')result='>' else result='<'break; case ')':if(top='(')result='=' else result='>'break; case '(': result='<'break; default: printf("the opera

36、ter is out of band.n"); / switchreturn result; elemtype operate(elemtype a,char theta,elemtype b)/计算式的计算 elemtype result; switch(theta) case '+': result=a+b;break; case '-': result=a-b;break; case '*': result=a*b;break; case '/':if(b=0)/特殊计算特殊处理 printf("分母为0

37、,the result is errorn"); result=0; else result=a/b;break;default: printf("nThe operater is wrong.n"); return result;elemtype In(char c) /判断输入字符是否为运算符,返回1，则c为操作符，返回0则c不是操作符 char p8="+-*/()#" elemtype i=0; while(pi!='0') if(pi=c) return 1; i+; return 0;elemtype evaluat

38、e(Linklist opnd,Linklist1 optr) elemtype flag=0;/当flag为0时表示上一个输入的是字符符号，当其为1时表示上一个输入的是数字字符 elemtype a,l,f; char theta,c,e; c=getchar(); while(c!='#'|gettop1(*optr)!='#')/当不是终止符或者是开始符时继续 if(!In(c)/c若为操作数则入opnd栈 if(flag=1)/将连续输入的字符数字转换成相应的int类型 f=pop(opnd); push(opnd,(f*10+(c-48); else

39、push(opnd,c-48);/将单个的字符数字转换生相应的int类型 flag=1; c=getchar(); else flag=0; switch(precede(gettop1(*optr),c) case '<': push1(optr,c); c=getchar();break; case '=': e=pop1(optr); c=getchar();break; case '>': theta=pop1(optr); l=pop(opnd); a=pop(opnd);/从栈中取得计算元素 push(opnd,opera

40、te(a,theta,l);/将元素计算后压入栈中 break;/switch/if/while return pop(opnd); elemtype zhuce( )/注册以一个比较函数来确定密码elemtype i; printf("tttPlesae enter you uername!n");scanf("%s",h);do printf("tttPlease enter your password:n"); /输入密码被函数getch吸收到数组以*号形式显示出来 for(i=0;i<9;i+) ri=getch();

41、if(ri!='r') printf("*"); else ri='0' break; printf("ntttPlease enter your password again!n"); for(i=0;i<9;i+) di=getch(); if(di!='r') printf("*"); else di='0' break; if(strcmp(r,d)=0) printf("ntttCongratulations!ntWelcome %s !n&qu

42、ot;,h); k=1; return 1; break; else printf("tttPlesae try again!n");while(1);elemtype denglu( )/登录(以一个比较函数来核对其身份)elemtype i, g=3;while(g) printf("Please enter your password .n"); for(i=0;i<9;i+) di=getch(); if(di!='r') printf("*"); else di='0'break; if

43、(strcmp(b,d)=0|(k=1&&strcmp(r,d)=0)/是原始密码或者已经注册 return 1; break; else printf("ntERROR INPUT !nttt"); g-; return 0;void main() elemtype n,m=0,flag=3,result;Sqstack opnd0;Sqstack1 optr0; Linklist opnd;/操作数栈 Linklist1 optr;/操作符栈opnd=&opnd0; optr=&optr0; do printf("Please

44、make a choice !ntt 0:注册；t1:登录。"); printf("n"); scanf("%d",&n); printf("n"); if(n=0) m=zhuce( ); else if(n=1) m=denglu( ); else flag-; printf("Error Iuput !"); while(flag&&!m); getchar(); while(m=1) initstack1(optr); initstack(opnd); push1(optr

45、,'#'); printf("n*n"); printf("nnn Please input the 运算表达式，以'#'结尾nnn"); printf("n*n"); result=evaluate(opnd,optr); printf("ntThe result is %dnn",result); getchar(); 四、使用说明：(一)登陆界面1：登陆界面2：（二）输入运算表达式可能结果1:可能结果2：五、调试分析说明：1、输入的操作数和操作码由于是字符串类型的，在原设计中实

46、现的操作都是对个位数实现的。由于仅是对个位数的运算，实用性不大，故在后来的设计中，通过一个标志flag实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算。2、本设计的关键是运算符优先级的判断，由于优先级的错判，很容导致结果的运算错误。 要明晰判断当前运算符和运算符栈栈顶元素的先后顺序，这个易出错误。3、在本次设计中充分利用了，栈先进后出的特点。4、该设计的内存分配：初始化栈时，每个栈分配100个内存单元，如果不够用，以后每次可增加10个动态内存单元。5、由于程序比较长，在调试期间，可以再每个调用函数中加上printf语句，通过观察程序的运行过程，理由查找错误，和改进程序。6、程序时

47、间复杂度为O（n）；7、该设计，自顶向下，分层设计，将每个功能模块化，简洁明了。8、经验体会：借助DEBUG调试器和数据观察窗口，可以加快找到程序的瑕点9、要注意在算数运算中，除数不能为0，在开始的设计中没有注意到这一点。10、在表达式的运算中，要注意输入的是字符串，应将其转换为相应的整形类型的数据再进行运算。否则将出错。并且应当操作数的出栈顺序，以及相应的运算顺序，先出栈的为第二操作数，第二次出栈的为第一操作数。 11、设计的登录函数和注册函数使得只有在注册或者知道原始密码的情况下才可以登录到操作界面，从而保证了设计的技术权威性。六、特色及改进设想；本程序适用于基础的四则运算，但不是用于像乘

48、方之类的运算，这是他的一个大弊端，为了解决这个问题我们还得继续进行研究。在各个运算处加入之类的运算，调用到数学函数库中的的POW（）等函数。为了使得本设计更实用一些，特意设计登录函数及注册函数，如此可以增加本设计的全面性。七、程序的产生该程序是由我们这个团体的所有成员分工合作，辛勤劳动的结果。我们不否认从网上有过摘抄，但是更多的是我们的汗水与对知识的总结。在形成过程中我们先是一起讨论，之后是有人负责密码部分，也有人负责基本函数部分，还有人负责主要函数部分，重要的是有人负责总体的安排与调试。这使得我们学会了团队合作的重要性。坚信：团结就是力量。八、综合设计过程，做出总结；（1）总结人:杨剑（学号

49、：200814160237） 通过这个学期对数据结构的学习，我获益匪浅。特别是在学栈的时候我学的很认真。因而这次课程设计我可以较为轻易的解决。但是这次的课程设计我还是 碰到了几个难题。其一,如何处理栈的构建问题，由于输进去的有数字也有字符所以这里的有一个判断。我起初试图用一个初始函数去解决，因为我认为Int型的应该可以容纳字符型的，但是解决不了。其二，就是函数调用时候的地址问题。这次的课程设计中的函数并非全部都得用地址，譬如Gettop（）函数他就不需要用；而Top（）函数却得用。这时因为Top（）函数的改变栈的存储的内容而Gettop（）则不用。第三，做事得有条理 ，分清主次，有强烈的逻辑性

50、。第四，由于运行环境的问题，我们该程序得加上几个 Gerchar()函数，这还是一个不懂的地方，因为对于这个环境（C/C+程序设计学习与试验系统）还是第一次碰到这个问题。总之，这次设计对我的数据结构及C 语言有个综合性的考察，让我对他们了解的更加透彻。并且大大加深了我的我的专业的学习热情。我期待来年的学习使对计算机的了解更加透彻！（2）杨基长（200814160236）经过两个星期的实习，过程曲折可谓一语难尽。在此期间我们也失落过，也曾一度热情高涨。从开始时满富盛激情到最后汗水背后的复杂心情，点点滴滴无不令我回味无长。生活就是这样，汗水预示着结果也见证着收获。劳动是人类生存生活永恒不变的话题。

51、通过实习，我才真正领略到“艰苦奋斗”这一词的真正含义。我想说，设计确实有些辛苦，但苦中也有乐，在如今单一的理论学习中，很少有机会能有实践的机会，但我们可以，而且设计也是一个团队的任务，一起的工作可以让我们有说有笑，相互帮助，配合默契，多少人间欢乐在这里洒下，大学里一年的相处还赶不上这十来天的合作，我感觉我和同学们之间的距离更加近了；我想说，确实很累，但当我们看到自己所做的成果时，心中也不免产生兴奋； 正所谓“三百六十行，行行出状元”。我们同样可以为社会作出我们应该做的一切，这有什么不好？我们不断的反问自己。也许有人不喜欢这类的工作，也许有人认为设计的工作有些枯燥，但我们认为无论干什么，只要人生活的有意义就可。社会需要我们，我们也可以为社会而工作。既然如此，那还有什么必要失落呢？于是我们决