I solved this problem using a different technique than the ones mentioned. And I got it Accepted by the online system judge.
After figuring out the operator at the first level of the tree (Thanks to @Asiri Rathnayake for his idea), I recursively construct the expression tree. During the construction, I scan the string. If the character is '(', then I create a node with the current operator value and add it to the tree. Then, I alternate the operator and go for a deeper recursion level. If the character is 'T', then I create a node with value "True", add it to the tree and continue scanning. If the character is 'F', then I create a node with the value "False", add it to the tree and continue scanning. Finally, if the character is ')', then I return to one level up of the recursion.
At the end, I will have the expression tree completed. Now, all I need to do is a simple evaluation for the tree using basic recursive function.
Below is my C++ code:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct Node {
char value;
vector<Node*> children;
};
void ConstructTree (int &index, string X, Node *&node, int op)
{
for(; index<X.size(); index++)
{
if(X[index]=='T')
{
Node *C= new Node;
C->value='T';
node->children.push_back(C);
}
else if(X[index]=='F')
{
Node* C= new Node;
C->value='F';
node->children.push_back(C);
}
else if(X[index]=='(')
{
if(op==0)
{
Node* C= new Node;
C->value='O';
node->children.push_back(C);
}
else
{
Node* C= new Node;
C->value='A';
node->children.push_back(C);
}
index++;
ConstructTree(index,X,node->children[node->children.size()-1],1-op);
}
else
return;
}
}
bool evaluateTree(Node* node)
{
if(node->value=='T')
return true;
else if(node->value=='F')
return false;
else if(node->value=='O')
{
for(int i=0; i<node->children.size(); i++)
if(evaluateTree(node->children[i])==true)
return true;
return false;
}
else if(node->value=='A')
{
for(int i=0; i<node->children.size(); i++)
if(evaluateTree(node->children[i])==false)
return false;
return true;
}
}
int main()
{
string X;
int testCase=1;
while(cin>>X)
{
if(X=="()")
break;
int index=0;
int op=-1;
int P=0;
int max=0;
for(int i=0; i<X.size(); i++)
{
if(X[i]=='(')
P++;
if(X[i]==')')
P--;
if(P>max)
max=P;
}
if(max%2==0)
op=0; //OR
else
op=1; //AND
Node* root = new Node;
if(op==0)
root->value='O';
else
root->value='A';
index++;
ConstructTree(index,X,root,1-op);
if(evaluateTree(root))
cout<<testCase<<". true"<<endl;
else
cout<<testCase<<". false"<<endl;
testCase++;
}
}