⾮抢占式优先算法例题_算法学习笔记（39）：调度场算法算术表达式打交道。⽽算术表达式根据运算符所在的位置可以分为三种表⽰⽅法：
有⼀类题⽬，需要我们与算术表达式
前缀表达式（波兰式），如(- (+ 3 (* 2 4)) 1)，Lisp语⾔就是使⽤的这种表⽰⽅法
前缀
中缀表达式，如3+2*4-1，最适合⼈阅读的表⽰⽅法
中缀
后缀表达式（逆波兰式），如3 2 4 * + 1 -，计算机处理起来⽐较⽅便
后缀
栈，让数字依次进栈，遇到运算符时，就弹出栈顶两个元素，将计算结果⼊栈，如图：
计算后缀表达式很简单，只需要维护⼀个栈
也可以⽤这种⽅法构建表达式树，但算法竞赛中⼀般不会有这样的需求。
调度场算法。
为了把较难处理的中缀表达式转化为容易处理的后缀表达式，Dijsktra（没错⼜是他）引⼊了⼀个算法，称为调度场算法
其实中缀表达式之所以难处理，本质上就是因为运算符优先级。如果我们把表达式全部按优先级加上括号，把3+5*4^2-1变成(3+(5*(4^2)))-1，很容易递归地计算。但是，“按优先级加括号”并不是很好实现，所以我们换⼀种思路，仍使⽤栈栈来解决问题。
为什么要使⽤栈？因为当我们读到a+b时，我们并不知道后⾯是a+b+c还是a+b*c，所以不能⽴刻转化为a b +，⽽要暂缓⼀步，把加号存到栈⾥，等到有了⾜够的信息时，再把它放出来。
什么时候有⾜够的信息呢，不妨倒过来想。
乘⽅是表达式⾥优先级最⾼的运算，那我们⼀读到a^b，不管b后⾯是什么运算符，都可以⽴刻把它变成a b ^。
假设乘⽅
乘法，可能有a*b^c^d^...这样的长链，但⼀旦我们读到另⼀个*或者⼀个+，形成了a*b^c^d^...*或a*b^c^d^...+的形式，前⾯那个*便可以对于乘法
放⼼地放于此符号之前。
加法也是类似，但是放出来的条件仅有读到另⼀个+。
⽽加法
优先级不低于新读⼊的运算符。当然，当表达式结束时，也要把栈⾥剩余的运算符依归纳⼀下发现，栈顶的运算符可以被弹出的条件是其优先级不低于新读⼊的运算符
次弹出。
⼀般地，我们采取这样的算法：
1. 依次按顺序读⼊，
1. 读到数字：直接输出；
2. 读到运算符：如果栈顶的运算符优先级不低于该运算符，则输出栈顶运算符并使之出栈，直到栈空或不满⾜上述条件为⽌；然后
⼊栈。
2. 当读⼊完毕时，依次输出并弹出栈顶运算符，直到栈被清空。
Wikipedia上有⼀张图⽚描绘了这个过程：
Salix alba绘制的⽰意图
处理括号
括号的优先级是多少？你可能条件反射地说，括号的优先级当然是最⾼的。但是，在调度场算法中，这样的处理会出问题——如果简单地把括号当成⼀种拥有最⾼优先级的运算符，当你读到左括号就⽴刻输出了，这当然不对。
恰恰相反，我们得把左括号的优先级当作最低。不仅如此，还必须在算法中对括号特别处理。注意，后缀表达式⾥没有括号，所以括号不应该被输出。由于括号⾥⼀定是⼀个完整的表达式，所以可以这样修改算法：
1. 依次按顺序读⼊，
1. 读到数字：直接输出；
⼀般运算符：如果栈顶的运算符优先级不低于该运算符，则输出栈顶运算符并使之出栈，直到栈空或不满⾜上述条件为⽌；
2. 读到⼀般
然后⼊栈；
左括号：直接⼊栈；
3. 读到左括号
运算符优先级图片4. 读到右括号
右括号：输出栈顶运算符并使之出栈，直到栈顶为左括号为⽌；令左括号出栈。
2. 当读⼊完毕时，依次输出并弹出栈顶运算符，直到栈被清空。
右结合运算符
右结合的运算符，例如乘⽅在某些编程语⾔（如Haskell）中就是右结合
刚刚我们谈的都是左结合运算符，但有时我们也会处理右结合
的。a^b^c会被理解为a^(b^c)⽽不是(a^b)^c。C语⾔中的赋值运算符（=）是⼀个优先级较低（⽐上⾯提到的所有运算符都低）的右结合运算符，我们⽤它来举例。
考虑这个表达式：x = y = 2 + 3 ，按照上⾯的算法，我们要先计算后⾯的y = 2 + 3，所以在遇到第⼆个=时不能弹出栈顶运算符（不然就成
了x y =），⽽要等到读⼊+时再弹出。这样我们就看出左结合与右结合的区别了：仅仅在于读⼊优先级相同的运算符时是否弹出。
存在右结合运算符的算法如下：
1. 依次按顺序读⼊，
1. 读到数字：直接输出；
不低于该运算符，则输出栈顶运算符并使之出栈，直到栈空或不满⾜上述条件为左结合运算符：如果栈顶的运算符优先级不低于
2. 读到左结合
⽌；然后⼊栈；
⾼于该运算符，则输出栈顶运算符并使之出栈，直到栈空或不满⾜上述条件为右结合运算符：如果栈顶的运算符优先级⾼于
3. 读到右结合
⽌；然后⼊栈；
左括号：直接⼊栈；
4. 读到左括号
右括号：输出栈顶运算符并使之出栈，直到栈顶为左括号为⽌；令左括号出栈。
5. 读到右括号
2. 当读⼊完毕时，依次输出并弹出栈顶运算符，直到栈被清空。
举⼀个例题：
（洛⾕P1175 表达式的转换）
题⽬描述
题⽬描述
平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，⽽中缀表达式就不必⽤括号了。
后缀标记法：书写表达式时采⽤运算紧跟在两个操作数之后，从⽽实现了⽆括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并⽤结果取⽽代之。
例如： 8-(3+2*6)/5+4可以写为： 8326*+5/-4+
其计算步骤为：
8 3 2 6 * + 5 / – 4 +
8 3 12 + 5 / – 4 +
8 15 5 / – 4 +
8 3 – 4 +
5 4 +
9
输⼊格式
编写⼀个程序，完成这个转换，要求输出的每⼀个数据间都留⼀个空格。 输⼊格式
就⼀⾏，是⼀个中缀表达式。输⼊的符号中只有这些基本符号 0123456789+-*/^()，并且不会出现形如 2*-3的格式。
表达式中的基本数字也都是⼀位的，不会出现形如 12形式的数字。
输出格式
所输⼊的字符串不要判错。 输出格式
输⼊
输⼊输出样例 输⼊若⼲个后缀表达式，第 I+1⾏⽐第 I⾏少⼀个运算符和⼀个操作数，最后⼀⾏只有⼀个数字，表⽰运算结果。 输⼊输出样例输出
8-(3+2*6)/5+4 输出
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
说明/提⽰
9 说明/提⽰
运算的结果可能为负数， /以整除运算。并且中间每⼀步都不会超过
。字符串长度不超过100.
#include <bits/stdc++.h>
using namespace std;
// 这⾥定义Token主要是为了使数字和运算符可以存到同⼀个容器⾥
/
/ 其实op和num同时只⽤得上⼀个值，但⽤Union的话，判断类型反⽽⿇烦。C++17的话可以考虑std::variant
struct Token
{
char op;
int num;
};
map<char, int> pre{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}}; // 优先级
int main()
{
{
string expr;
vector<Token> infix, suffix;
stack<Token> oper;
cin >> expr;
for (auto c : expr) // 将字符串解析成若⼲Token存⼊vector
{
if (isdigit(c))
infix.push_back(Token{0, c - '0'});
else
infix.push_back(Token{c, 0});
}
for (auto t : infix)
{
if (!t.op)
suffix.push_back(t);
else if (t.op == '(')
oper.push(t);
else if (t.op == ')')
{
while (!pty() && p().op != '(')
{
suffix.push_p());
oper.pop();
}
oper.pop();
}
else
{
while (!pty() && p().op] >= pre[t.op])
{
suffix.push_p());
oper.pop();
}
oper.push(t);
}
}
while (!pty())
{
suffix.push_p());
oper.pop();
}
// 这⾥对后缀表达式的计算，因为要输出中间结果，就直接开⼆重循环了，没有使⽤栈    while (suffix.size() > 1)
{
for (auto t : suffix)
if (t.op)
cout << t.op << " ";
else
cout << t.num << " ";
cout << endl;
for (int i = 2; i < suffix.size(); ++i)
{
int res;
Token a = suffix[i - 2], b = suffix[i - 1];
switch (suffix[i].op)
{
case 0:
continue;
case '+':
res = a.num + b.num;
break;
case '-':
res = a.num - b.num;
break;
case '*':
case '*':
res = a.num * b.num;
break;
case '/':
res = a.num / b.num;
break;
case '^':
res = pow(a.num, b.num);
break;
}
suffix.insert(suffix.begin() + i + 1, Token{0, res});
break;
}
}
cout << suffix[0].num; // 输出最后结果
return 0;
}
类似的题⽬还有洛⾕P1449、P1981、P2718、P1054等。Pecco：算法学习笔记（⽬录）z huanlan.zhihu

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。