湖南大学数据结构实验四：四则运算表达式的求值实验报告

简介：
本实验报告详细记录了湖南大学数据结构课程第四次实验的内容与过程，主要探讨并实现了四则运算表达式的求值算法，加深了对栈应用的理解。 ### 湖南大学数据结构实验4：四则运算表达式求值实验报告 #### 需求分析 本次实验的主要目标是实现一个程序，能够处理用户输入的整数四则运算表达式（中缀表达式），将其转换为后缀表达式，并计算后缀表达式的值。具体需求如下： 1. **基本功能** - 用户输入包含加减乘除运算符的整数表达式。 - 程序将输入的中缀表达式转换成后缀表达式。 - 计算并输出后缀表达式的计算结果。 2. **要求** - 使用二叉树表示表达式的结构。 - 实现从中缀到后缀的转换功能。 - 能够正确地计算出给定表达式的值。 3. **输入和输出形式** - 输入：用户在命令行界面输入一个不超过100字符长度的中缀表达式。 - 输出：如果输入格式正确，则程序将显示对应的后缀表达式及其结果；若不合法，提示重新输入。 4. **测试数据** - 正常情况示例：1+2*3 转换成 1 2 3 * + 结果为7。 - 括号使用案例：21+23*(12-6) 应输出 21 23 12 6 - *，结果是159。 - 包含负数的示例：-2+3*4 转换成 -2 3 4 * + 结果为10。 - 混合使用括号和负数：(-2)*(3+4)-5 应输出 -2 3 4 + *，结果是-19。 - 错误输入示例：如 20 或 (2+3)*2) 将提示用户重新输入。 #### 概要设计 ##### 抽象数据类型定义 1. **二叉树** - 数据对象：数值和运算符。 - 关系结构：每个节点包含左子树、右子树指针，叶子为数值，非叶结点代表操作符号。 - 基本方法： `initTree(&T)`：初始化空的二叉树。 `inOrder(T)`：中序遍历输出表达式值和运算符顺序。 `postOrder(T)`：后序遍历生成后缀表示。 2. **栈** - 数据对象：数值与操作符 - 关系结构：遵循先进后出原则的线性表。 - 基本方法： `isEmpty()` 判断是否为空。 `topVal()`: 获取当前顶部元素值。 `push(e)` 向堆栈添加一个新项 e 作为新的顶部项目。 `pop()` 移除并返回堆顶的元素。 ##### 算法设计思想 1. **预处理输入**：去掉括号，并将负数标记为特殊字符以便后续解析。 2. **合法性检查**：确保表达式格式正确无误。 3. **构建二叉树模型**：根据中缀表示创建对应的运算结构，数值作为叶节点，操作符作为分支结点。 4. **生成后缀形式**：通过遍历所建的二叉树来获得后缀字符串输出。 5. **计算结果值**：从右至左扫描后缀表达式，遇到数字时将其压入栈中；若为运算符号，则弹出栈顶两元素进行相应操作，并将新得到的结果再推回堆栈内。 6. **显示最终答案**：打印生成的后缀形式及计算后的结果。 #### 详细设计 ##### 物理数据类型 1. **二叉链表**：每个节点包括指向左右子树的指针，用于存储表达式信息。 2. **链式栈结构**：采用动态链接方式实现堆栈操作以适应不断变化的数据需求。 通过以上方案的设计与实施，可以有效地将中缀表示转化为易于计算处理的形式，并完成相应的数学运算任务。此实验不仅加深了学生对数据结构的理解，还提升了编程技巧和问题解决能力，在面对复杂表达式时尤其重要。