c++ - How many ways are there to evaluate expression to true?

Question

given a string that includes the characters ['T','F', '|', '&', '^'], such that between every two expressions (T, F), there is an operand (|,^,&), how many ways are there to put parentheses in the expression to make it True?

I go along with the recursive approach, I did a for loop that splits the expression string at every position, meaning for the string "T|F^T", at the first level of the recursion it would make two calls with "T", "F^T" and "T|F", "T".

The base case is when the string is of length 1, the number of ways would be 1 if the expression is "T", and 0 if the expression is "F".

I'm having a hard time calculating the total ways to reach a true expression.

The code is as follows:

bool exp(string e)
{
    return e=="T";
}
bool calc(bool a, bool b, char para)
{
    bool ans;
    if(para =='|') ans= a|b;
    else if(para == '&') ans= a&&b;
    else ans= a^b;
    return ans;
}
bool cntExpr(string A, int &countsub, int &cnt)
{
   // cout<<A<<endl;
    if(A.length()==1)
        if(exp(A))
        {
            countsub=1;
            return true;
        } 
        else {
            countsub =0;
            return false;
        }
    for(int i = 1;i<A.length();i+=2) //1,3,5 ->operand positions 
    {
        string l , r;
        int leftcnt=0, rightcnt=0;
        l = A.substr(0, i);
        r = A.substr(i+1,A.length()-(i+1));
        char operand = A[i];
        bool left = cntExpr(l,leftcnt, cnt);
        bool right = cntExpr(r,rightcnt, cnt);
        countsub = leftcnt+rightcnt;
        if(calc(left, right, operand))
            cnt+=countsub;
    }
    return false;
}

question from:https://stackoverflow.com/questions/66060386/how-many-ways-are-there-to-evaluate-expression-to-true

Answer 1

Waitting for answers