《栈的表达式求值 数据结构优秀课程设计》由会员分享，可在线阅读，更多相关《栈的表达式求值 数据结构优秀课程设计（16页珍藏版）》请在金锄头文库上搜索。
1、栈的表达式求值1设计的目的（1）较熟练地掌握C语言的基本内容及程序设计的基本方法与编程技巧。（2）较熟练地掌握在系统上编辑、编译、连接和运行C程序的方法。（3）通过设计一个完整程序，掌握数据结构的算法编写、类C语言算法转换成C程序 并上机调试的基本方法。2 课程设计方案论证2.1设计思路表达式求值是程序设计语言编译中的一个基本问题。它的实现是栈应用的一个典型 例子。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值， 首先要能正确解释表达式。要用栈求解一个表达式，就要将这个表达式翻译成正确求值 的一个机器指令序列，即正确解释表达式，了解算术四则混合运算的规则：（1）先乘除，后
2、 加减；（2）从左算到右；（3）先括号内，后括号外，再根据这个运算优先的规定来实现对 表达式的编译或解释执行。2.11算法设计：首先将中缀表达式转换成后缀表达式：从左至右依次扫描中缀表达式的每一个字 符，如果是数字字符和，则直接将它们写入后缀表达式中。如果遇到的是开括 号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它 匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（” 时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。如果遇到的是操作 符，则将该操作符和操作符栈顶元素比较：当所遇到的操作符的优先级小于或等于栈顶 元素的优先级时，则取
3、出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到 栈顶元素的优先级小于当前操作符的优先级；当所遇到的操作符的优先级大于栈顶元素 的优先级时，则将它压入栈中。重复上述步骤直到遇到中缀表达式的结束0弹出 栈中的所有元素并放入后缀表达式中，算法结束。通过建立函数，完成栈的表达式求值。主函数可以调用子函数，分别完成字符的输 入，字符的检验，类型转换，表达式的运算和输出信息。在主函数中可以设置调用子函 数，根据输入的字符的不同，做出不同的判断，输出相应的结果。主要功能模块即如图1所示:图1功能模块图2.2设计方法根据所构想的功能及模块设计出与之相对算法并建立函数来实现功能。int check(c
4、har *c)：输入参数为char *c:它是输入的字符串。返回参数为0表示字符 串中有不符合规定的字符；返回参数为1表示字符串字符符合规定，没有不符合规定的 字符。此函数的功能是检查字符串中有否除了 0-9,之外的其他字符，如果有，则返回0,表示出现错误。若没有，则返回1,表式字符串符合规定。Void move(char *f, double *s,int p)输入参数有 char *f :运算符数组；double *s:数值数组；int p: 当前运算符数组位置。功能：将当前已经完成运算的运算符消去，同时将数值数组的位置调整以进 行下一次运算。double convnum(char *c)
5、输入参数为char *c :由数字和小数点组成的字符，用以转换成double型 的数值。返回参数为num:返回转换好的值。功能是将输入的字符串先将其小数点以前的部分复制到 temp数组中，若有小数点，贝9将小数点之后的数值，也就是小数 部分先进行计算,值存入num中。计算完成后，再对整数部分进行计算，值加上小数部 分的值，存入num中。double good(char *c)：输入参数为char *c :即将进行运算的字符串型数学表达式。如 3.5+(2*3/5)。返回参数为s0，表示计算结果将放入s0中。功能是将输入的字符串中的数字分别调用convnum(char *c)函数进行数值变换，再
6、将其依次存入doulbe si中，将 加减乘除运算符依次存入字符串符号数组char fi中，然后如果遇到括号，则将括号内 的字符串存入另一字符数组中，然后用此good(char *c)递归函数进行递归运算。然后 根据先乘除，后加减的顺序对已存入数组的数值根据存入字符串符号数组的运算符进 行运算。结果存入s0中。返回最终结果。(1)主函数的流程图NO*c!=0 ?NONOk-检验成功输入字符串*CK=0c=) ?*c=(0v=*cv=9ll*c=(+ll-ll*ll/ll.ll(ll) ?图3检验函数的流程图(2)检验函数的流程NO输入错误YESYESYESYES开始k+结束c+NOc(0)i=
7、startivlen ?i+ci=P=ip!=0NOivlen ?ci=i-NOnum=0.0;a=1.0;i=0;p=0;start=0 ;tempi=0(3)类型转换函数的流程a=a*0.1;num+=(a*(ci-48);YESi=p+1start=1;f=-1NOYESNOYESYESNOYESYES开始Temp=0Temptempi+结束输入错误图4类型转换流程图2.3源程序清单#includevstdio.h#includevstring.h#includevstdlib.h int check(char *c) int k=0;while(*c!=O)if(*c=0 & *cv=
8、9) II *c=+ IIc=- | *c=* | *c=/ |*c=. | *c=( |*c=)elseprintf（输入错误，包含不是数学字符的字符!n）;return 0;if(*c=()k+;else if(*c=)k-;elsec+;if(k!=0)printf(”输入错误，括号的输入不正确!n);return 0;return 1; void move(char *f, double *s,int p) int i=0,len=strlen(f);for(i=p; ivlen; i+)fi=fi+1；si=si+l;si=si+1; flen-1=0;double convnum(
9、char *c)double num=0.0;double a=1.0;int i=0,p=0,len=0;char temp100;int tempi=0;int start=0;int f=1;len=strlen(c);if(c0=-)start=1;f=-1;for(i=start; ilen; i+)if(ci=.)p=i;break;temptempi+=ci;temptempi=O;if(p!=0)for(i=p+1;i=0; i-)num=num+(a*(tempi-48); a*=10;num=num*f;return num;double good(char *c)char
10、 g100,number30;char f80;int fi=0;double s80;int si=0;int k=0;int num=0,i=0;int cc=0;int jj=0；while(*c!=0)k=0;num=0;switch(*c)case +:case -:case *:case/:ffi+=*c;if(*C=* II *c=/)CC+；elsejj+；if(*(c-l)!=)numberi=O;i=0;ssi+=convnum(number);break;case(:k+;while(k0)c+;gnum=*c;num+;if(*c=)else if(*c=()k+;gn
11、um-1=0;num=0;ssi+=good(g);break;default: numberi+=*c;if(*(c+1)=0) numberi=0; ssi+=convnum(number);break;c+;ffi=O;i=0;while(cc0)switch(fi)case *: cc-; si+l=si*si+l; move(f,s,i);break;case /: cc-; si+1=si/(float)si+1; move(f,s,i);break;default:i+; break;i=0;while(jj0)switch(fi)case +: si+1=si+si+1; jj
12、-； move(f,s,i);break;case -: si+1=si-si+1; jj-； move(f,s,i);break;default:printf(运算符错误!”)； break;return s0;void main()char str100;double sum=0;int p=1;while(1)printf(输入表达式:(输入exit退出)n); scanf(”s,str);p=strcmp(str,exit);if(p=0)break;p=check(str);if(p=0)continue;sum=good(str);printf(”s=%f,str,sum);pri
13、ntf(n);printf(结束!n);3设计结果与分析在Microsoft Visual C+ 6.0环境中输入源程序，在没有提示错误的情况下编译，运行文件。在输 入表达式回车后显示表达式的值（值为正）。图5输入正确表达式运行的正值结果 在输入表达式回车后显示表达式的值（值为负）。图6输入正确表达式后运行的负值结果 输入一个表达式，在表达式中括号不正确的情况下，显示的提示信息。 F:vc +-E. 3Co mmonjVI SD ev9SBinDe bu cC ppi. exe辄八表达式：谕八飞L返出)5+2.3*2-4)-3/2F+2.3*2-4)-3/2=4.100000 输人表达式: 输人飞di返出 2-3*2.6*4)-5/22 3*2.6*4)-5/2=-12.30腕盹 衰达式江输人3计退出4 + 口十3 4*9
