栈的应用表达式求值的设计

《栈的应用表达式求值的设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告（2014）数据结构课程设计报告栈的应用：表达式求值专业计算机科学与技术学生姓名班级学号指导教师完成日期2014年7月4日1数据结构课程设计报告（2014）目录1设计内容12设计分析12.1后缀表达式设计12.2中缀到后缀的转换设计23设计实践33.1实现要求33.2程序代码34测试方法174.1测试目的174.2测试输入174.3正确输出184.4实际输出185程序运行效果186设计心得191数据结构课程设计报告（2014）栈的应用：表达式求值的设计1设计内容设计一个表达式求值的程

2、序。该程序必须可以接受包含(,),+,-,*,/,%,和^（求幂运算符，a^b=ab）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件在文件的结尾处停止。输出要求：对于每个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值，也可能是错误信息“ERRORININFIXNOTATION”。2设计分析在计算机中

3、，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式求值程序的最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操作数。输入的表达式是由操作数（又称运算对象）和运算符以及改变运算次序的圆括号连接而成的式子。算术表达式有中缀表示法和后缀表示法，本程序输入的表达式采用中缀表示法，在这种表达式中，二元运算符位于两个操作数中间。由于不同运算符之间存在优先级，同一优先级的运算间又存在着运算结合顺序的问题，所以简单的从左到右的计算是不充分的。当然凭直观判断一个中缀表达式中哪个运算符最先，哪个次之，哪

4、个最后并不困难，但通过计算机处理就比较困难了。因为计算机只能一个字符一个字符地扫描，要想知道哪个运算符先算，就必须对整个中缀表达式扫描一遍。而后缀表达式则很容易通过应用栈实现表达式的计算，这为实现表达式求值程序提供了一种直接的计算机制。2.1后缀表达式设计后缀表达式是由一系列的运算符、操作数组成的表达式，其中运算符位于两个操作数之后。后缀表达式很容易通过应用栈实现表达式的计算。其基本过程是：当输入一个操作数时，它被压入栈中，当一个运算符出现时，就从栈中弹出适当数量的操作数，对该运算进行计算，计算结果再压

5、回栈中。对于最常见的二元运算符来说，弹出的操作数只有两个。处理完整个后缀表达式之后，栈顶上的元素就是表达式的结果值。整个计算过程不需要理解计算的优先级规则。19数据结构课程设计报告（2014）2.2中缀到后缀的转换设计从上面的分析可知，后缀表达式是很容易应用栈进行计算的，但要处理的是中缀表达式。同样，也可以应用栈将中缀表达式转换为后缀表达式。此时，栈里要保存的是运算符，而在后缀表达式计算中，栈里保存的是操作数。应用栈将中缀表达式转换为后缀表达式的基本过程如下。从头到尾读取中缀表达式的每个对象，对不同对象

6、按不同的情况处理：●如果遇到空格，则认为是分隔符，不需处理。●若遇到操作数，则直接输出。●若是左括号，则将其压入至栈中。●若遇到的是右括号，表明括号的中缀表达式已经扫描完毕，把括号中的运算符退栈，并输出。●若遇到的是运算符，当该运算符的优先级大于栈顶运算符的优先级时，则把它压栈，当该运算符的优先级小于等于栈顶运算符时，将栈顶运算符退栈并输出，再比较新的栈顶运算符，按同样处理方法，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈。●若中缀表达式处理完毕，则要把栈中存留的运算符一并输出。上述处理过程

7、的一个关键是不同运算符优先级的设置。在程序实现中，可以用一个数来代表运算符的优先级，优先级数值越大，它的优先级越高，这样的优先级的比较就转换为两个数的大小比较。程序的整体算法过程分两步：第一步，从“input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果（转换后得到的后缀表达式）存放在一个temp文件中。第二步，从temp文件中读取后缀表达式，并应用操作数栈Operands计算后缀表达式结果，将结果输出到“output.txt”文件中。本程序中的栈

8、采用前面所述的带头节点的链式存储结构，涉及两种类型：用于存储运算符号的char类型的链栈以及用于存储操作数的float类型的链栈。本程序将整个求值过程分解为两个步骤：中缀表达式转换为后缀表达式、计算后缀表达式结果值。其实，可以将这两个过程统一合并在一起完成，当然也同样需要操作数和运算符这两类栈。另外，本程序中，应用函数OperatorValue来判别运算符的优先级，一种更灵活的方式是应用数组来记录各运算符的优先级。读者可应用以上思路对本程序