数据结构实验：中缀转后缀表达式及计算

"实验报告，涉及数据结构与算法课程，主要关注栈在算术表达式计算中的应用，包括中缀转后缀以及后缀表达式的求值。" 实验旨在深化理解栈这一数据结构的基本操作，如入栈、出栈、查看栈顶元素以及判断栈是否为空，并将这些操作应用于解决实际问题，即处理算术表达式的计算。实验分为两部分： 第一部分要求编写程序，将用户输入的中缀表达式（字符串形式）转换为后缀表达式。中缀表达式可以包含括号及双目运算符（加、减、乘、除、乘方）。在这个过程中，需要实现栈操作的头文件，其中栈的元素类型为字符。转换函数`Change(char *S1, char *S2)`负责中缀到后缀的转换，而主函数则负责输入输出及调用转换函数。 第二部分为选做，需要编写函数`double pute(char *str)`来计算给定的后缀表达式的值。这里，栈的元素类型改为双精度浮点数。同样，栈操作的头文件需包含在内，主函数中应加入调用求值函数并输出结果的代码。 实验报告要求填写在`report2.doc`文件中，同时需要上传源代码文件`stack1.h`、`stack2.h`（如果有的话）和`test6_2.cpp`到FTP服务器。 在算法设计上，通常采用以下步骤： 1. 初始化一个空栈。 2. 遍历输入的中缀表达式，遇到数字时，将其添加到后缀表达式中；遇到运算符时，与栈顶运算符比较优先级，如果当前运算符优先级更高或栈为空，将当前运算符压入栈；否则，将栈顶运算符弹出并添加到后缀表达式，直到当前运算符可以压栈。 3. 遇到左括号时，将其压栈；遇到右括号时，将栈顶运算符弹出并添加到后缀表达式，直到遇到相应的左括号，此时将左括号丢弃。 4. 遍历完成后，栈中剩余的运算符按优先级顺序弹出并添加到后缀表达式。 对于后缀表达式的求值，一般遵循以下策略： 1. 从左到右遍历后缀表达式，遇到数字时，压入栈；遇到运算符时，弹出栈顶的两个元素进行运算，将结果压回栈。 2. 最终栈中只剩一个元素，即为表达式的结果。 这个实验不仅锻炼了编程能力，也强化了对数据结构中栈的应用理解，特别是在解析和计算数学表达式方面。通过这个实验，学生能够更好地理解和运用栈这一抽象数据类型，提升问题解决的能力。