2012年第一学期）表达评价专业计算机科学与技术学生姓名班级学生ID导师完成日期》《1.1课程设计目的》《1.2课程设计内容》《2.1系统目标》《2.2主要功能》《2.3开发环境》 3.1 系统功能模块划分》 《3.2 系统流程图》 《4 系统详细设计》 《5.1 测试方案》 《5.2 测试结果》 《参考文献》 附录1 源程序清单 11 表达式评价 1.1 课程设计目的 1. 学生要求熟练掌握C语言的基础知识和技能。 2、了解并掌握数据结构和算法的设计方法，具有初步的独立分析和设计能力。 3、提高程序设计和调试能力。 学生通过计算机实践验证自己设计的算法的正确性。 学习有效地使用基本的调试方法来快速发现程序代码中的错误并进行修改。 4.培养算法分析能力。 分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
5、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试的基本方法和技能。 1.2 课程设计内容 设计表达评价程序。 程序必须接受并计算包含 (,)、+、-、*、/、% 和 ^（求幂运算符，a^b=ab）的中缀表达式。 如果表达式正确，则输出表达式的结果； 如果表达式非法，则输出错误消息。 系统需求分析 2.1 系统目标 设计一个使用堆栈的程序，可用于表达式求值。 程序将读取的中缀表达式转换为后缀表达式，然后读取后缀表达式，并输出结果。 输入要求：程序从“input.txt”文件中读取信息。 如果该文件中有多个中缀表达式，则每个表达式占一行，程序的读取操作在文件末尾停止。 输出要求：对于每个表达式，将其结果放入“.txt”文件的每一行中。 这些结果可能是数值（精确到小数点后两位）或错误消息“”。 2.2 main函数可以处理无变量以字符序列形式输入的实数表达式，正确处理负数和小数，判断表达式语法是否正确（包括分母不能为零的情况），正确实现表达式对混合算术运算公式的求值可以将计算中遇到的问题和结果以文件的形式存储。 2.3 开发环境系统总体设计 3.1 系统功能模块划分 1、判断操作数函数isnum()判断当前指向的字符是否为数字，是则返回“1”，否则返回“0”。
2.查找运算符优先级函数() 为了方便判断运算符优先级，首先使用该函数将不同的整数返回给不同的运算符，然后根据数字的大小来判断优先级。 '+'、'-' 具有相同的优先级并返回相同的数字，'*' 和 '/' 也是如此。 3、表达式求值函数() 该函数是根据设计思想直接完成问题需求的函数，其中调用了判断运算符的函数isnum()和计算运算符优先级的函数()。 循环结束时，弹出堆栈 2 的值并返回。 4、主函数main()定义一个数组来存储表达式的整个字符串，将返回值直接赋值给浮点类型，并输出。 5、两个栈的函数设计：栈初始化函数()()()()入栈函数()()出栈函数()()取栈顶函数()()销毁栈()()3.2系统流程图系统流程图系统流程图 4 系统详细设计 基本分析： 在计算机中，算术表达式的计算常常是利用堆栈来实现的。
因此，这个表达式求值程序最重要的数据结构就是栈。 堆栈可用于存储输入表达式的运算符和操作数。 输入表达式是由操作数、运算符和改变运算顺序的括号连接而成的公式。 表达式求值是高级语言编译中的一个基本问题，是堆栈的典型应用实例。 任何表达式都是由操作数（）、运算符（）和分隔符（）组成。 操作数可以是常量，也可以是声明为变量或常量的标识符； 运算符可分为三类：算术运算符、关系运算符、逻辑运算符； 基本分隔符包括左括号、右括号和表达式终止符等。 中缀表达式求值： 中缀表达式：每个二元运算符位于两个操作数的中间，假设操作数为整型常量，且运算符仅包括加、减、乘、除四种运算符，分隔符有 left 和右括号和表达式起止符“#”，如：#(7+15)*(23-28/4)#。 要计算一个简单的算术表达式，首先必须了解四种算术运算的规则，即：先括号内，后括号外。 运算符和分隔符可以统称为运算符，它们组成的集合称为OPS。 根据以上三个运算规则，在运算过程中，任意两个连续出现的算子θ1和θ2之间的优先级关系一定是以下三种关系之一：θ1θ2，θ1的优先级低于θ2。 θ1=θ2，θ1的优先级等于θ2。
θ1 θ2，θ1的优先级高于θ2。 实现算子优先级算法时，需要两个工作栈：一个用于存储算子；另一个用于存储算子。 另一个用于存储操作数或运算的中间结果。 算法的基本过程如下：首先初始化操作数栈和运算符栈，将表达式起始符“#”压入运算符栈； 依次读取表达式中的每个字符，如果是操作数则直接进入运算数栈，如果是运算符则与运算符栈顶运算符比较优先级，并做如下处理：如果优先级为栈顶操作符和刚才读到的操作符是一样的，解释一下左右括号的相遇，只是将栈顶操作符（左括号）出栈。 当栈顶元素和当前读取的字符均为“#”时，表示表达式起始字符“#”遇到表达式结束字符“#”，整个表达式计算结束。 ()(&);(&);(&,(″\n\on(=();while(ch!='#'||()!= '# ')if(!In(ch,OPS))(&,a);}(((),ch))(&,ch);ch=();break ; =();break;(&,&op); (&, (&,v);break; v=();(v); 后缀表达式计算：计算后缀表达式在算法上比计算中缀表达式快得多更简单。
这是因为表达式中既没有括号也没有优先级约束。 具体方法：只使用一个对象栈。 从左到右扫描表达式时，每遇到一个操作数，就将其送入堆栈存储。 每次遇到运算符时，都会从堆栈中取出两个操作数用于当前操作。 计算，然后将结果压回栈中，直到整个表达式结束，此时送入栈顶的值就是结果。 以下是计算后缀表达式的算法。 在下面的算法中，假设每个表达式都是符合语法的，并且假设后缀表达式已经存储在足够大的字符数组A中，并且‘#’是结束符，为了简化问题，操作数的位数仅限于一位，并且忽略了数字串与相应数据之间的转换问题。 (char (s); while (ch!= if(ch!=)(s, ch); else (ch) =='+':
