> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/evaluate-expression-to-true.md).

# Evaluate Expression To True

Given an expression, **A**, with operands and operators **(OR , AND , XOR)**, in how many ways can you evaluate the expression to true, by grouping in different ways?

Operands are only **true** and **false**.

Return the number of ways to evaluate the expression modulo **10^3 + 3**.

**Input Format:**

```
The first and the only argument of input will contain a string, A.

The string A, may contain these characters:
    '|' will represent or operator 
    '&' will represent and operator
    '^' will represent xor operator
    'T' will represent true operand
    'F' will false
```

**Output:**

```
Return an integer, representing the number of ways to evaluate the string.
```

**Constraints:**

```
1 <= length(A) <= 150
```

**Example:**

```
Input 1:
    A = "T|F"

Output 1:
    1

Explanation 1:
    The only way to evaluate the expression is:
        => (T|F) = T 

Input 2:
    A = "T^T^F"
    
Output 2:
    0
    
Explanation 2:
    There is no way to evaluate A to a true statement.
```

```java
public class Solution {
    // The recurrence relation will look like the following :
    // some rules =>
    // or operator:
    // T|F = T
    // T|T = T
    // F|T = T
    // F|F = F

    // and operator:
    // T&F = F
    // T&T = T
    // F&T = F
    // F&F = F

    // x-or operator
    // T^T = F
    // T^F = T
    // F^T = T
    // F^F = F
    public int cnttrue(String s) {
        pair[][] dp = new pair[s.length()][s.length()];
        pair ways = getcount(s, 0, s.length() - 1, dp);
        return ways.tc;
    }

    static class pair {
        int tc;
        int fc;

        pair(int tc, int fc) {
            this.tc = tc;
            this.fc = fc;
        }
    }
    // Consider start and end as 2 pointers on a string
    public static pair getcount(String s, int st, int end, pair[][] dp) {
        if (st == end) {
            if (s.charAt(st) == 'T')
                return new pair(1, 0);
            else
                return new pair(0, 1);
        } else if (dp[st][end] != null)
            return dp[st][end];
        else {
            int tc = 0; // true count
            int fc = 0; // false count
            // Putting a "Seprator" and solving seprately one by one
            for (int i = st + 1; i < end; i += 2) {
                char op = s.charAt(i);
                pair lp = getcount(s, st, i - 1, dp);
                pair rp = getcount(s, i + 1, end, dp);
                int t = 0;
                int f = 0;
                if (op == '|') {
                    t = ((lp.tc * rp.tc) % 1003 + (lp.fc * rp.tc) % 1003 + (lp.tc * rp.fc) % 1003) % 1003;
                    f = (lp.fc * rp.fc) % 1003;
                } else if (op == '&') {
                    t = (lp.tc * rp.tc) % 1003;
                    f = ((lp.fc * rp.fc) % 1003 + (lp.fc * rp.tc) % 1003 + (lp.tc * rp.fc) % 1003) % 1003;
                } else {
                    t = ((lp.fc * rp.tc) % 1003 + (lp.tc * rp.fc) % 1003) % 1003;
                    f = ((lp.tc * rp.tc) % 1003 + (lp.fc * rp.fc) % 1003) % 1003;
                }
                tc = (tc + t) % 1003;
                fc = (fc + f) % 1003;
            }
            pair p = new pair(tc, fc);
            dp[st][end] = p;
            return p;
        }
    }
}
```