数据结构实验报告3-栈与队列-中缀表达式求值-实验内容及要求.docx

从键盘输入中缀表达式，建立操作数与运算符堆栈，计算并输出表达式的求值结果。 基本要求：实现 +, -, *, /四个二元运算符以及（）； 操作数范围为0至9。 提高要求：实现+, -两个一元运算符（即正、负号）； 操作数可为任意整型值（程序可不考虑计算溢出）。 若两个整数相除，结果只保留整数商（余数丢弃）；每位同学可选择实现基本要求或者提高要求；程序可不处理表达式语法错误。 ### 数据结构实验报告知识点 #### 实验背景与目标 本次实验是关于数据结构的一个实践案例——利用栈这一数据结构来实现中缀表达式的求值。实验的主要目的是让学生深入理解栈的基本概念及其在解决实际问题中的应用，特别是如何利用栈来进行表达式的解析与计算。 #### 实验内容与要求 实验要求学生编写一个程序，该程序能够从标准输入读取一个中缀表达式，并通过建立操作数栈和运算符栈来计算表达式的值。 ##### 基本要求 - 实现`+`, `-`, `*`, `/`四个二元运算符以及括号`()`的处理。 - 操作数的范围限制在0至9之间。 - 若两个整数相除，则结果仅保留整数部分，舍去余数。 - 程序无需处理表达式的语法错误。 ##### 提高要求 - 在基本要求的基础上，还需实现`+`和`-`的一元运算符功能（即表示正负号）。 - 操作数可以是任意整型值（无需考虑计算溢出的情况）。 #### 数据结构设计 为了实现上述功能，本实验采用了以下数据结构设计： - **操作数栈**：用于存放表达式中的操作数，数据类型为整型。 - **运算符栈**：用于存放表达式中的运算符，数据类型为字符型。 - **数组**：用来实现栈的数据结构，其中操作数和运算符分别存储在不同的数组中。 #### 算法设计 算法的核心思想是先将中缀表达式转换为后缀表达式（逆波兰表示法），然后基于后缀表达式进行求值。 1. **中缀转后缀**： - 遍历输入的中缀表达式。 - 遇到操作数时，直接输出。 - 遇到运算符或括号时，根据运算符的优先级和栈顶元素的优先级比较决定是否弹出栈顶元素并输出，直至栈为空或栈顶元素优先级小于当前运算符。 - 如果遇到左括号`(`，直接入栈；如果遇到右括号`)`，则弹出栈内元素直至遇到对应的左括号`(`为止。 - 表达式遍历结束后，将栈内剩余的运算符依次弹出并输出。 2. **后缀表达式求值**： - 遍历转换后的后缀表达式。 - 遇到操作数时，将其压入栈中。 - 遇到运算符时，从栈中弹出两个操作数，根据运算符进行相应的运算，并将结果重新压入栈中。 - 表达式遍历结束后，栈顶元素即为最终的计算结果。 #### 输入输出设计 - **输入**：用户通过键盘输入一个中缀表达式，表达式由数字、运算符（`+`, `-`, `*`, `/`）以及括号组成。输入以特殊字符`#`结束。 - **输出**：程序输出表达式的计算结果，结果为整型数据。 #### 编程语言与工具 - **编程语言**：C语言 - **开发环境**：Linux自带的vim编辑器和gcc编译器 - **输入输出库**：使用C语言标准库中的`putchar`和`printf` #### 主要函数说明 实验中定义了多个辅助函数来实现算法流程，包括但不限于： - `char pop(char* optr, int* _top)`：操作符元素退栈 - `void push(char* optr, char ch, int* _top)`：操作符元素进栈 - `char get_top(char* optr, int* _top)`：获取操作符栈顶元素 - `int pop_number(int* opnd, int* top)`：操作数元素退栈 - `void push_number(int* opnd, int number, int* top)`：操作数元素进栈 - `int get_top_number(int* opnd, int* top)`：获取操作数栈顶元素 - `int ispTransform(char c)`：栈中运算符优先级转化 - `int icpTransform(char c)`：栈外运算符优先级转化 - `int calculate(int* opnd, int* top, char ch)`：计算二元运算数值 - `void exTransform(char* optr, int* opnd, int* _top, int* top)`：中缀表达式转化为后缀表达式再求值 #### 程序测试 - **测试方法**：编写测试用例，覆盖各种可能的输入情况，包括合法和非法的中缀表达式。 - **预期结果**：对于合法的中缀表达式，程序应能正确计算出结果；对于非法的表达式，由于实验要求不处理语法错误，程序应能正常运行。 以上是对“数据结构实验报告3-栈与队列-中缀表达式求值”的知识点总结，该实验不仅加深了对栈的理解，还锻炼了编程实践能力。