算法分享02——调度场算法【简单】

介绍调度场算法是计算机科学史上的经典算法之一由Dijkstra听到这个名字大家应该都不陌生吧发明不仅应用广泛也是考试面试的重要内容。算法应用场景是在编译器、计算器、表达式求值等场景中的底层核心算法核心思想只用一个栈将中缀表达式转换成后缀表达式也叫逆波兰式那么在介绍这个算法前我们就得先知道有三种不同的表达式中缀表达式运算符在两个操作数中间也是我们日常使用的表达式写法前缀表达式波兰式运算符在两个操作数之前。后缀表达式逆波兰式运算符在两个操作数之后。那为什么要发明这个算法将中缀表达式转换成后缀表达式呢原因就在于中缀表达式很难直接计算而后缀表达式无优先级、无括号计算机可以通过栈就能直接计算因此这个算法就是为了解决计算机计算中缀表达式的麻烦那知道了不同的表达式及其之间的联系后我们就来看这个算法的几个核心思想算法用栈来暂存运算符而数字就之间输出到后缀表达式的结果之中去算法根据运算符优先级决定运算符入栈还是弹出到后缀表达式的结果中去括号强制改变运算符的顺序因此括号内部的内容要优先处理知道核心思想后我们还得清楚从中缀表达式转换到后缀表达式的规则运算符优先级从高到低为括号()乘除*/加减-运算符栈的比较规则当栈顶运算符优先级 ≥ 当前运算符时栈顶运算符弹出到后缀表达式的结果中而当前运算符入栈当栈顶运算符优先级 当前运算符时当前运算符直接入栈即可算法步骤准备阶段创建运算符栈用来存运算符 - * / ( )创建存放后缀表达式结果的容器。遍历中缀表达式遍历中每次都要分情况来操作遇到数字直接加入到结果之中遇到左括号(直接压入栈遇到右括号)从栈顶不停弹出运算符到结果之中直到遇到左括号(结束 注左右括号在运算符栈中经历相关操作后就直接丢弃不要加入到结果之中遇到 - * /运算符通过循环来不停比较若栈顶运算符优先级 ≥ 当前运算符这即是循环条件则弹出栈顶运算符到结果之中直到栈顶运算符优先级 当前运算符或栈已为空则当前运算符入栈注意若栈顶是(则直接入栈遍历结束将栈中剩余的所有运算符依次弹出到结果之中实例演示比如将中缀表达式1 * 3 - 4 * 2 / (5 - 1)转换成后缀表达式遍历元素操作运算符栈后缀表达式1数字送入结果中空1*栈空则直接入栈*13数字送入结果中*1 3-*优先级 -*弹出-入栈-1 3 *4数字送入结果中-1 3 * 4*-优先级 **入栈- *1 3 * 42数字送入结果中- *1 3 * 4 2/*优先级 /*弹出/入栈- /1 3 * 4 2 *(左括号直接入栈- / (1 3 * 4 2 *5数字送入结果中- / (1 3 * 4 2 * 5-栈顶是(则直接入栈- / ( -1 3 * 4 2 * 51数字送入结果中- / ( -1 3 * 4 2 * 5 1)弹栈直到遇到(故把-弹出()则直接丢弃- /1 3 * 4 2 * 5 1 -遍历结束弹出所有运算符送入结果中空1 3 * 4 2 * 5 1 - / -因此最终的后缀表达式为1 3 * 4 2 * 5 1 - / -若对结果不确定我们还可以验证验证我们可以用栈来对后缀表达式求值若得到的结果与用中缀表达式的结果一致那我就有很大的信心能够确定这个后缀表达式是正确的。而具体的计算步骤如下本文就不在具体演示了创建一个栈来暂存中间结果从左往右依次读取后缀表达式的一个字符若读入的是操作数则将其压入栈中若读入的是运算符则从栈中连续弹出两个元素进行相应的运算并将结果压入栈中注先弹出来的为运算符的右操作数而后弹出来到则为左操作数若读入结束则栈顶元素就是计算结果示例代码#includeiostream#includestack#includestringusingnamespacestd;// 判断是否为运算符boolisOperator(charc){returnc||c-||c*||c/;}// 获取运算符优先级intpriority(charc){if(c*||c/)return2;if(c||c-)return1;return0;// 代表这是括号虽然括号优先级最高但为了不同情况弹栈入栈操作逻辑的一致性还是把括号的优先级设为了 0}// 调度场算法 --- 中缀转为后缀stringFix(string inf){stackcharop;// 运算符栈string pos;// inf 为中缀表达式pos 为后缀表达式结果for(charc:inf){// 情况1数字 → 直接加入结果if(isdigit(c)){posc;}// 情况2左括号 → 入栈elseif(c(){op.push(c);}// 情况3右括号 → 弹出直到左括号elseif(c)){while(!op.empty()op.top()!(){posop.top();op.pop();}op.pop();// 丢弃左括号}// 情况4运算符 → 按优先级处理elseif(isOperator(c)){while(!op.empty()priority(op.top())priority(c)){posop.top();op.pop();}op.push(c);}}// 弹出栈中剩余运算符while(!op.empty()){posop.top();op.pop();}returnpos;}// 测试intmain(){string inf1*3-4*2/(5-1);cout后缀表达式Fix(inf)endl;// 输出13*42*51-/-return0;}复杂度分析时间复杂度O(n)空间复杂度O(n)算法优点高效简洁只用一个栈就可实现求值且时间复杂度仅O(n)化繁为简完美处理优先级、括号计算机无法直接计算的中缀表达式可瞬间转成可直接计算的后缀表达式来计算应用广泛计算器、编译器、表达式解析、脚本语言核心经典算法此算法是栈最经典的实战应用拓展还有一个小小的拓展就是上述所说的三个表达式还与表达式树有着很深的联系这三个表达式其实就对应着表达式树的三种遍历方式参考题目洛谷 P1175 表达式的转换