4966 - Normalized Form

#include<bits/stdc++.h>
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define LSOne(i) (i&(-i))
#define rep(i,a,b) for(int(i)=(a);(i)<(b);i++)
#define BUG(x) {cout<<#x<<" = "<<x<<endl;}
#define left(x) (x<<1)
#define right(x) ((x<<1) +1)
#define middle(s,e)(s+(e-s)/2)
#define size_tree(n) 2*(int)pow(2,ceil(log2(n)))
#define CL(A,I) (memset(A,I,sizeof(A)))
#define endl '\n'
#define PHAS(_n) (pbits[(_n)>>5] & (1u << ((_n) & 0x1f)))
#define PSET(_n) (pbits[(_n)>>5] |= (1u << ((_n) & 0x1f)))
//unsigned int pbits[200000000/32+1];

static const int INF = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const long double epsilon = 1e-15;
static const long double pi = acos((long double) -1);
using namespace std;
inline void init_io(){ios_base::sync_with_stdio(false);cin.tie(NULL);}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef long long ll;
string s;
map<int,int> m;


bool solve(int ss,int ee,int op)
{
    bool res=(op==1)?true:false;
    bool tmp;
    for(int i=ss+1;i<ee;)
    {
        if(s[i]=='(')
        {
            tmp=solve(i,m[i],1-op);
            i=m[i];
        }
        else
            tmp=(s[i]=='F')?false:true;

        if(op) res&=tmp;
        else res|=tmp;
        i++;
    }
    return res;
}


int main()
{
        int test=1;
    while (cin>>s && s.size()>2)
        {
      int idx=0;
            int deep=0;
      vector<int> q;
            m.clear();
            q.clear();
            while (idx!=s.size())
            {
                if(s[idx]=='(')
                    q.push_back(idx);
                else if(s[idx]==')')
                {
                    deep=max(deep , int(q.size()) );
                    m[q[q.size()-1]]=idx;
                    q.pop_back();
                }
                idx++;
            }
            if(solve(0,s.size()-1,deep%2))
                cout<<test<<". true\n";
            else
                cout<<test<<". false\n";
            test++;
    }
    return 0;
}