# Open the Brackets

## 题目描述

There is a syntactically correct boolean expression.
The definition of syntactically correct expression follows as:

1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
2. If A is a correct expression, then !A and (A) are correct expressions too.
3. If A is a correct expression and B is a correct expression, then A||B, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.
Small Latin letters are variables, ! denotes negation, || – disjunction, & – conjunction, <=> – equality, => – implication, # – excepting or.
Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.
Two expressions are called identical if their values are the same in any values of variables.
Make the expression, which will be identical with given expression. New expression must be free of brackets.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

struct Solver {
private:
string s;
void input() { cin >> s; }
int len(char c) {
switch (c) {
case '!' : return 0;
case '&' : return 0;
case '|' : return 1;
case '<' : return 2;
case '=' : return 1;
case '#' : return 0;
}
}
int priority(char c) {
switch (c) {
case '!' : return 1;
case '&' : return 2;
case '|' : return 3;
case '<' : return 3;
case '=' : return 3;
case '#' : return 3;
case '(' : return 4;
}
}
bool single(bool a, char c, bool b) {
switch (c) {
case '&' : return a && b;
case '|' : return a || b;
case '<' : return a == b;
case '=' : return a || ! b;
case '#' : return a ^ b;
}
}
int match(string s, int p) {
int cnt = 1;
while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
return p;
}
stack <char> symbol;
stack <bool> number;
void pop() {
if (symbol.top() == '!') {
symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
} else {
bool p = number.top(); number.pop();
bool q = number.top(); number.pop();
number.push(single(p, symbol.top(), q));
symbol.pop();
}
}
bool calc(string s) {
for (int i = 0; i < s.length(); ++ i) {
if (isdigit(s[i])) number.push(s[i] - '0');
else if (s[i] == '(') symbol.push('(');
else if (s[i] == ')') {
while (symbol.top() != '(') pop();
symbol.pop();
} else {
while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
symbol.push(s[i]), i += len(s[i]);
}
}
while (! symbol.empty()) pop();
return number.top();
}
bool check(int p, string s) {
for (int i = 0; i < s.length(); ++ i)
if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
return calc(s);
}
void process() {
for (int i = 0; i + 1 < s.length(); ++ i)
while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
s = s.substr(0, i) + s.substr(i + 2);
string ans, sep;
for (int i = 0; i < 1 << 10; ++ i)
if (check(i, s)) {
ans += sep, sep = "||";
string s;
for (int j = 0; j < 10; ++ j) {
ans += s, s = "&";
if (! (i & 1 << j)) ans += "!";
ans += j + 'a';
}
}
if (ans.length() == 0) ans = "!a&a";
cout << ans << endl;
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot