给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^： & 表示逻辑与运算； | 表示逻辑或运算； ^ 表示逻辑异或运算。表达式还包含三种基本逻辑值：0、1、?。每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？由于答案可能很大，请输出方案数模 1,000,000,007 的余数。前缀表达式的定义如下： 0、1、? 都是前缀表达式；如果 x、y 都是前缀表达式，则 &xy、|xy、^xy 都是前缀表达式；不满足以上两条规则的表达式都不是前缀表达式。输入格式单个字符串表示输入的前缀表达式。输出格式单个整数：表示答案模 1,000,000,007 的余数。输入样例1 &?? 输出样例1 3 输入样例2 ||??|||?^?|0|1&???|?? 输出样例2 4 输入样例3 |?^?|0|&??||?^?|1?? 输出样例3 64 说明提示设 |s| 表示输入字符串的长度。 50% 的数据，1 ≤ |s| < 1,000； 100% 的数据，1 ≤ |s| < 200,000。限制时间限…

C++程序题：逻辑表达式

给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：

表达式还包含三种基本逻辑值：0、1、?。每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？由于答案可能很大，请输出方案数模 1,000,000,007 的余数。前缀表达式的定义如下：

输入格式

单个字符串表示输入的前缀表达式。

输出格式

单个整数：表示答案模 1,000,000,007 的余数。

输入样例1

&??

输出样例1

输入样例2

||??|||?^?|0|1&???|??

输出样例2

输入样例3

|?^?|0|&??||?^?|1??

输出样例3

说明提示

设 |s| 表示输入字符串的长度。

50% 的数据，1 ≤ |s| < 1,000；

100% 的数据，1 ≤ |s| < 200,000。

限制

时间限制：1000，内存限制：512000