算术表达式的求解

1、软件综合课程设计 算术表达式的求解&车厢调度 二一四 年 六 月目录算数表达式的求解3一、前言3二、问题陈述3三、需求分析3四、 概要设计4五、详细设计和编码6六、上级调试过程10七、总结与心得12八、参考文献13附录（源程序）：13车厢调度20一、 问题陈述20二、 问题分析与设计20三、 运行结果20四、设计体会与总结21附录(源程序)21算数表达式的求解一、前言表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因

2、此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和操作数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。二、问题陈述（算数表达式的求解）给定一个算数表达式，通过程序求出最后的结果。 要求如下： 1、从键盘输入要求解的算术表达式； 2、采用栈结构进行算数表达式的求解过程； 3、能够判断算数表达式的正确与否； 4、对于错误表达式给

3、出提示； 5、对于正确表达时给出最后的结果。三、需求分析有题目可知，程序要求给定一算数表达式并计算最后的结果，我们知道，在高级语言中，任何一个表达式都是有操作数、运算符和界限符组成。在计算过程中，还要考虑表达式中有无括号以及左右括号之分。由于运算符有优先级的高低，因此一个算数表达是不可能总是按顺序执行。 通过以上可知，可以用栈来实现运算符的优先级完成算术表达式的求解。为实现算法的优先级，设置两个栈：一个称为操作数栈opnd，用以寄存操作数和运算结果，另一个为操作符栈optr，用以寄存运算符。该算法的基本思想是：（1） 首先置操作数栈opnd为空栈，表达式结束符“#”为操作符栈optr的栈底元素

4、。（2）依次读入表达式中每个字符，若为操作数，则进opnd栈；若是运算符，则与optr栈的栈顶运算符比较优先级后做相应操作：若当前操作符大于optr栈的栈顶，则当前操作符入栈；否则，opnd栈的栈顶元素、次栈顶元素出栈，同时optr栈的栈顶元素也出栈，形成运算，并将结果压入opnd栈，直至整个表达式求值完毕（即optr栈的栈顶元素和当前读入的字符均为“#”）。对于算术表达式的输入，本程序采用gets()的方法读入，将运算符+，-，*，/，（，），#存储在数组中时，定义表达式求解函数，在函数中判断读入的字符，如果是运算符，将这些字符入操作符optr栈，并比较优先级，判断是否运算。若读入的字符为0

5、到9之间的数字时，用字符相减转化为整型，然后将转化后的整型再转化为ASCII的形式压入操作数栈opnd中。4、 概要设计 1、存储结构设计本程序主要采用顺序栈结构类型（Stack）来存储表达式计算中的数据。程序中需要建立两个栈，一个栈用于寄存运算符，另一个则用于寄存操作数和计算结果，故需要建立两个顺序栈结构类型。何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺

6、序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。 2、算数优先级设计 对一任意的表达式，由于表达式中运算符的优先级不同，可能会使表达式不按顺序进行计算。在本程序中定义函数Proceed（）来比较运算符的优先级，而函数中各优先级的比较主要根据以下优先级比较的表格：表1：运算符优先级运算符+-*/（）#用数字表示0123456栈内操作符的优先级3355160栈外操作符的优先级2244610 在Precede（）函数中定义两个字符型参数变量op和c，其中op表示栈顶运算符，c表示当前读入运算符，对于当前运算符是否入栈

7、，进行如下操作：比较当前运算符和栈顶运算符的优先级的大小： 1、如果当前运算符的优先级大于栈顶运算符的优先级，即opc;令函数返回值为c；令函数返回值为，此时应将栈顶运算符出栈和栈顶、次栈顶操作数出栈并进行相应的运算。 3、如果当前元素的优先级等于栈顶运算符的优先级，即op=c；令函数的返回值为=，此时界限符内的表达式已计算完毕。 3、ADT描述ADT Stack数据对象：D= |ElemSet,i=1,2,，n, n0数据对象：R1=|,i=2,，n约定端为栈顶，端为栈底。基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果

8、：用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()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。ADT Sta

9、ck 4、程序模块设计 (1）程序模块 本程序主要包含3个模块：主程序模块、计算模块以及顺序栈操作模块，调用关系如图所示：顺序栈操作模块计算模块主程序模块 图1：程序模块图 (2）系统功能模块 本程序大致包含10个函数，其中包含主函数。每个函数都有其相对应的功能实现。 操作符的输入函数 int In(char c); 运算符比较优先级函数 char Proceed(char op,char c); 进行四则运算函数 int Operate(int a,char a1,int b); 实现表达式的求值函数 int EvalExpres(void); 初始化栈函数 void InitStack(S

10、tack *s); 入栈函数 void Push(Stack *s, int x); 出栈函数 int Pop(Stack *s); 取栈顶元素函数 int GetTop(Stack *s) ; 判栈空函数 void Empty(Stack *s); 主函数 int main() （3)函数之间主要调用的关系图 本程序主要包含10个程序，各程序之间的关系如图所示：（部分函数用以上的编号表示）Void main()Int EvalExpres(void) 图2：函数之间调用关系图 五、详细设计和编码 1、结构体类型的定义 typedef struct int dataMAXSIZE; int t

11、op; /栈顶int base; /栈底 Stack; 2、全局变量定义/以下为函数声明void InitStack(Stack *); /初始化栈 int Empty(Stack *); /判空栈 void Push(Stack *, int ); /进栈 int Pop(Stack *);/出栈 int GetTop(Stack *); /取栈顶元素 int Operate(int ,char ,int ); / 计算结果 char Proceed(char ,char ); / 比较优先级 int In(char ); /判断输入符int EvalExpres(void); /表达式计算

12、函数/ 定义两个栈分别存放运算符和操作数Stack StackR,StackD; 3、系统主要子程序的详细设计 (1）主函数模块设计int main()/主函数int v;char ch;while (1)cout *算术表达式求解* endl;v = EvalExpres();cout 表达式的计算结果为: v endl;cout Input n to quit and ENTER run again: ch;if (ch = n | ch = N)exit(0); while (ch != n);system(cls);return 0;在主函数中，设定用户操作界面的形式，通过调用表达式求

13、解的子函数实现算法所要实现的功能，然后通过while()循环语句控制，可以实现多次调试。 (2）计算函数模块 int Operate(int a, char a1, int b) int s;int d1 = a;int d2 = 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;elsecout 除数不可以为0! endl;exit(0);return (s + 0); /将运算结果

14、转化为ascii码的形式入栈， 在计算函数中，定义3个变量，表示基本运算中的变量。采用开关语句实现表达式的基本运算，将运算结果转化为ASCII的形式返回。 (3）表达式求解的函数模块 int EvalExpres(void) / 表达式求解函数 int a, b, i = 0, s = 0;char c80, r;InitStack(&StackR);Push(&StackR, #);InitStack(&StackD);cout 请输入表达式并以#结束： = 0 & ci = 9)s += ci - 0; /字符相减将字符型转化为整型 while (!In(c+i) /继续判断下一个字符，若

15、不是运算符，表明为多位数，直到读取到字符为运算符为止 s *= 10;s += ci - 0;Push(&StackD, s + 0); /将整型转化为ascii的形式入栈，使字符在栈内以ascii的形式保存，实现多位数的计算 s = 0; /初始化s，继续判断elsecout 你输入的表达式有误! endl;exit(0);elseswitch (Proceed(GetTop(&StackR), ci) /此函数用来比较读取的运算符和栈顶运算符的优先级 case : /栈顶的优先级高则出栈，并将计算结果压入栈内 r = Pop(&StackR);a = Pop(&StackD) - 0; /

16、操作数在栈内以ascii的形式存储，出站后要将ascii转化为整型，然后进行运算 b = Pop(&StackD) - 0;Push(&StackD, Operate(a, r, b);break;return (GetTop(&StackD) - 0); / 将栈顶元素转化为整型的形式输出 对于表达式求解函数，在程序中主要思想是对读入的表达式进栈进行判断。若读入的是0到9之间的字符，将这些字符采用ascii相减的形式转化为整型，再入opnd栈，若读入的字符为运算符，则将运算符入栈，并比较运算符之间的优先级，看是否运算，若栈顶的运算符小于当前输入的运算符，则不需运算，只要将当前运算符入栈即可。

17、否则，运算。运算时先将optr栈的栈顶运算符和opnd栈的栈顶、次栈顶元素出栈，并将opnd栈中出栈的元素的ASCII形式转化为整型再计算，最后讲计算结果再转化为ASCII码的形式压入opnd栈中。使表达式求解函数返回值为opnd的栈顶元素。六、上级调试过程 1、遇到问题以及解决方案 问题1、调试时没有错误，但运行时显示错误。解决方案：通过它提示的错误和警告，在判断是否为运算符的子函数中出现错误，如果为运算符时返回1，其次返回0，在返回0时没有用else，这样使得整个子函数可以返回一个有效值。 问题2、调试时程序显示没有错误，可以运行，但在运行时结果却出现错误。解决方案：把程序从头看了一遍，发

18、现在比较优先级的函数中，优先级的比较比较乱，而且部分出错，后来查了关于运算符优先级的资料，通过在纸上把各种优先级列出，解决这个错误。2、算法的时间复杂度 由于在主函数用到嵌套循环，故算法的时间复杂度为O（n2）。3、测试结果及其分析 （1）实现基本的加减乘除运算，当想要继续输入表达式时点击enter键，若要结束，点击n或N键即可，而且可实现多位数的运算。（2）实现复杂的算术表达式（3）错误表达式的处理4、用户使用说明 （1）本程序执行的文件为“算数表达式的求解问题”。 （2）所求表达式中都只是仅包含加、减、乘、除4种基本运算的，其中也包含括号的应用，所有的运算对象均为简单变量，要求将表达式中的

19、数字字符转化为整型，且输入表达式以“#”结束。 （3）输入表达式时，以#结束，当点击回车键时即可得到运算结果，当想继续输入表达式时，再次点击回车键即可，当想结束时，点击字母n或N。 （4）当输入错误表达式时，程序会给出相应的提醒。七、总结与心得这次课程设计让我更加了解大一学到的C+和大二学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写EvalE

20、xpres()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时发现上机的重要作用，特别算术表达式有了深刻的理解。通过实际操作，我也发现我的好多不足之处：(1)用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式。开始有些茫然，后来通过结合课本和同学的帮助完成了该课题。(2)对一些

21、看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。(3)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。八、参考文献 1王昆仑 、李红主编，数据结构与算法，北京：中国铁道出版社，2007年5月 2阮宏一 、鲁静主编，数据结构课程设计（C/C+描述），北京：电子工业出版社，2011年1月 3严蔚敏、吴伟民主编 数据结构（C语言版） 清华大学出版社 2002 4殷人昆等著 数据结构（C+版） 清华大学出版社 2001附录（源程序）：#include using namespace std;#de

22、fine MAXSIZE 16typedef structint dataMAXSIZE;int top;int base; /栈底 Stack; / 顺序栈的定义/以下为函数声明void InitStack(Stack *); /初始化栈 int Empty(Stack *); /判空栈void Push(Stack *, int); /进栈int Pop(Stack *);/出栈int GetTop(Stack *); /取栈顶元素int Operate(int, char, int); / 计算结果char Proceed(char, char); / 比较优先级int In(char)

23、; /判断输入符int EvalExpres(void); /表达式计算函数/ 定义两个栈分别存放运算符和操作数Stack StackR, StackD;int main()/主函数int v;char ch;while (1)cout *算术表达式求解* endl;v = EvalExpres();cout 表达式的计算结果为: v endl;cout Input n to quit and ENTER run again: ch;if (ch = n | ch = N)exit(0); while (ch != n);system(cls);return 0;void InitStack(

24、Stack *s) /初始化栈s-top = 0;s-base = 0;int Empty(Stack *s)/判断栈是否为空if (s-top = s-base)return 1; /栈空时返回1，否则返回0 elsereturn 0;void Push(Stack *s, int x) / 进栈 if (s-top = MAXSIZE)cout error datas-top = x;s-top+;int Pop(Stack *s)/ 出栈int e;if (Empty(s)cout error top-;e = s-datas-top;return e;int GetTop(Stack

25、*s) /取栈顶元素if (Empty(s)cout error datas-top - 1;int EvalExpres(void) / 表达式求解函数int a, b, i = 0, s = 0;char c80, r;InitStack(&StackR);Push(&StackR, #);InitStack(&StackD);cout 请输入表达式并以#结束： = 0 & ci = 9)s += ci - 0; /字符相减将字符型转化为整型 while (!In(c+i) /继续判断下一个字符，若不是运算符，表明为多位数，直到读取到字符为运算符为止 s *= 10;s += ci - 0

26、;Push(&StackD, s + 0); /将整型转化为ascii的形式入栈，使字符在栈内以ascii的形式保存，实现多位数的计算 s = 0; /初始化s，继续判断elsecout 你输入的表达式有误! endl;exit(0);elseswitch (Proceed(GetTop(&StackR), ci) /此函数用来比较读取的运算符和栈顶运算符的优先级 case : /栈顶的优先级高则出栈，并将计算结果压入栈内 r = Pop(&StackR);a = Pop(&StackD) - 0; /操作数在栈内以ascii的形式存储，出站后要将ascii转化为整型，然后进行运算 b = P

27、op(&StackD) - 0;Push(&StackD, Operate(a, r, b);break;return (GetTop(&StackD) - 0); / 将栈顶元素转化为整型的形式输出int In(char c) /判断C是否为运算符是返回1否则返回0char ch7 = +, -, *, /, #, (, ) ;int i;for (i = 0; i ; break;case *:case /:case (: ch = ; break;case (: ch = ;else if (op = () /*栈顶元素为(的时候*/switch (c)case +:case -:cas

28、e *:case /:case (: ch = ; break;case #:cout Error!没有右括号! ; break;case (:cout Error!括号匹配错误! endl;exit(0);else if (op = #) /栈顶元素为#的时候 switch (c)case +:case -:case *:case /:case (: ch = ; break;case ):cout Error!没有左括号! endl;exit(0);return ch;int Operate(int a, char a1, int b)int s;int d1 = a;int d2 = b

29、; /把字符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;elsecout 除数不可以为0! endl;exit(0);return (s + 0); /将运算结果转化为ascii码的形式入栈， 车厢调度1、 问题陈述假设停在铁路调度站入口处的车厢序列的编号一次为1，2，3，4。设计一个程序，求出所有可能由此输出的长度为4的车厢序列。2、 问题分析与设计 车厢调度问题是实际生活中的一个抽象问题，

30、实际上其本质就是一个N个数的全排列问题，所谓全排列算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 N个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外都有一个前驱。每一个排列的后继都可以从它的前驱经过最少的变化得到，全排列的生产算法就是从第一个排列开始逐个生产所有的排列的方法。 全排列的生产法通常有几下几种： 字典排序法：从右往左开始找出第一个比右边数字小的数字的序号j，然后在以j为基准再从左往右，找出第一个比它大的最小的数，然后这两个数位置对调。例如：1 5 4 7 6 32 的下一个排列是 1 56

31、74 3 2 。 邻位交换法：邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。例如：以4个元素的排列为例，将最后的元素4逐次与前面的元素交换，可以生成4个新排列：1 2 3 4、1 243、14 2 3、4 1 2 3。然后将最后一个排列的末尾的两个元素交换，再逐次将排头的4与其后的元素交换，又生成四个新排列：4 13 2、143 2、1 3 4 2、1 3 2 4。再将最后一个排列的排头的两个元素交换，再将4从后往前移：3 1 2 4、3 14 2、34 1 2、4 3 1 2。如此循环既可求出全部排列。 递归类算法： 我将选择递归类算法作为实现该车厢调度的主要算法，通过设计perm递归函数。3、 运行结果 当列车长度为4时：四、设计体会与总结递归算法是解决问题的一种非常好的方法，我在网上看到这个车厢调度的问题一般用栈来实现，但是觉得可以用递归来完成，而且比栈更简单，就选择了用递归来完成，通过这两周内的时间，我如期完成了此次的课程设计，车厢调度算法从本质上讲就是N个数的全排列算法，虽然从代码量上看是比较少，但是能够彻底的从分析问题到理解问题再到解决问题，实际上还是没那么容易。通过此次课程设计我们大学生应该注重算法的分析以及打牢和巩固基础，这样在实现一些比较稍