山东大学计科实验：栈的实现与数学表达式计算

本实验报告由山东大学计算机科学与技术学院学生武学伟完成，学号201700130033，班级2017级2班，于2018年11月4日进行。实验的主要目标是深入理解并掌握栈结构的定义、实现以及其在计算中的应用。 实验内容主要包括两部分：创建栈类并采用数组实现，以及利用栈结构计算数学表达式的值。首先，实验者需创建一个栈类，这个栈将作为基础数据结构来处理中缀表达式。在中缀表达式转化为后缀表达式（逆波兰表示法）的过程中，通过遍历输入的数学表达式，将数字直接加入后缀表达式，同时维护一个运算符栈。遇到运算符时，根据运算符优先级判断是否需要将其入栈或出栈。整个过程遵循从左到右的顺序，确保了正确的转换。 其次，后缀表达式的求值采用另一个栈，即数字栈。从后缀表达式的末尾开始处理，遇到数字就压入数字栈，遇到运算符则弹出栈顶的两个数字进行相应运算，并将结果替换掉栈顶元素。特别地，对于负号和除法操作，需要正确处理栈顶元素的顺序和取数规则。 测试一提供了一个复杂的数学表达式作为输入，展示了如何通过栈结构进行计算和解析。结果显示，实验者能够成功地将中缀表达式转换为后缀表达式，并通过栈实现计算，得到最终的结果。 通过这次实验，学生不仅加深了对栈这种线性数据结构的理解，还锻炼了解决复杂问题的算法设计能力，包括中缀表达式转后缀表达式算法的实现和后缀表达式求值的执行。这有助于提升他们在实际编程中的问题解决和数据结构运用技巧。