哈工大威海《数据结构》实验：算术表达式求值与栈的应用

在本实验中，我们探讨了如何在计算机程序设计中处理算术表达式求值问题。该实验基于哈尔滨工业大学（威海）《数据结构》课程的要求，主要关注的是如何通过栈来解决算术表达式的计算。算术表达式通常由常量、变量、运算符和括号构成，这些元素的组合使得求值过程复杂化，因为运算符具有不同的优先级和括号的存在需要考虑。 首先，实验的核心在于实现一个程序，该程序能够将输入的数学表达式字符串转换成后缀表达式，也称为逆波兰表达式（RPN）。后缀表达式的特点是运算符位于其操作数之后，这样便于利用栈的特性简化计算流程。程序需要设计两个栈：一个用于存储运算符（字符型），另一个用于存储运算数（浮点型）。当读取输入的字符时，程序会识别并处理运算符和数字，同时利用运算符栈来确定优先级，确保正确执行运算。 具体步骤如下： 1. 分析和规格说明阶段，明确了输入为包含常量、变量、运算符和括号的字符串，允许实数和特定的运算符（如+、-、*、/、^等）参与运算。输入格式还包括特殊符号#作为终止标志。 2. 当读取到一个数字时，将其压入运算数栈；遇到运算符时，比较运算符栈的栈顶元素与当前运算符的优先级，如果当前运算符优先级高，则弹出栈顶运算符并与栈顶运算数进行计算，然后将结果压回栈中；否则，将当前运算符压入运算符栈。这个过程将持续到遇到运算结束符号或到达输入的末尾。 3. 在运算结束后，输出运算结果，同时展示运算过程中运算数栈栈顶数据的变化情况，直观地展示求值过程。 4. 算法设计遵循清晰的规定，包括输入和输出的形式，以及对错误输入和未定义运算的处理。例如，如果输入包含非法字符或不完整的运算，程序应能够正确识别并给出错误提示。 5. 实验设计采用的数据结构是两个栈，一个用于操作数（ADTSqStack_f），它具有初始化、获取栈顶元素、压入元素和弹出元素的基本操作。这些操作在实现算法时被频繁调用，以保持栈的动态管理和运算的顺序执行。 此实验重点考察了如何运用栈的数据结构原理，处理算术表达式的求值问题，既锻炼了对数据结构的理解，又展示了在实际编程中的应用。通过编写并运行这样的程序，学生可以加深对运算符优先级、栈操作和表达式求值规则的理解。