洛谷P8815题解

对给出的表达式建立表达式树，再遍历计算两种短路次数：先计算左子树，如果短路就忽略右子树。

怎么建树：

用两个栈，一个存表达式树的操作数（结点编号、也可以同时把值算出来），一个存运算符。

一个括号就是一棵子树，最后括号内的所有东西都会变成一个值，即遇到完整括号就要立刻处理。

而括号内的表达式是按优先级算的（同优先级从左到右），计算的时候，让运算符栈保持优先级的严格单调性：

比如 1 & 1 | 0 处理到 | 的时候让 1 & 1 先算出结果

反过来 1 | 1 & 0 处理到 & 的时候就不必先计算 1 | 1

而 1 | 1 | 0 处理到第二个 | 时，也要先处理 1 | 1

所谓处理，就是从操作数栈中取出两个元素，运算符栈中取出一个符号，来连边建树

现在从左到右扫一遍表达式，一共有六种字符：( 、) 、 0、 1、 &、 |

遇到左括号，就直接入栈 遇到右括号，就一直出栈，处理到对应的左括号为止 遇到数字，就建立叶子结点 遇到运算符，就先循环查看栈顶是否优先级高于或等于当前运算符，是就进行处理，最后把运算符入栈 最后处理运算符栈中剩余的运算，时间复杂度 O(|S|)。

看我这么努力，确定不点个赞再走嘛