91 lines
2.3 KiB
C++
91 lines
2.3 KiB
C++
#include <iostream>
|
|
#include <stack>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
string expr;
|
|
|
|
vector<char> expr_builder;
|
|
stack<char> op_builder;
|
|
|
|
void in_order2post_order() {
|
|
for (char ele: expr) {
|
|
if (ele == '0' || ele == '1')expr_builder.push_back(ele);
|
|
else if (ele == '(')op_builder.push(ele);
|
|
else if (ele == ')') {
|
|
while (!op_builder.empty() && op_builder.top() != '(') {
|
|
expr_builder.push_back(op_builder.top());
|
|
op_builder.pop();
|
|
}
|
|
op_builder.pop();
|
|
} else if (ele == '&') {
|
|
while (!op_builder.empty() && op_builder.top() == '&') {
|
|
expr_builder.push_back(op_builder.top());
|
|
op_builder.pop();
|
|
}
|
|
op_builder.push('&');
|
|
} else if (ele == '|') {
|
|
while (!op_builder.empty() && op_builder.top() != '(') {
|
|
expr_builder.push_back(op_builder.top());
|
|
op_builder.pop();
|
|
}
|
|
op_builder.push('|');
|
|
}
|
|
}
|
|
while (!op_builder.empty()) {
|
|
expr_builder.push_back(op_builder.top());
|
|
op_builder.pop();
|
|
}
|
|
}
|
|
|
|
const int N = 1e6 + 5;
|
|
|
|
struct node {
|
|
int v, left, right;
|
|
} ast[N];
|
|
|
|
int plant_tree() {
|
|
int idx = 0;
|
|
stack<int> st;
|
|
for (auto item: expr_builder) {
|
|
if (isdigit(item)) {
|
|
ast[++idx] = {item - '0', -1, -1};
|
|
st.push(idx);
|
|
} else {
|
|
int right = st.top();
|
|
st.pop();
|
|
int left = st.top();
|
|
st.pop();
|
|
ast[++idx] = {(item == '&' ? 2 : 3), left, right};
|
|
st.push(idx);
|
|
}
|
|
}
|
|
return idx;
|
|
}
|
|
|
|
int short_circuit_and = 0, short_circuit_or = 0;
|
|
|
|
int calc(int start) {
|
|
// Digit
|
|
if (ast[start].v == 0 || ast[start].v == 1) return ast[start].v;
|
|
// Operator
|
|
int left = calc(ast[start].left);
|
|
if (left == 0 && ast[start].v == 2) { // AND operator
|
|
short_circuit_and++;
|
|
return 0;
|
|
} else if (left == 1 && ast[start].v == 3) { // OR operator
|
|
short_circuit_or++;
|
|
return 1;
|
|
}
|
|
int right = calc(ast[start].right);
|
|
return right;
|
|
}
|
|
|
|
int main() {
|
|
cin >> expr;
|
|
in_order2post_order();
|
|
int start = plant_tree();
|
|
cout << calc(start) << endl;
|
|
printf("%d %d\n", short_circuit_and, short_circuit_or);
|
|
} |