首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13160

逻辑表达式 题目描述 给定一个逻辑表达式,以运算符做前缀的形式给出。它包含三种运算符:&、|、^: & 表示逻辑与运算 | 表示逻辑或运算 ^ 表示逻辑异或运算…

逻辑表达式

题目描述

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

& 表示逻辑与运算

| 表示逻辑或运算

^ 表示逻辑异或运算

表达式还包含三种基本逻辑值: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

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//C语言参考代码 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #define MOD 1000000007 typedef struct {    long long zero;    long long one; } Node; Node stack[200000]; int top = -1; void push(Node node) {    stack[++top] = node; } Node pop() {    return stack[top--]; } int main() {    char s[200001];    scanf("%s", s);    int len = strlen(s);    for (int i = len - 1; i &gt;= 0; i--) {        char c = s[i];        if (c == '0') {            push((Node){1, 0});        } else if (c == '1') {            push((Node){0, 1});        } else if (c == '?') {            push((Node){1, 1});        } else {            Node right = pop();            Node left = pop();            Node res = {0, 0};            if (c == '&amp;') {                res.zero = (left.zero * right.zero % MOD + left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;                res.one = left.one * right.one % MOD;            } else if (c == '|') {                res.zero = left.zero * right.zero % MOD;                res.one = (left.one * right.zero % MOD + left.zero * right.one % MOD + left.one * right.one % MOD) % MOD;            } else if (c == '^') {                res.zero = (left.zero * right.zero % MOD + left.one * right.one % MOD) % MOD;                res.one = (left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;            }            push(res);        }    }    Node result = pop();    printf("%lld\n", result.zero);    return 0; }</pre><pre class="brush:cpp;toolbar:false">//C++参考代码 #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;vector&gt; using namespace std; const int MOD = 1e9+7; struct Node {     long long zero, one;     Node(long long z=0, long long o=0) : zero(z), one(o) {} }; int main() {     string s;     cin &gt;&gt; s;     stack&lt;Node&gt; st;          for (int i = s.size()-1; i &gt;= 0; --i) {         char c = s[i];         if (c == '0') {             st.push(Node(1, 0));         } else if (c == '1') {             st.push(Node(0, 1));         } else if (c == '?') {             st.push(Node(1, 1));         } else {             Node right = st.top(); st.pop();             Node left = st.top(); st.pop();             Node res;                          if (c == '&amp;') {                 res.zero = (right.zero * left.zero % MOD +                             right.zero * left.one % MOD +                             right.one * left.zero % MOD) % MOD;                 res.one = right.one * left.one % MOD;             } else if (c == '|') {                 res.zero = right.zero * left.zero % MOD;                 res.one = (right.one * left.one % MOD +                            right.one * left.zero % MOD +                            right.zero * left.one % MOD) % MOD;             } else if (c == '^') {                 res.zero = (right.zero * left.zero % MOD +                             right.one * left.one % MOD) % MOD;                 res.one = (right.zero * left.one % MOD +                            right.one * left.zero % MOD) % MOD;             }             st.push(res);         }     }          cout &lt;&lt; st.top().zero % MOD &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。