毕业设计论文-基于c语言的表达式求解课程设计论文.doc

摘 要 通过数据结构这门课程，我们较深入的了解到了栈，栈是一种重要的线性结构，它广泛应用于各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。 本次试验我们将探索表达式求值问题，表达式求值是程序设计语言编译中的一个最基本的问题，它的实现是栈应用的又一个典型的例子。通过实在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。用一个一维数组存放从键盘输入的表达式,表达式中可包含：加（+）、减（-）、乘（*）、除（/）,括号（（,））等运算符。要对输入的表达式进行检查，看是否是合格的表达式，如遇到错误则终止，不进行计算；例如：括号不配对、除数不为零等；输入的表达式可以是常量表达式，也可以是变量表达式；如果是常量表达式，则直接输出结果；如果是变量表达式，通过对变量的不断赋值，计算变量取不同值时表达式的结果。参与运算的操作数可以是整型，也可以是浮点型。 关键词： 栈；先进先出；带括号的表达式；表达式求值 目 录 1绪论 1 1.1设计任务 1 1.2设计思想 1 1.3基础知识 2 2采用类c语言定义相关的数据类型 4 2.1设定栈的数据类型定义 4 2.2设定表达式求值的抽象数据类型定义： 5 3各模块的伪码算法 7 3.1存放操作符的模块： 7 3.2存放操作数的模块： 7 3.3栈的基本操作设置模块： 7 4函数的调用图 9 4.1系统总结构图 9 4.2算法模块的调用关系 9 4.3表达式求值流程图 11 5调试及测试 12 5.1调试分析 12 5.1.1调试中遇到的问题及对问题的解决方法 12 5.1.2算法的时间复杂度和空间复杂度 13 5.2测试结果 14 6源程序 21 7设 计 总 结 29 致 谢 30 参考文献 31 1绪论 1.1设计任务 （1）较熟练地掌握Ｃ语言的基本内容及程序设计的基本方法与编程技巧。? （2）较熟练地掌握在系统上编辑、编译、连接和运行C程序的方法。? （3）通过设计一个完整程序，掌握数据结构的算法编写、类C语言算法转换成C程序并上机调试的基本方法。 （4）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。?? （5）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。 1.2设计思想 表达式求值是程序设计语言编译中的一个基本问题。它的实现是栈应用的一个典型例子。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能正确解释表达式。要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：先乘除,后加减；从左算到右；先括号内,后括号外，再根据这个运算优先的规定来实现对表达式的编译或解释执行。①从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.”?，则直接将它们写入后缀表达式中。②如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。③如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。重复上述步骤直到遇到中缀表达式的结束‘\0’，弹出栈中的所有元素并放入后缀表达式中，算法结束。? 通过建立函数，完成栈的表达式求值。主函数可以调用子函数，分别完成字符的输入，字符的检验，类型转换，表达式的运算和输出信息。在主函数中可以设置调用子函数，根据输入的字符的不同，做出不同的判断，输出相应的结果。 算法设计：? （1）算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。 （2）算法输出：表达式运算结果。 （3）算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 栈是一种数据，它按照后进出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来