70pts求调,代码清晰
查看原帖
70pts求调,代码清晰
371409
Dangerise楼主2023/10/18 13:55
#include <bits/stdc++.h>
using namespace std;

struct Node {
	int l = -1, r = -1;
	char f = 0;
	bool v;
};

Node node[2002000];
int ns;

string s;
int n;

//建立一个子树
inline int add_val(bool v) {
	node[ns].v = v, node[ns].f = 0;
	ns++;
	return ns - 1;
}

int r;

int parse();

//解析一个子树
int pch() {
	int idx;
	if (s[r] == ')') {
		r--;
		idx = parse();
		assert(s[r] == '(');
		r--;
	} else {
		assert(s[r] == '0' || s[r] == '1');
		bool v = s[r] - '0';
		idx = add_val(v);
		r--;
	}
	return idx;
}

//解析表达式&建树
int parse() {
	assert(r >= 0);
	Node t;
	t.r = pch();
	if (r < 0 || s[r] == '(') {
		return t.r;
	}
	t.f = s[r--];
	bool kd = (s[r] == ')');
	t.l = parse();

	node[ns++] = t;

	//解决优先级问题
	if (node[ns - 1].l != -1 && !kd) {
		int l = node[ns - 1].l;
		if (node[ns - 1].f == '&' && node[l].f == '|') {
			node[ns - 1].l = node[l].r;
			node[l].r = ns - 1;
			return l;
		}
	}

	return ns - 1;
}

//int k = 0;

//打印函数
void dfs(int rt) {
	if (node[rt].f) {
//		int c = k++;
		printf("(");
		if (node[rt].l != -1) {
			dfs(node[rt].l);
		}
		putchar(node[rt].f);
		if (node[rt].r != -1) {
			dfs(node[rt].r);
		}
		printf(")");
	} else {
		putchar('0' + node[rt].v);
	}
}

int a1, a2;
//计算表达式
bool calc(int rt) {
	if (node[rt].f) {
		bool l = calc(node[rt].l);
		if (node[rt].f == '|' && l == 1) {
			a2++;
			return l;
		} else if (node[rt].f == '&' && l == 0) {
			a1++;
			return l;
		}
		bool r = calc(node[rt].r);
		if (node[rt].f == '|') {
			return l || r;
		} else if (node[rt].f == '&') {
			return l && r;
		}
		printf("Panic : %d\n", node[rt].f);
		exit(0);
	} else {
		return node[rt].v;
	}
}
//(1|0)&(1&1)|(1|0&1)
//1&1|1|1&1
//1&1|1&1&1

int main() {
	cin >> s;
	n = s.size();
	r = n - 1;

	int rt = parse();

//	for (int i = 0; i < n; i++) {
//		printf("%d l:%d r:%d : ", i, node[i].l, node[i].r);
//		dfs(i);
//		putchar('\n');
//	}
//	printf("\n\n");
//
//	printf("%d\n", rt);
//
//	dfs(rt);
//	putchar('\n');

	//以下输出为答案
	int res = calc(rt);
	printf("%d\n%d %d\n", res, a1, a2);
	return 0;
}
2023/10/18 13:55
加载中...