比赛 CSP2022普及组 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 逻辑表达式 最终得分 100
用户昵称 zxhhh 运行时间 0.343 s
代码语言 C++ 内存使用 3.13 MiB
提交时间 2022-10-29 15:20:45
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

struct node {
	int x, acnt, ocnt;
};

stack <node> stk;
stack <char> stk2;
string s;

void add (char c) {
	node a = stk.top(); stk.pop();
	node b = stk.top(); stk.pop();
	node ans = (node){0, 0, 0};
	if (c == '|') {
		if (b.x) ans = (node){1, b.acnt, b.ocnt + 1};
		else if (a.x) ans = (node){1, b.acnt + a.acnt, b.ocnt + a.ocnt};
		else ans = (node){0, b.acnt + a.acnt, b.ocnt + a.ocnt};
	}
	else if (c == '&') {
		if (!b.x) ans = (node){0, b.acnt + 1, b.ocnt};
		else if (!a.x) ans = (node){0, b.acnt + a.acnt, b.ocnt + a.ocnt};
		else ans = (node){1, b.acnt + a.acnt, b.ocnt + a.ocnt};
	}
	stk.push(ans);
}

int main () {
	freopen("csp2022pj_expr.in", "r", stdin);
	freopen("csp2022pj_expr.out", "w", stdout);
	cin >> s;
	for (int i = 0;i < s.size();i++) {
		if (s[i] == '0' || s[i] == '1') stk.push((node){s[i] - '0', 0, 0});
		else {
			if (s[i] == ')') {
				while (stk2.size() && stk2.top() != '(') {
					char c = stk2.top(); stk2.pop();
					add(c);
				}
				stk2.pop();
			}
			else if (s[i] == '(') stk2.push(s[i]);
			else if (s[i] == '|') {
				while (stk2.size() && (stk2.top() == '|' || stk2.top() == '&')) {
					char c = stk2.top(); stk2.pop();
					add(c);
				}
				stk2.push(s[i]);
			}
			else if (s[i] == '&') {
				while (stk2.size() && stk2.top() == '&') {
					char c = stk2.top(); stk2.pop();
					add(c);
				}
				stk2.push(s[i]);
			}
		}
	}
	while (stk2.size()) {
		char c = stk2.top(); stk2.pop();
		add(c);
	}
	printf("%d\n%d %d\n", stk.top().x, stk.top().acnt, stk.top().ocnt);
	return 0;
}