调度场算法如何应用于优化？

介绍 调度场算法是计算机科学史上的经典算法之一，由 Dijkstra（听到这个名字大家应该都不陌生吧）发明，不仅应用广泛，也是考试面试的重要内容。 算法应用场景 是在编译器、计算器、表达式求值等场景中的底层核心算法 核心思想 只用一个栈将中缀表达式转换成后缀表达式（也叫逆波兰式） 那么在介绍这个算法前，我们就得先知道有三种不同的表达式： 中缀表达式：运算符在两个操作数中间，也是我们日常使用的表达式写法 前缀表达式（波兰式）：运算符在两个操作数之前。 后缀表达式（逆波兰式）：运算符在两个操作数之后。 那为什么要发明这个算法将中缀表达式转换成后缀表达式呢？原因就在于中缀表达式很难直接计算，而后缀表达式无优先级、无括号，计算机可以通过栈就能直接计算，因此这个算法就是为了解决计算机计算中缀表达式的麻烦 那知道了不同的表达式及其之间的联系后，我们就来看这个算法的几个核心思想： 算法用栈来暂存运算符，而数字就之间输出到后缀表达式的结果之中去 算法根据运算符优先级，决定运算符入栈还是弹出到后缀表达式的结果中去 括号强制改变运算符的顺序，因此括号内部的内容要优先处理 知道核心思想后，我们还得清楚从中缀表达式转换到后缀表达式的规则： 运算符优先级，从高到低为： 括号 ( ) 乘除 * / 加减 + - 运算符栈的比较规则： 当栈顶运算符优先级 ≥ 当前运算符时：栈顶运算符弹出到后缀表达式的结果中，而当前运算符入栈 当栈顶运算符优先级 < 当前运算符时：当前运算符直接入栈即可 算法步骤 准备阶段：创建运算符栈，用来存运算符 + - * / ( ) ；创建存放后缀表达式结果的容器。 遍历中缀表达式：遍历中每次都要分情况来操作： 遇到数字：直接加入到结果之中 遇到左括号 ( ：直接压入栈 遇到右括号 ) ：从栈顶不停弹出运算符到结果之中，直到遇到左括号 ( 结束 （注： 左右括号在运算符栈中经历相关操作后就直接丢弃，不要加入到结果之中） 遇到 + - * / 运算符：通过循环来不停比较：若栈顶运算符优先级 ≥ 当前运算符（这即是循环条件），则弹出栈顶运算符到结果之中；直到栈顶运算符优先级 < 当前运算符或栈已为空，则当前运算符入栈；注意，若栈顶是 ( 则直接入栈 遍历结束：将栈中剩余的所有运算符依次弹出到结果之中 实例演示 比如将中缀表达式 1 * 3 - 4 * 2 / (5 - 1) 转换成后缀表达式： 遍历元素 操作 运算符栈 后缀表达式 1 数字，送入结果中 空 1 * 栈空则直接入栈 * 1 3 数字，送入结果中 * 1 3 - * 优先级 > - ，* 弹出，- 入栈 - 1 3 * 4 数字，送入结果中 - 1 3 * 4 * - 优先级 < * ，* 入栈 - * 1 3 * 4 2 数字，送入结果中 - * 1 3 * 4 2 / * 优先级 = / ，* 弹出，/ 入栈 - / 1 3 * 4 2 * ( 左括号，直接入栈 - / ( 1 3 * 4 2 * 5 数字，送入结果中 - / ( 1 3 * 4 2 * 5 - 栈顶是 ( ，则直接入栈 - / ( - 1 3 * 4 2 * 5 1 数字，送入结果中 - / ( - 1 3 * 4 2 * 5 1 ) 弹栈直到遇到 ( ，故把 - 弹出，( ) 则直接丢弃 - / 1 3 * 4 2 * 5 1 - 遍历结束 弹出所有运算符送入结果中 空 1 3 * 4 2 * 5 1 - / - 因此最终的后缀表达式为：1 3 * 4 2 * 5 1 - / - 若对结果不确定，我们还可以验证验证： 我们可以用栈来对后缀表达式求值，若得到的结果与用中缀表达式的结果一致，那我就有很大的信心能够确定这个后缀表达式是正确的。