#include <fstream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
char s[10000];
enum Type
{
value,
operation,
identifier
};
enum Operation
{
and,
or,
not,
eq,
impl,
braceop,
bracecl
};
map<Operation, int> prior;
int vals[256];
vector<char> all;
struct Tok
{
union {
Operation op;
char id;
bool val;
};
Tok() {};
Type type;
Tok(bool v)
{
val = v;
type = value;
}
Tok(Operation o)
{
op = o;
type = operation;
}
Tok(char c)
{
id = c;
type = identifier;
if (vals[(unsigned int)c] == -1)
{
all.push_back(c);
vals[(unsigned int)c] = 0;
}
}
void print()
{
/*
if (type == value) cout <<val;
if (type == operation)
{
switch (op)
{
case not :
cout <<'!'; break;
case and :
cout <<'&'; break;
case or :
cout <<'|'; break;
case eq :
cout <<'='; break;
case impl:
cout <<"=>"; break;
default:
assert(false);
}
}
if (type == identifier) cout <<id;
*/
}
};
vector<Tok> poland;
void input()
{
cin.getline(s, 10000);
//cout <<s<<endl;
}
bool nextToken(Tok & t)
{
static int idx = 0;
while (s[idx] == ' ') ++idx;
if (s[idx] == 0) return false;
if ((s[idx] >= 'a') && (s[idx] <= 'z') || (s[idx] >= 'A') && (s[idx] <= 'Z'))
{
t = Tok(s[idx++]);
return true;
}
switch (s[idx])
{
case '(':
t = Tok(braceop); break;
case ')':
t = Tok(bracecl); break;
case '&':
t = Tok(and); break;
case '|':
t = Tok(or); break;
case '~':
t = Tok(not); break;
case '=':
if (s[idx+1] == '>')
{
t = Tok(impl); ++idx;
}
else
t = Tok(eq);
break;
case '0':
t = Tok(false);break;
case '1':
t = Tok(true);break;
default: assert(false);
};
++idx;
return true;
}
stack<Tok> operandStack;
stack<Tok> operationStack;
void moveOp()
{
if (poland.size() > 0)
{
poland.push_back(operationStack.top());
operationStack.pop();
}
}
void printPoland()
{
/*
int i;
for (i = 0;i != poland.size();++i)
poland[i].print();
cout <<endl;
*/
}
void makepoland()
{
prior[not] = 0;
prior[and] = 1;
prior[or] = 2;
prior[impl] = 3;
prior[eq] = 4;
prior[braceop] = 5;
prior[bracecl] = 6;
Tok t;
while (nextToken(t))
{
if (t.type == value || t.type == identifier)
poland.push_back(t);
else
{
assert(t.type == operation);
switch (t.op)
{
case braceop:
operationStack.push(t);
break;
case bracecl:
{
while (operationStack.top().op != braceop)
moveOp();
operationStack.pop();
break;
}
default:
while ((poland.size() > 0) && (!operationStack.empty()) && ((prior[t.op]>=prior[operationStack.top().op])))
{
if ((t.op == impl) && (operationStack.top().op == impl)) break;
if (t.op == eq && operationStack.top().op == eq)
{
printPoland();
int i;
for (i = poland.size()-1; i >= 0;--i)
if (poland[i].type != operation) break;
assert(i >=0);
moveOp();
poland.push_back(poland[i]);
printPoland();
operationStack.push(and);
break;
}
moveOp();
}
operationStack.push(t);
}
}
}
while (!operationStack.empty())
moveOp();
while (!operandStack.empty())
{
poland.push_back(operandStack.top());
operandStack.pop();
}
printPoland();
}
void genvalues()
{
int i;
for (i = 0;i != all.size();++i)
vals[(unsigned int)all[i]] = rand() % 2;
}
bool calc()
{
bool st[10000];
int top = -1;
int i;
if (poland.size() == 0) return true;
int k = poland.size ();
for (i = 0;i != poland.size();++i)
{
switch (poland[i].type)
{
case value:
st[++top] = poland[i].val;
break;
case identifier:
st[++top] = vals[(unsigned int)poland[i].id] != 0; break;
case operation:
switch (poland[i].op)
{
case not:
{
st[top] = !st[top];
}
break;
case and:
{
assert(top>0);
st[top-1] = st[top] && st[top-1];
--top;
}
break;
case or:
{
assert(top>0);
st[top-1] = st[top] || st[top-1];
--top;
}
break;
case eq:
{
assert(top>0);
st[top-1] = st[top] == st[top-1];
--top;
}
break;
case impl:
{
assert(top>0);
st[top-1] = !st[top-1]||st[top];
--top;
}
break;
default:
assert(false);
}
};
}
assert(top == 0);
return st[0];
}
void gen(int a, int b, int idx)
{
int i;
for (i = 0; i != all.size();++i)
{
if (i == idx) vals[(unsigned int)all[i]] = a;
else vals[(unsigned int)all[i]] = b;
}
}
bool solve()
{
const int maxiter = 20000;
int i;
for (i = 0;i != all.size();++i)
{
gen(0, 1, i);
if (!calc()) return false;
gen(1, 0, i);
if (!calc()) return false;
}
gen(0, 0, 0);
if (!calc()) return false;
gen(1, 1, 0);
if (!calc()) return false;
for (i = 0; i != maxiter;++i)
{
genvalues();
if (!calc()) return false;
}
return true;
}
int main()
{
memset(vals, -1, 256*sizeof(int));
input();
makepoland();
if (solve())
{
cout <<"true";
}
else
{
cout <<"false";
if (all.size() > 0) cout <<": ";
int i;
for (i = 0;i != 256;++i)
if (vals[i] != -1)
cout << (char)i <<'='<< vals[i]<<' ';
}
return 0;
}