Public feed
#601533
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<cmath>
#include<map>
using namespace std;
int n;
string expr="";
string postfix="";
map<string,int> mp;
map<int,int> mp1;
vector<string> available;
bool cmp(string a,string b)
{
if(a.length()>b.length())
{
return false;
}
else if(a.length()<b.length()) return true;
else if(a[0]>b[0]) return false;
else return true;
}
char operat[]={'&','|','!'};
bool isOperator(char a)
{
for(int i=0;i<3;i++)
{
if(a==operat[i]) return true;
}
return false;
}
bool isOperator(string a)
{
for(int i=0;i<3;i++)
{
if(a[0]==operat[i]) return true;
}
return false;
}
int len;
string getNum(int from,int &to)
{
string num="";
int i;
int sign=0;
for(i=from;i<len;i++)
{
// if(s[i]=='-'&&i==from) sign=1;
if(expr[i]==' '||expr[i]==')'||expr[i]=='('||expr[i]=='\0'||isOperator(expr[i]))
{
break;
}
else
num+=expr[i];
}
to=i-1;
string wh=num.substr(1,num.length());
int y;
sscanf(wh.c_str(),"%d",&y);
// cout<<num<<" "<<wh<<" "<<endl;
int flag=0;
for(i=0;i<available.size();i++)
{
if(wh==available[i])
{
flag=1;
break;
}
}
if(flag==0) available.push_back(wh);
return num;
}
string toPostfix(int st,int &end)
{
string pstfx="";
stack<char> stk;
int sign=0;
for(int i=st;i<len;i++)
{
if(expr[i]=='(')
{
int e;
pstfx+=" "+toPostfix(i+1,e);
while(sign)
{
pstfx+=" !";
sign--;
}
i=e;
}
else if(expr[i]==')')
{
end=i;
while(stk.size())
{
char c=stk.top();
stk.pop();
pstfx+=" ";
pstfx+=c;
}
return pstfx;
}
else if(isOperator(expr[i]))
{
// cout<<expr[i]<<endl;
if(expr[i]=='!')
{
sign=1;
i++;
while(i<len&&expr[i]=='!')
{
sign++;
i++;
}
// if(sign>1)
i--;
}
else if(expr[i]=='&')
{
if(stk.size()&&stk.top()=='&')
{
pstfx+=" &";
}
else
{
stk.push('&');
}
}
else if(expr[i]=='|')
{
if(stk.size()&&stk.top()=='|')
{
pstfx+=" |";
}
else if(stk.size()&&stk.top()=='&')
{
while(stk.size()&&stk.top()=='&')
{
stk.pop();
pstfx+=" &";
}
if(stk.size()&&stk.top()=='|') pstfx+=" |";
else stk.push('|');
}
else { stk.push('|'); }
}
}
else
{
int e;
string num=getNum(i,e);
pstfx+=" "+num;
while(sign)
{
pstfx+=" !";
sign--;
}
i=e;
}
}
while(stk.size())
{
char c=stk.top();
stk.pop();
pstfx+=" ";
pstfx+=c;
}
return pstfx;
}
bool evaluate(int z,bitset<10> val)
{
int y=0;
int temp=z;
stack<string> stk;
stringstream ss(postfix);
string x;
int pos1,pos2;
int v1,v2,res;
string s1,s2;
char t[5];
while(ss>>x)
{
if(isOperator(x))
{
switch(x[0])
{
case '|':
s1=stk.top();
stk.pop();
s2=stk.top();
stk.pop();
if(s1[0]=='x')
{
s1=s1.substr(1,s1.length());
pos1=val[mp[s1]];
}
else
{
sscanf(s1.c_str(),"%d",&pos1);
}
if(s2[0]=='x')
{
s2=s2.substr(1,s2.length());
pos2=val[mp[s2]];
}
else
{
sscanf(s2.c_str(),"%d",&pos2);
}
res=pos1|pos2;
sprintf(t,"%d",res);
stk.push(string(t));
break;
case '&':
s1=stk.top();
stk.pop();
s2=stk.top();
stk.pop();
if(s1[0]=='x')
{
s1=s1.substr(1,s1.length());
pos1=val[mp[s1]];
}
else
{
sscanf(s1.c_str(),"%d",&pos1);
}
if(s2[0]=='x')
{
s2=s2.substr(1,s2.length());
pos2=val[mp[s2]];
}
else
{
sscanf(s2.c_str(),"%d",&pos2);
}
res=pos1&pos2;
sprintf(t,"%d",res);
stk.push(string(t));
break;
case '!':
string s1=stk.top();
stk.pop();
if(s1[0]=='x')
{
s1=s1.substr(1,s1.length());
pos1=val[mp[s1]];
}
else
{
sscanf(s1.c_str(),"%d",&pos1);
}
res=!pos1;
sprintf(t,"%d",res);
stk.push(string(t));
break;
}
// cout<<stk.top()<<endl;
}
else
{
stk.push(x);
}
}
// cout<<stk.top()<<endl;
string res1=stk.top();
if(res1[0]=='x')
{
res1=res1.substr(1,res1.length());
int k=mp[res1];
if(val[k]==1) return true;
else return false;
}
if(stk.top()=="1") return true;
else return false;
}
int main()
{
cin>>n;
char c;
while((c=getchar())!=EOF)
{
if(c!=' '&&c!='\t'&&c!='\n')
expr+=c;
}
int end;
len=expr.length();
postfix=toPostfix(0,end);
// cout<<postfix<<endl;
string av[]={"1","2","3","4","5","6","7","8","9","10"};
for(int i=0;i<n;i++)
{
int flag=1;
for(int j=0;j<available.size();j++)
{
// cout<<available[j]<<endl;
if(available[j]==av[i])
{
flag=0;
break;
}
}
if(flag==1) mp[av[i]]=0;
}
sort(available.begin(),available.end(),cmp);
// for(int i=0;i<available.size();i++) cout<<available[i]<<endl;
int rep;
rep=0;
for(int i=0;i<available.size();i++)
{
mp[available[i]]=rep++;
}
int pw=(int)pow(2.0,n*1.0);
int flag=0;
for(int i=pw-1;i>=0;i--)
{
bitset<10> val((unsigned long)i);
if(!evaluate(i,val))
{
cout<<"NO"<<endl;
flag=1;
for(int j=0;j<available.size();j++)
{
mp[available[j]]=val[mp[available[j]]];
}
for(int j=1;j<n+1;j++)
{
char t[5];
sprintf(t,"%d",j);
cout<<mp[string(t)]<<" ";
}
break;
}
}
if(flag==0)
{
cout<<"YES"<<endl;
}
cin>>n;
return 0;
}