#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

struct TreeNode
{
	union{
		char var;
		bool value;
	};
	TreeNode *rchild,*lchild;
	TreeNode(char ch,TreeNode*r=NULL,TreeNode*l=NULL)
	:var(ch),rchild(r),lchild(l){}
	TreeNode(bool val):value(val){}
};
bool isoperator(char ch)
{
	if(ch=='|'||ch=='&'||ch=='~'||ch=='('||ch==')')
		return true;
	else
	return false;
}
int GetPriority(char ch)
{
	if(ch=='~')
		return 3;
	else if(ch=='|'||ch=='&')
		return 1;
	else if(ch=='(')
		return 2;
	else if(ch=='#')
		return 0;
	else
		return -1;
}
TreeNode* PostCreatTree(char s[])
{
	stack<TreeNode*>ST;
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(isoperator(s[i]))
		{
			if(s[i]=='~')
			{	
				TreeNode *opnode =new TreeNode(s[i],ST.top());
				ST.pop();
				ST.push(opnode);
			}
			else
			{
				TreeNode *rchild=ST.top();
				ST.pop();
				TreeNode *lchild=ST.top();
				ST.pop();
				TreeNode *opnode=new TreeNode(s[i],rchild,lchild);
				ST.push(opnode);
			}
		}
		else
		{
			TreeNode*node=new TreeNode(s[i]);
			ST.push(node);
		}
	}
	return ST.top();
}
TreeNode*InCreateTree(char s[])
{
	char posts[1000]={0};
	int num=0;
	int len=strlen(s);
	stack<char>ST;	
	for(int i=0;i<len;i++)
	{
		char now=s[i];
		if(isoperator(now)==false)
		{
			posts[num++]=now;
		}
		else if(now=='(')
		{
			ST.push(now);
		}
		else if(now==')')
		{
			while(ST.top()!='(')
			{
				posts[num++]=ST.top();
				ST.pop();
			}
			ST.pop();
		}
		else if(now=='&'||now=='|'||now=='~')
		{
			while(!ST.empty()&&ST.top()!='('&&GetPriority(ST.top())>=GetPriority(now))
			{
				posts[num++]=ST.top();
				ST.pop();
			}
			ST.push(now);
		}
	}
	while(!ST.empty())
	{
		posts[num++]=ST.top();
		ST.pop();
	}
//	cout<<posts<<endl;
	return PostCreatTree(posts);
}
void Inorder(TreeNode*node)
{
	if(node!=NULL)
	{
		Inorder(node->lchild);
		cout<<node->var<<" ";
		Inorder(node->rchild);
	}
}
void Postorder(TreeNode*node)
{
	if(node!=NULL)
	{
		Postorder(node->lchild);
		Postorder(node->rchild);
		cout<<node->var<<" ";
	}
}
void Preorder(TreeNode*node)
{
	if(node!=NULL)
	{
		cout<<node->var<<" ";
		Preorder(node->lchild);
		Preorder(node->rchild);
	}
}
bool maplist[1000];
bool cal(bool A,char op,bool B)
{
	if(op=='|')
	return A|B;
	else if(op=='&')
	return A&B;
	else if(op=='~')
	return !B;
}
bool GetResult(TreeNode *p)
{
	if(p)
	{
		if(p->rchild==NULL&&p->lchild==NULL)
		{
			return maplist[p->var];
		}
		else
		{
			return cal(GetResult(p->lchild),p->var,GetResult(p->rchild));
		}
	}
	else
	{
		return NULL;
	}
}
TreeNode*root=NULL;
char maxchar;
int flag;
bool GetTrueList;
void judge(char i)
{
	if(i<maxchar)
	{
		maplist[i]=!maplist[i];
		judge(i+1);
		maplist[i]=!maplist[i];
		judge(i+1);
	}
	else
	{
		if(GetTrueList)
		{
			for(int j='A';j<maxchar;j++)
			printf("%d",maplist[j]);
			printf("真值：%d",GetResult(root));
			printf("\n");
		}
		else
		if(flag!=GetResult(root))
		{
			flag=-1;
			return;
		}
	}
}
int main()
{
	//freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
	char s[1000];	
	while(1)
	{
		root=NULL;
		maxchar=0;
		GetTrueList=false;
		memset(maplist,sizeof(maplist));
		printf("请输入逻辑表达式:");
		scanf("%s",s);
		for(int i=0;i<strlen(s);i++)
		{
			if(!isoperator(s[i]))
			maxchar=max(maxchar,s[i]);
		}
		maxchar++;
		root=InCreateTree(s);
		printf("先序遍历：");
		Inorder(root);
		printf("\n");
		printf("后序遍历：");
		Postorder(root);
		printf("\n");
		flag=GetResult(root);//得到一个起始值，根据变化情况判断
		judge('A');
		if(flag==0)
		{
			printf("永假\n");
		}
		else if(flag==1)
		{
			printf("永真\n");
		}
		else
		{
			printf("可满足式,是否显示真值表或自定义变量？（1）打印真值表（2）自定义变量\n");
			rewind(stdin);
			int is;
			scanf("%d",&is);
			if(is==2)
			{
				while(is==2)
				{
					for(char i='A';i<maxchar;i++)
					{
						printf("%c=",i);
						scanf("%d",&is);
						maplist[i]=is;			
					}
					if(GetResult(root)==true) 
					printf("当前逻辑表达式为:真\n");
					else
					printf("当前逻辑表达式为:假\n");
					printf("输入2继续，其他退出:");
					scanf("%d",&is);
				}
			}
			else
			{
				GetTrueList=true;
				for(int i='A';i<maxchar;i++)
				printf("%c",i);
				printf("\n");
				judge('A');
			}
		}
	}
	return 0;
}
/*
(A&B&C)|(C&D&~(A&B))
(A|B|C)&(C|D|~C)&(~A)&(B)&A|(A&B&C)
(A&B|C)
(A&B&C&D&E)|(F&C&G&H)|I
(A|~A)
*/