Lesson in string parsing and Boolean expressions

Interesting problem by LeetCode: https://leetcode.com/problems/parsing-a-boolean-expression/

Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:

• "t", evaluating to True;
• "f", evaluating to False;
• "!(expr)", evaluating to the logical NOT of the inner expression expr;
• "&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
• "|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...

Example 1:

Input: expression = "!(f)"
Output: true

Example 2:

Input: expression = "|(f,t)"
Output: true

Example 3:

Input: expression = "&(t,f)"
Output: false

Example 4:

Input: expression = "|(&(t,f,t),!(t))"
Output: false

Constraints:

• 1 <= expression.length <= 20000
• expression[i] consists of characters in {'(', ')', '&', '|', '!', 't', 'f', ','}.
• expression is a valid expression representing a boolean, as given in the description.

The function to tokenize the string is a typical case of parsing strings with brackets, in which you need to keep track of the open/close brackets properly in order to avoid splitting the tokens at the wrong positions. The Boolean expression "learning" come into play when you’re evaluating the “AND” and “OR”: as soon as you hit one of the fundamental cases for AND (if any of the tokens evaluate to false) and OR (if any of the tokens evaluate to true), you can stop the computation and return. Worked fine. Code is  below, cheers, ACC.

public class Solution

{

    public bool ParseBoolExpr(string expression)

    {

        if (expression.Equals("t")) return true;

        if (expression.Equals("f")) return false;

        if (expression.StartsWith("!(")) return !ParseBoolExpr(expression.Substring(2, expression.Length - 3));

        if (expression.StartsWith("&("))

        {

            LinkedList<string> exp = ParseExpr(expression.Substring(2, expression.Length - 3));

            foreach (string e in exp)

            {

                bool val = ParseBoolExpr(e);

                if (!val) return false;

            }

            return true;

        }

        if (expression.StartsWith("|("))

        {

            LinkedList<string> exp = ParseExpr(expression.Substring(2, expression.Length - 3));

            foreach (string e in exp)

            {

                bool val = ParseBoolExpr(e);

                if (val) return true;

            }

            return false;

        }

        return true;

    }

    private LinkedList<string> ParseExpr(string expression)

    {

        LinkedList<string> retVal = new LinkedList<string>();

        if (String.IsNullOrEmpty(expression)) return retVal;

        int countOpenBrackets = 0;

        string token = "";

        for (int i = 0; i < expression.Length; i++)

        {

            if ((expression[i] == ',' && countOpenBrackets == 0) || i + 1 == expression.Length)

            {

                if (i + 1 == expression.Length)

                {

                    token += expression[i].ToString();

                }

                retVal.AddLast(token);

                token = "";

                continue;

            }

            else if (expression[i] == '(')

            {

                countOpenBrackets++;

            }

            else if (expression[i] == ')')

            {

                countOpenBrackets--;

            }

            token += expression[i].ToString();

        }

        return retVal;

    }

}