中缀转后缀与任务调度算法：表达式计算与时间优化

本实验报告主要探讨了两个关键的IT领域话题：表达式求值和任务调度。首先，我们来看表达式求值部分。 1. 表达式求值技术： - **中缀表达式与前缀/后缀表达式转换**：实验关注中缀表达式（如11+22*(7-4)/3），这种表达式通常按照运算符优先级和括号规则进行计算。为了简化计算过程，实验涉及将中缀表达式转换为前缀（如+11/*22-743）和后缀（如2274-*3/11+）形式。后缀表达式（也称逆波兰表示法）避免了括号，计算时按照运算符出现的顺序进行。 - **求值算法设计**：利用栈（如`SqStack`结构体定义）实现表达式求值，其中栈用于存储操作数和运算符。中缀表达式会通过一系列步骤（如逆波兰算法，Shunting Yard算法）转换为后缀或前缀，然后逐个处理运算符和操作数，最终得到结果。 2. 任务调度： - **多任务操作系统中的调度问题**：在多用户多任务环境中，操作系统需要根据任务的特性来决定它们的执行顺序。这里设定只有一个CPU，任务需要的CPU运行时间已知，目标是找到一个执行顺序，使得所有任务的平均等待时间最短。 - **数据结构设计**：涉及到任务数据结构`struct P`，包含任务编号、提交时间、运行时间和优先级等信息。同时，`Record`结构体用于记录每个任务的运行情况，包括等待时间、开始时间、结束时间等。 - **调度算法设计**：尽管具体算法未详述，但可以推测可能基于贪心策略或动态规划，先考虑当前可用的CPU资源和任务的相对紧迫性，逐步决定每个任务的执行时间，以最小化总等待时间。 整个实验综合运用了数据结构（如栈）、算法设计以及操作系统原理，旨在提升学生对表达式处理和任务调度的理解，并锻炼他们实际编程的能力。通过这个实验，参与者不仅能学习如何高效地求解不同形式的表达式，还能掌握操作系统中的任务调度算法，这对于理解并开发高效能的软件系统至关重要。