> 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;
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/evaluate-expression-to-true.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.