数据结构实验题解：括号匹配、逆波兰式转换与循环队列操作

数据结构作业4包含了四个编程问题，涵盖了不同方面的数据结构和算法应用。 1. 括号匹配 Problem A 这个问题要求设计一个程序来检查给定的算术表达式中括号是否正确配对。输入是一个字符串，包含圆括号、方括号和花括号。算法需遍历输入，使用栈数据结构来跟踪未关闭的括号。每当遇到一个左括号，就将其压入栈中；遇到右括号时，检查栈顶的左括号是否与其匹配。如果栈为空或者不匹配，则返回"No"；否则，当所有括号都检查完后，如果栈为空，说明括号配对正确，输出"Yes"。 2. 四则元算表达式转换为逆波兰式 Problem B 在这个题目中，需要将传统的四则运算表达式转换为逆波兰表示法（也称后缀表达式），它是一种没有括号的运算表达方式。主要利用两个栈，一个用于存放操作数，另一个存放运算符。遍历输入表达式，根据操作符优先级决定是将当前操作数压栈还是直接进行计算。最后，栈中的剩余元素即为逆波兰表达式。 3. 循环队列 Problem C 循环队列是一种特殊的线性表，通过设置队尾和队头指针实现“头尾相连”。本题要求实现队满判断和入队/出队操作。队满的条件是 rear 指针加一等于 length，表示下一个位置已超出数组范围。入队时，如果队列不满，将新元素放在 rear 位置，否则丢弃新元素并输出"No"。出队时，返回并移除 length 指向的元素，同时更新 rear 和 length。 4. k阶斐波那契数列 Problem D 这个问题是关于递归和动态规划的应用，涉及k阶斐波那契数列。斐波那契数列通常定义为F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)，但在k阶版本中，可能有k个不同的初始值。算法需要设计一个递推或记忆化搜索的方法，计算k阶序列的第n项，同时确保在有限时间内和内存限制下运行。 通过这些题目，学生可以巩固对数据结构（栈、队列、递归）的理解，同时也锻炼了解决实际编程问题的能力，包括输入处理、错误处理以及优化算法以适应时间复杂度和空间限制。