算术表达式求值

1、题目：算术表达式求值问题内容：一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。要求：（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。选作内容：操作数类型扩充到实数。一：问题分析和任务定义1. 问题分析：分析题目并参考书目可以基本了解完成一个算术表达式所存在的问题。对一个表达式来说，由于各

2、种运算符和界限符的运用，运算符和界限符的优先级决定了算术表达式不是简单的从左往右的运算。因此设计算法完成算术表达式时就要考虑各运算符和界限符的优先级，同时还要注意操作数与算符的判断。在算法中要求完成操作数、运算符和界限符的出入栈，运算符和界限符的优先级比较和操作数之间的运算。最后完成的算法要求输入一个算术表达式，能够正确的计算出来它的最后结果并输出。为了不用考虑算符优先级，将输入的中缀表达式转换成后缀表达式。这样就可以知道实现本程序需要进行的操作：1） 建立空栈，存储信息；2） 运用函数实现出入栈和取栈顶元素操作。3） 将中缀表达式转换成后缀表达式。4） 实现后缀表达式的求解。5） 建立一个函

3、数使中缀表达式能够被有效输入。本程序的关键是中缀表达式转换成后缀表达式对于栈的操作（1）建空栈setstack() 运算的结果是将栈顶元素返回。（2）清空栈emptystack（），可以用于判断栈内元素的有无，在栈顶元素的输出被使用。（3）入栈push（），出栈pop()和取栈顶元素top()。2.任务定义1) 本演示程序中，利用栈将输入的中缀表达式转换成后缀表达式，并完成其求解过程来达到计算表达式的目的。2) 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。3) 程

4、序执行的命令包括： 1)输入任意一个整数表达式；2）是否继续。4) 测试数据 输入一个整数表达式：3+（5*8-9）输出：后缀表达式：3 5 8 *9 -+结果为：34继续？（y/n）二、数据结构的选择和概要设计算术表达式中各数据元素间存在一种线性关系，设计的数据类型如下：#define maxnum 50typedef int datatype; typedef struct datatype smaxnum; int t; seqstack,*pseqstack;/定义一个类型名为seqstack的数据类型本算法设计过程中只采用加减乘除等四种运算符，题目要求借助栈完成算法设计，提示中要把中

5、缀表达式转换成后缀表达式计算，因此操作运算包括要建空栈、清空栈、进栈、出栈、取栈顶元素，中缀表达式转换成后缀表达式，后缀表达式的运算等。将运算符和界限符一起描述为算符，本程序的设计如下：（1） 先定义一下数据结构来存储算术表达式。（2） 建空栈setstack(),清空栈。（3） 对栈进行的运算函数，出入栈和取栈顶元素。（4） 中缀表达式转换成后缀表达式的函数its（）。（5） 后缀表达式计算函数。（6） 设计存放后缀表达式的队列。（7） 主函数main(),使得整个程序完整进行。三、详细设计和编码为了实现概要设计中的所有数据类型，对每个操作给出算法。对主程序和其他模块也都需要写出算法。1）

6、数据类型#define maxnum 50typedef int datatype; typedef struct datatype smaxnum; int t; seqstack,*pseqstack;/定义一个类型名为seqstack的数据类型建空栈和其它关于栈的操作这部分为栈的运算问题。为后面表达式转换和计算做准备。这方面的知识书上有系统讲到，不需要过多去设计算法。2） 表达式的转换和计算将中缀表达式转换成后缀表达式，顺序扫描中缀算术表达式，当读到数字时直接将起送至输出队列中；当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；当读入左括

7、号时，即入栈；当读入右括号时，将靠近栈的第一个左括号上面的运算符依次弹出，送至输出队列中，再删除栈中左括号。在计算后缀表达式式，最后保存的值是最先取出参与运算，所以要用到栈。 读到数字时直接送至输出队列中：switch(c1) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: set =1; suffixj+=c1; /*遇到数字输出*/ break;当读到左括号时入栈： case (: set=0; push(ps, c1); /*遇到左括号，入栈*/ break; 当读入右括号时，

8、将靠近栈的第一个左括号上面的运算符依次弹出，送至输出队列中，再删除栈中左括号： case ): c2 = ); /*遇到右括号把右括号赋值给c2*/ while(!emptystack(ps) /*当栈不为空时*/ c2=top(ps); /*遇到右括号取栈顶*/ pop(ps); /*出栈*/ if(c2 =() break; /*遇到左括号时停止出栈*/ suffixj+=c2; /*c2的值放入后缀表达式中*/ 当读到加减乘除号时，栈和后缀表达式的变化。因为优先级的关系，将加减号同时考虑，乘除号同时考虑。读到加减号处理时运用算法如下： case +: case -: while(!emp

9、tystack(ps) /*当栈不为空时*/ c2 = top(ps); /*将栈顶元素赋值给c2*/ if(c2 =+| c2 =-| c2 = * | c2 = /) pop(ps); /*遇到加减号时栈中栈顶元素是加减乘除四种运算符出栈*/ suffixj+ = c2; /*将c2放入后缀表达式中*/ else if(c2=() break; /*遇到加减号时栈顶元素是左括号不进行出栈*/ push(ps, c1); /*c1入栈*/ break; 读到乘除号处理时算法与加减法基本一致，但在if语句时只需考虑c2 = * | c2 = /。 计算后缀表达式时读到数值时计算sum的值 sw

10、itch(c) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: if(set = 1) /*遇到操作数*/ sum = sum * 10 + c - 0; /*sum的计算*/ else /*所遇到的不是操作数*/sum = c - 0;/*sum的计算*/ set=1;break; 考虑遇到空格、制符表和运算符时sum值的入栈情况 case : caset: case n:if (set = 1) push(ps, sum); /*遇到空格或制表符sum入栈*/ set = 0;

11、break; case +: case -: case *: case /: if(set = 1) push(ps, sum); /*遇到运算符时sum入栈*/ set = 0; 遇到加减乘除四个运算符时将栈顶和次栈顶元素分别运用所遇到运算符进行运算，并将运算结果入栈 num2 = top(ps); /*栈顶元素赋值给num2*/ pop(ps); /*元素出栈*/ if(emptystack(ps) /*当栈为空*/ free(ps); /*释放栈内空间*/ return 0; num1 = top(ps); /*栈顶元素赋值给num1*/ pop(ps); /*元素出栈*/ if(c =

12、 +) /*c为加号时*/ push(ps, num1 + num2); /*num1与num2的和入栈*/ if(c = -) /*c为减号时*/ push(ps, num1 - num2); /*num1与num2的差入栈*/ if(c = *) /*c为乘号时*/ push(ps, num1 * num2); /*num1与num2的积入栈*/ if(c = /) /*c为除号时*/ push(ps, num1 / num2); /*num1与num2的商入栈*/ break; default: free(ps); return 0; 该部分为程序的核心算法，即将算术表达式的值正确的输出

13、。4)主函数基本的数据定义，并实现表达式的输入，并调用getline()函数 void main() char c, infixmaxnum, suffixmaxnum; int result; int flag = 1; while(flag = 1) printf(请输入任意一个整数算术表达式:n); getline(infix, maxnum); /*调用getline()函数*/ if(its(infix, suffix) = 1) printf(所得后缀为:%sn, suffix); else printf(无效缀!n); 调用calculatesuffix()函数使程序完整 if(

14、calculatesuffix(suffix, &result) = 1) /*调用calculatesuffix()函数*/ printf(结果为:%dn, result); else printf(非法后缀!n); 四、上机调试 1.编程中遇到的几个问题 刚看到题目的时候，我对题意没有理解，运用的普通的方法来完成程序，运行时输入无括号的算术表达式可以正确输出结果，但输入带括号的表达式时输出的结果与运算结果不符。因此根据提示，设计算法将输入的中缀表达式转换成后缀表达式再运算得到结果。在此算法即最终使用的程序中，中缀表达式转换成后缀表达式函数中 2、算法设计、调试的经验和体会刚开始拿到这个问题

15、时自己对如何设计算法没有一点头绪。但我从中理解了题目的意思，也找到了解决问题的思路，最重要的是启发了我运用本课程中所学的去解决该问题。我做完本次实验还有一个体会是：设计一个程序需要按一个完整的步骤来进行。首先必须弄懂程序要解决的是什么问题。在弄懂之后大脑中就要开始构思要用是什么方法来解决问题，多问同学、老师或者多查阅相关资料通过网络等等。只有经过这个过程才会提高自己的发现问题、分析问题、解决问题的能力，使得思维更加严谨。虽然这次课程设计不是很难，不是做一个比较大的系统，代码不算多，但是我认为要成功地完成一个程序，包括完整的实验报告都要投入必要的时间和精力，认真对待，这样我们可以收获不少东西。

16、通过这次课程设计，我深知自己学习的知识还远远不够。这是一种全面综合训练，是与课堂听讲，自学和练习相辅相成的，必不可少的一个教学环节。这次的课程设计为以后的学习打下了坚实的基础。我们网络工程专业就要跟大量的程序算法打交道。这就要求我们必须将每一句语言的精髓领悟透彻，注重细节，掌握每一种算法的功能。只有这样，我们在解决实际生活中的问题的时候，才能运用的得心应手，恰到好处。五、测试结果及其分析1、运行程序后，初界面： 图1：运行程序后初界面2、输入表达式后： 图2：输入表达式后3、输入y后： 图3：输入y后 4、再次输入表达式： 图4：再次输入表达式5、输入n后： 图5：输入n后6、在初始界面后输入

17、#时： 图6：在初始界面后输入#时 六、用户使用说明在输入时候，必须为正确的表达式。否则程序将判断出错，提前结束程序。七、参考文献 1、王昆仑。数据结构与算法。北京：中国铁道出版社。2002、谭浩强。c程序设计（第三版）。北京：清华大学出版社。20053、谭浩强。c程序设计指导。北京：清华大学出版社。2005八、附录 带有注释的源程序#include #include #define maxnum 50typedef int datatype; typedef struct datatype smaxnum; int t; seqstack,*pseqstack;/定义一个类型名为seqsta

18、ck的数据类型 /*构造一个空栈*/pseqstack setstack() pseqstack stack; stack=(seqstack*)malloc(sizeof( seqstack);/强制转换数据类型 if (stack=null) printf(空间不够!n); / else stack-t=-1; return stack;/返回空栈顶 /*清空栈*/int emptystack(pseqstack stack) return stack-t=-1; /*入栈*/void push(pseqstack stack, datatype x) if (stack-t = maxn

19、um - 1) /判断栈满 printf(满溢!n); /栈满时输出“满溢!” else stack-t = stack-t+1; stack-sstack-t=x; /栈未满时元素入栈 /*出栈*/void pop(pseqstack stack) if (stack-t=-1) printf(满溢!n); /当栈空时输出“满溢!” else stack-t = stack-t-1; /当栈不空时元素出栈 /*返回栈顶元素的值*/datatype top(pseqstack stack) return stack-sstack-t; /返回栈顶元素 /*将中缀表达式转换为后缀表达式，顺利转换

20、返回1，若转换过程中发现中缀表达式非法则返回0*/ int its(const char* infix, char* suffix) int set = 0; /*set记录状态，等于1表示刚读入的是操作数，等于0表示刚读入的是运算符，*/ /*设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/ char c1, c2; pseqstack ps = setstack(); int i, j = 0; for(i=0; infixi!=0;i+) /*中缀表达式不为空时,遍历表达式*/ c1=infixi; /*把遍历到的元素指赋给c1*/ if(set=

21、1) suffixj+= ;/*读到数字时输出一个空格*/ switch(c1) case : case t: case n: break; /*遇到空格或制表符忽略*/ case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: set =1; suffixj+=c1; /*遇到数字输出*/ break; case (: push(ps, c1); /*遇到左括号，入栈*/ break; case ): c2 = ); /*遇到右括号把右括号赋值给c2*/ while(!emptystack(

22、ps) /*当栈不为空时*/ c2=top(ps); /*遇到右括号取栈顶*/ pop(ps); /*出栈*/ if(c2 =() break; /*遇到左括号时停止出栈*/ suffixj+=c2; /*c2的值放入后缀表达式中*/ if(c2 !=() /*c2不是左括号时*/ free(ps); /*释放栈内空间*/ suffixj+=0; return 0; break; case +: case -: while(!emptystack(ps) /*当栈不为空时*/ c2 = top(ps); /*将栈顶元素赋值给c2*/ if(c2 =+| c2 =-| c2 = * | c2 =

23、 /) pop(ps); /*遇到加减号时栈中栈顶元素是加减乘除四种运算符出栈*/ suffixj+ = c2; /*将c2放入后缀表达式中*/ else if(c2=() break; /*遇到加减号时栈顶元素是左括号不进行出栈*/ push(ps, c1); /*c1入栈*/ break; case *: case /: while(!emptystack(ps) /*当栈不为空时*/ c2 = top(ps); /*将栈顶元素赋值给c2*/ if(c2 = * | c2 = /) pop(ps); /*遇到乘除号时栈中栈顶元素是乘除运算符时出栈*/ suffixj+ = c2; /*将c

24、2放入后缀表达式中*/ else if(c2=+|c2=-|c2=() break; /*遇到乘除号时栈中栈顶元素是加减号和左括号时不进行出栈*/ push(ps, c1); break; default: free(ps); /*释放栈内空间*/ suffixj+ = 0; return 0; while(!emptystack(ps) /*当栈不为空*/ c2 = top(ps); /*栈顶元素赋值给c2*/ pop(ps); /*元素出栈*/ if(c2 = () /*c2值为左括号时*/ free(ps); /*释放栈内空间*/ suffixj+ = 0; return 1; suff

25、ixj+ = c2; /*将c2值放入后缀表达式中*/ free(ps); /*释放栈内空间*/ suffixj+ = 0; return 1; /*计算后缀表达式*/int calculatesuffix(const char * suffix, int * presult) int set = 0; /*set记录状态，等于1表示刚读入的是操作数，等于0表示刚读入的是运算符，*/ pseqstack ps = setstack(); int sum = 0, num1, num2; /*定义num1、num2用于操作数间的运算，并定义数据sum*/ int i; char c; for(i

26、 = 0; suffixi != 0; i+) /*中缀表达式不为空时,遍历表达式*/ c = suffixi; /*把遍历到的元素指赋给c*/ switch(c) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: if(set = 1) /*遇到操作数*/ sum = sum * 10 + c - 0; /*sum的计算*/ else /*所遇到的不是操作数*/sum = c - 0;/*sum的计算*/ set=1; break; case : caset: case n:if (

27、set = 1) push(ps, sum); /*遇到空格或制表符sum入栈*/ set = 0; break; case +: case -: case *: case /: if(set = 1) push(ps, sum); /*遇到运算符时sum入栈*/ set = 0; if(emptystack(ps) /*当栈为空*/ free(ps); /*释放栈内空间*/ return 0; num2 = top(ps); /*栈顶元素赋值给num2*/ pop(ps); /*元素出栈*/ if(emptystack(ps) /*当栈为空*/ free(ps); /*释放栈内空间*/ return 0; num1 = top(ps); /*栈顶元素赋值给num1*/ pop(ps); /*元素出栈*/ if(c = +) /*c为加号时*/ push(ps, num1 + num2); /*num1与num2的和入栈*/ if(c = -) /*c为减号时*/ push(ps, num1 - num2); /*num1与num2的差入栈*/ if(c = *) /*c为乘号时*/ pu