算术表达式的求解

算术表达式的求解&车厢调度二〇一四年六月软件综合课程设计目录算数表达式的求解.........................................3一、前言..............................................3二、问题陈述..........................................3三、需求分析..........................................3四、概要设计.........................................4五、详细设计和编码....................................6六、上级调试过程.....................................10七、总结与心得.......................................12八、参考文献.........................................13附录（源程序）：.....................................13车厢调度................................................20一、问题陈述........................................20二、问题分析与设计..................................20三、运行结果........................................20四、设计体会与总结...................................21附录(源程序).........................................21算数表达式的求解一、前言表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和操作数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。二、问题陈述（算数表达式的求解）给定一个算数表达式，通过程序求出最后的结果。要求如下：1、从键盘输入要求解的算术表达式；2、采用栈结构进行算数表达式的求解过程；3、能够判断算数表达式的正确与否；4、对于错误表达式给出提示；5、对于正确表达时给出最后的结果。三、需求分析有题目可知，程序要求给定一算数表达式并计算最后的结果，我们知道，在高级语言中，任何一个表达式都是有操作数、运算符和界限符组成。在计算过程中，还要考虑表达式中有无括号以及左右括号之分。由于运算符有优先级的高低，因此一个算数表达是不可能总是按顺序执行。通过以上可知，可以用栈来实现运算符的优先级完成算术表达式的求解。为实现算法的优先级，设置两个栈：一个称为操作数栈opnd，用以寄存操作数和运算结果，另一个为操作符栈optr，用以寄存运算符。该算法的基本思想是：（1）首先置操作数栈opnd为空栈，表达式结束符“#”为操作符栈optr的栈底元素。（2）依次读入表达式中每个字符，若为操作数，则进opnd栈；若是运算符，则与optr栈的栈顶运算符比较优先级后做相应操作：若当前操作符大于optr栈的栈顶，则当前操作符入栈；否则，opnd栈的栈顶元素、次栈顶元素出栈，同时optr栈的栈顶元素也出栈，形成运算，并将结果压入opnd栈，直至整个表达式求值完毕（即optr栈的栈顶元素和当前读入的字符均为“#”）。对于算术表达式的输入，本程序采用gets()的方法读入，将运算符‘+’，‘-’，‘*’，‘/’，‘（’，‘）’，‘#’存储在数组中时，定义表达式求解函数，在函数中判断读入的字符，如果是运算符，将这些字符入操作符optr栈，并比较优先级，判断是否运算。若读入的字符为‘0’到‘9’之间的数字时，用字符相减转化为整型，然后将转化后的整型再转化为ASCII的形式压入操作数栈opnd中。四、概要设计1、存储结构设计本程序主要采用顺序栈结构类型（Stack）来存储表达式计算中的数据。程序中需要建立两个栈，一个栈用于寄存运算符，另一个则用于寄存操作数和计算结果，故需要建立两个顺序栈结构类型。何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。2、算数优先级设计对一任意的表达式，由于表达式中运算符的优先级不同，可能会使表达式不按顺序进行计算。在本程序中定义函数Proceed（）来比较运算符的优先级，而函数中各优先级的比较主要根据以下优先级比较的表格：表1：运算符优先级运算符+-*/（）#用数字表示0123456栈内操作符的优先级3355160栈外操作符的优先级2244610在Precede（）函数中定义两个字符型参数变量op和c，其中op表示栈顶运算符，c表示当前读入运算符，对于当前运算符是否入栈，进行如下操作：比较当前运算符和栈顶运算符的优先级的大小：1、如果当前运算符的优先级大于栈顶运算符的优先级，即opc;令函数返回值为''，并将当前运算符进optr栈。2、如果当前运算符的优先级小于栈顶运算符的优先级，即opc；令函数返回值为''，此时应将栈顶运算符出栈和栈顶、次栈顶操作数出栈并进行相应的运算。3、如果当前元素的优先级等于栈顶运算符的优先级，即op=c；令函数的返回值为'='，此时界限符内的表达式已计算完毕。3、ADT描述ADTStack{数据对象：D={ia|ia∈ElemSet,i=1,2,…，n,n≧0}数据对象：R1={1,iiaa|1ia,Dai,i=2,…，n}约定na端为栈顶，ia端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。GetTop(S)初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push(&S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop(&S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1,c2)初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack4、程序模块设计(1）程序模块本程序主要包含3个模块：主程序模块、计算模块以及顺序栈操作模块，调用关系如图所示：图1：程序模块图(2）系统功能模块本程序大致包含10个函数，其中包含主函数。每个函数都有其相对应的功能实现。○1操作符的输入函数intIn(charc);○2运算符比较优先级函数charProceed(charop,charc);主程序模块计算模块顺序栈操作模块○3进行四则运算函数intOperate(inta,chara1,intb);○4实现表达式的求值函数intEvalExpres(void);○5初始化栈函数voidInitStack(Stack*s);○6入栈函数voidPush(Stack*s,intx);○7出栈函数intPop(Stack*s);○8取栈顶元素函数intGetTop(Stack*s);○9判栈空函数voidEmpty(Stack*s);○10主函数intmain()（3)函数之间主要调用的关系图本程序主要包含10个程序，各程序之间的关系如图所示：（部分函数用以上的编号表示）○1○2○3○5○6○7○8○9图2：函数之间调用关系图五、详细设计和编码1、结构体类型的定义typedefstruct{intdata[MAXSIZE];Voidmain()IntEvalExpres(void)inttop;//栈顶intbase;//栈底}Stack;2、全局变量定义//以下为函数声明voidInitStack(Stack*);//初始化栈intEmpty(Stack*);//判空栈voidPush(Stack*,int);//进栈intPop(Stack*);//出栈intGetTop(Stack*);//取栈顶元素intOperate(int,char,int);//计算结果charProceed(char,char);//比较优先级intIn(char);//判断输入符intEvalExpres(void);//表达式计算函数//定义两个栈分别存放运算符和操作数StackStackR,StackD;3、系统主要子程序的详细设计(1）主函数模块设计intmain()//主函数{intv;charch;while(1){cout************算术表达式求解************endl;v=EvalExpres();cout表达式的计算结果为:vendl;coutInput'n'toquitandENTERrunagain:endl;do{cinch;if(ch=='n'||ch=='N')exit(0);}while(ch!='\n');system(cls);}return0;}在主函数中，设定用户操作界面的形式，通过调用表达式求解的子函数实现算法所要实现的功能，然后通过while()循环语句控制，可以实现多次调试。(2）计算函数模块intOperate(inta,chara1,intb){ints;intd1=a;intd2=b;//把字符ab变为对应数字switch(a1){case'+':s=d1+d2;break;case'-':s=d2-d1;break;case'*':s=d1*d2;break;case'/':if(d1!=0){s=d2/d1;}else{cout除数不可以为0!endl;exit(0);}}return(s+'0');//将运算结果转化为ascii码的形式入栈，}在计算函数中，定义3个变量，表示基本运算中的变量。采用开关语句实现表达式的基本运算，将运算结果转化为ASCII的形式返回。(3）表达式求解的函数模块intEvalExpres(void)//表达式求解函数{inta,b,i=0,s=0;charc[80],r;InitStack(&StackR);Push(&StackR,'#');InitStack(&StackD);cout请输入表达式并以‘#’结束：endl;gets(c);while(c[i]!='#'||GetTop(&StackR)!='#'){if(!In(c[i]))//判断读入的字符不是运算符是则进栈{if(c[i]='0'&&c[i]='9'){s+=c[i]-'0';//字符相减将字符型转化为整型while(!In(c[++i]))//继续判断下一个字符，若不是运算符，表明为多位数，直到读取到字符为运算符为止{s*=10;s+=c[i]-'0';}Pus