中缀表达式求值算法实现——四川大学计算机学院作业

"四川大学计算机学院的一份关于数据结构与算法分析的实验报告，主要讨论了如何实现中缀算术表达式的求值。学生袁东昊在指导教师游洪跃的指导下进行了该课程设计，涉及内容包括算术表达式的判断、处理单目和双目运算符，以及使用两个栈来实现运算的算法。报告中还提到了运算符的优先级设定，并给出了部分源代码（文件node.h）的模板。" 这篇实验报告主要探讨了数据结构中的一个重要应用——中缀表达式求值。中缀表达式是我们日常数学计算中常见的表达方式，但计算机处理起来并不直观，因此需要转换或使用特定的算法进行求值。报告中的任务是设计一个程序，能够处理包含括号的中缀表达式，计算其值，并能对错误的表达式给出提示。 报告指出，对于中缀表达式，计算遵循特定的运算规则：首先计算乘方，然后是乘除，最后是加减。同级别的运算从左到右进行，同时优先处理括号内的运算。为了简化运算符的比较，报告中将单目运算符（+ 和 -）视为具有相同优先级的操作符，并且规定当运算符前的字符非运算符时，用'0'表示。 在实现算法的过程中，采用了两个栈——操作符栈（optr）和操作数栈（opnd）。算法的基本流程如下： 1. 清空两个栈，并在optr栈中加入一个'='作为初始符号。 2. 从输入流中读取字符ch，循环执行直到计算完成。 3. 如果ch是'='且optr栈顶也是'=', 表达式求值结束，opnd栈顶的元素即为表达式的结果。 4. 若ch不是运算符，将其放回输入流，读取操作数并放入opnd栈。 5. 如果ch是运算符，会根据其类型和优先级与optr栈顶的运算符进行比较，进行相应的操作，如处理单目运算符，检查括号匹配，或者将运算符压入optr栈等待后续运算。 报告中提到，如果遇到不匹配的括号（如'('后面跟着')'），或者当前运算符的优先级高于栈顶运算符，程序应给出错误信息。此外，当遇到'('时，会将'('压入optr栈，而遇到')'时会弹出栈顶的'('，直到找到匹配的'('，然后继续处理输入的字符。 源代码示例部分给出了一个模板文件“node.h”，通常这个文件会定义用于构建数据结构（如运算符栈和操作数栈）的节点类。但由于信息不全，无法看到完整的实现细节，但可以推测它可能包含了对节点数据的存储和操作的相关函数。 这份实验报告详细介绍了如何利用数据结构和算法来解决中缀表达式求值的问题，涵盖了栈的应用、运算符优先级以及错误处理等方面，对于理解和实践数据结构与算法有着实际的指导意义。