A26404. 逻辑表达式
题目描述
逻辑表达式
题目描述
给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：
& 表示逻辑与运算 | 表示逻辑或运算 ^ 表示逻辑异或运算
表达式还包含三种基本逻辑值：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语言参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 >= 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 == '&') {
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;
}答案解析
//C++参考代码
#include <iostream>
#include <stack>
#include <vector>
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 >> s;
stack<Node> st;
for (int i = s.size()-1; i >= 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 == '&') {
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 << st.top().zero % MOD << endl;
return 0;
}