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

Comments

  1. AdeelJuly 26, 2019 at 8:02 AM

    This comment has been removed by a blog administrator.

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more