数据结构课程设计：算术表达式

表达式求值目的利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果需求分析设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。对于这个程序我们从输入，输出，和功能三方面来分析。程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“+”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。功能要求及说明：从键盘上输入表达式。分析该表达式是否合法（包含分母不能为零的情况）：（1） 是数字，则判断该数字的合法性。（2） 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3） 若是其它字符，则返回错误信息。若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。概要设计数据结构的选择：任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。为了实现算符优先算法，可以使用两个工作栈。一个称做SqStackl，用以寄存运算符；另一个称做SqStack2，用以寄存操作数或运算结果。首先置操作数栈为空栈，表达式起始符“＃”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，若是操作数则进入SqStack2栈，若是运算符则和SqStack1栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕。两个栈：typedefstruct//运算符栈{char*base;char*top;intstacksize;}SqStack1;typedefstruct//运算数栈{float*base;float*top;intstacksize;}SqStack2;相关功能函数：voidInitStackl(SqStackl&SI);//声明运算符栈建立函数voidInitStack2(SqStack2&S2);//声明运算数栈建立函数主要的确定如何入栈的函数：voidevaluate(SqStackl&S1,SqStack2&S2);voidPush1(SqStackl&S1,chare);//声明入栈函数

voidPush2(SqStack2&S2,floate);//声明入栈函数

charGetTop1(SqStackl&Sl);//声明取栈顶元素函数

floatGetTop2(SqStack2&S2);//声明取栈顶元素函数

charPop1(SqStackl&Sl);//声明出栈函数

floatPop2(SqStack2&S2);//声明出栈函数

charCompare(charm,charn);//声明比较函数通过这个函数我们来实现运算符运算的先后顺序判断运算符优先权，返回优先权高的算符间的优先关系如下：+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=最后的计算函数：floatOperate(floata,charrheta,floatb);//声明运算函数为了使运算的过程更加直观的反应出来，我们再绘制一个表格，绘制表格的相关函数如下：voidDispStackl(SqStackl&Sl);//从栈底到栈顶依次输出各元素voidDispStack2(SqStack2&S2);//从栈底到栈顶依次输出各元素

函数模块之间的调用关系：栈的建立及初始化模块O运算符运算数出栈模块判断字符类型模块运算符优先级比较模块判断输入是否结束模块主程序模块输入结束输出结果运算符进栈模块运算数进栈模块运算模块栈的建立及初始化模块O运算符运算数出栈模块判断字符类型模块运算符优先级比较模块判断输入是否结束模块主程序模块输入结束输出结果运算符进栈模块运算数进栈模块运算模块详细设计首先本程序定义两个顺序栈：运算符栈（SqStackl）和运算数栈（SqStack2）；typedefstruct//运算符栈{char*base;char*top;intstacksize;}SqStack1;typedefstruct//运算数栈{float*base;float*top;intstacksize;}SqStack2;然后是主要功能函数的详细设计：/*运算符栈函数*/voidInitStackl(SqStackl&S1)//构造一个空栈SI{S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!Sl.base)cout<<"存储分配失败！";//存储分配失败S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;}确定如何入栈的函数实现如下：voidPushl(SqStackl&S1,chare)//入栈{if(S1.top-S1.base>二S1.stacksize)//如果栈满，追加存储空间{Sl.base=(char*)realloc(Sl.base,(Sl.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base) cout<<"存储分配失败！";else{Sl.top=Sl.base+Sl.stacksize;Sl.stacksize=Sl.stacksize+STACKINCREMENT;}}*S1.top=e;S1.top二S1.top+1;//将元素压入栈中，指针上移}实现提取栈顶元素的函数实现：charGetTop1(SqStack1&S1)//取栈顶元素{chare;if(S1.top二二S1.base)cout<<"\n\t\t\t运算符栈已空!\n";elsee=*(Sl.top-l);returne;}以及设计的一个在结果显示过程的栈中清单打印函数voidDispStack1(SqStack1&S1)//从栈底到栈顶依次输出各元素{chare,*p;if(Sl.top==Sl.base)cout<<"";else{p=Sl.base;while(p<Sl.top){e=*p;p++;cout<<e;}}}核心的算法确定如何入栈函数的实现如下voidevaluate(SqStack1&S1,SqStack2&S2){charc;floatt,e;intn=0,i=1,j=0,k=0,l=0;charch[STACK_INIT_SIZE];ints=1;intflag=0,flag2=0;floatp1,p2;charch1;Pushl(Sl,'#');//将'#'入栈，作为低级运算符cout<<〃•请输入不含变量的表达式(以#结束！)：\n";cin>>ch;c=ch[0];cout<<〃\n•对表达式求值的操作过程如下：〃<<〃\n \n〃<<"步骤\t运算符栈S1\t运算数栈S2\t输入字符\t\t主要操作〃;while(c！='#'||GetTop1(S1)！='#'){cout<<〃\n \n〃;cout<<i++<<〃\t〃;DispStack1(S1);cout<<〃\t\t〃;DispStack2(S2);cout<<〃\t\t〃;if(flag==1){k--;flag=0;}if(flag2){k+=flag2;flag2=0;}for(l=0;l<k;l++)cout<<'';for(j=k;ch[j]!='\0';j++)cout<<ch[j];if(ch[k]!='#'&&flag!=1){k++;flag=0;}as:if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')){//输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数if(!(c=='.')&&n>=0){e=float(c-48);n++;if(n==1)t=e;elseif(n>1)t=t*10+e;c=ch[s++];}if(n==-1){e=float(c-48);t=t+e/10;c=ch[s++];}if(c=='.'){n=-1;c=ch[s++];}if((c>='0'&&c<='9')||c=='.'){flag2++;gotoas;}if(c<'0'||c>'9'){Push2(S2,t);}cout<<"\t\tPush2(S2,"<<t<<")";}else//输入的是运算符{n=0;//非运算型数据计数器清零switch(Compare(GetTopl(Sl),c))//比较运算符的优先级{case'<'://栈顶元素优先级低，则入栈且继续输入Push1(S1,c);cout<<"\t\tPush1(S1,"<<c<<")";c=ch[s++];break;case'='://栈顶元素优先级相等，脱括号并接收下一字符Pop1(S1);cout<<"\t\tPop1(S1)";c=ch[s++];break;case'>'://栈顶元素优先级高，则退栈并将运算结果入栈p1=Pop2(S2);p2=Pop2(S2);ch1=Pop1(S1);Push2(S2,Operate(p2,ch1,p1));cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';flag=1;break;}}}cout<<"\n \n";cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";for(j=0;j<k;j++)cout<<'';cout<<"#"<<"\t\t"<<"RETURN(GETTOP(S2))";cout<<"\n \n";if(S2.top-1二二S2.base)//显示表达式最终结果cout<<"\n•表达式的结果为："<<GetTop2(S2)<<endl;elsecout<<"\n表达式出错！\n";}运算符的优先级比较函数实现如下charCompare(charm,charn)//运算符的优先级比较{if(n=='+'||n=='-')//输入符号为〃+〃、〃-〃{if(m=='('||m=='#')return'<';//栈顶元素为〃(〃、〃#〃,此时栈顶符号优先级低，返回〃<〃elsereturn'>';//否则，栈顶符号优先级高,返回〃>〃}elseif(n=='*'||n=='/')//输入的符号为〃*〃、‘7〃{if(m==')'||m=='*'||m=='/')return'>';//栈顶元素为〃)〃、〃*〃、〃/〃,此时栈顶符号优先级高，返回〃>〃elsereturn'<';//否则，栈顶符号优先级低,返回〃<〃}elseif(n=='(')return'〈’；//输入的符号为〃(〃，则直接返回〃〈“elseif(n==')')//输入的符号为〃)〃{if(m=='(')return'二’；//栈顶元素为〃(〃,此时优先级同，返回〃二〃elsereturn'>';//否则，栈顶符号优先级高,返回〃>〃}else //输入符号为其他{if(m=='#')return'二’；//栈顶元素为〃#〃,此时优先级同，返回〃二〃elsereturn'>';//否则，栈顶符号优先级高,返回〃>〃}}以及最后的计算函数floatOperate(floata,chartheta,floatb)//运算函数{floattmp=0；if (theta二二'+')tmp二a+b;//从运算符栈取出的符号为〃+〃，则运算数栈的两元素相加，并返回elseif(theta二二'-')tmp二a-b;//从运算符栈取出的符号为〃-〃，则运算数栈的两元素相减，并返回elseif(theta二二'*')tmp二a*b;//从运算符栈取出的符号为〃*〃，则运算数栈的两元素相乘，并返回elseif(theta=='/') //从运算符栈取出的符号为〃/〃，则运算数栈的两元素相除，并返回{if(b==0)cout<<〃\n表达式出错!除数不能为0!\n";elsetmp=a/b;}returntmp;}调试分析1．结构分析:栈中的数据节点是通过数组来存储的。因为在C语言中数组是用下标从零开始的，因此我们在调用他们的数据是要特别注意。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P来访问结点，否则会引起程序错误。如果输入的数字不符合题目要求，则会产生错误结果。2．算法的时空分析：时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于是用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。在不知表达式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。测试结果1、实数混合运算

RETURN(GETTOP(S2))#3Opera(.7, 4.)74Push2(S2,4)74#PushlCSl,-)3社7Operate(.1,+,6jF#+16Operate(.2,:+:,3.)123Push2(S2,3)123-4#Pushl(：Sl/+\)4U+12#3-4#Push2(S2,2)3#+12*3-4#PushlCSl,+)社1+2*3-4#Push2(S2,1)11+2+3-4#运算数栈艾输入字符主要操作运算符栈關请输人不合变量的表达式〔以结束!〕RETURN(GETTOP(S2))#3Opera(.7, 4.)74Push2(S2,4)74#PushlCSl,-)3社7Operate(.1,+,6jF#+16Operate(.2,:+:,3.)123Push2(S2,3)123-4#Pushl(：Sl/+\)4U+12#3-4#Push2(S2,2)3#+12*3-4#PushlCSl,+)社1+2*3-4#Push2(S2,1)11+2+3-4#运算数栈艾输入字符主要操作运算符栈關请输人不合变量的表达式〔以结束!〕1+2+3-O对表达式求值的操作过程如下：E3'C:\IJsers\kai\Documents\C-表达式&©6,0\算术表达式,exe"OX果束继结结键的键意式意任达任按表按请・5"C:\Users\kai\Documents\C-Free\Prqjects\算术表达式\vc6,0\算术表达式.exe"- 0 X晴输人不含变量的表达式（以#结束！）:1.4+1.0*1.5-1.6#对表达式求值的操作过程如下：步骤 运算符栈E1运算数栈史输入字符主要操作1#1.4+1.0*1.5-1.舗Push2(S2,1.4)2#1.44+1.0*1.5-1.肘Pushl(SI,+)3 #+1.4+1.0*1.5-1.舗Push2(S2,1)4 tt+1.41.0*1.5-1.Pushl(SI,*)5 #+*1.410*1.5-1.舗F'ush2(S2,1.5)6#+*1.411.51.5-1.肘Operate」丄*,1.5.)7 #+1.41.51.5-1.训Opera4,+,1.5.)8#2.91.5-1.肘Pushl(SI,-)9 卜2.9.5-1.训F'ush2(S2,1.6)102.91.6-1.肘OperatmU.E1.6j11#1.3#RETURN(GETTOP(S2))表达式的结果为：1.3按任意键结束！请按任意键继续•••■■5 9HRlHOggl囱珏⑭宇中2336以上调试结果是正确的。能够实现各个符号优先级先后顺序的运算，根据符号优先级（、）、+、-、*、/，如此顺序进行运算，实现了基本表达式运算的功能。但是需要注意的是，这个程序功能并不是那么完善，具体能实现的功能如下：由于中英文字符的不同，加上本程序没有对中文字符加以处理，当从键盘输入的表达式中包含中文括号时程序无法正确的计算出结果，而是会报错！同样表达式中只能包含英文的运算符，输入中文的运算符时会报错！同样，从键盘输入的表达式必须要运算符匹配，例如括号要匹配，要成对出现，由于本程序没有加以处理，遇到这种情况，程序会报错！用户使用说明1•使用