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 toTrue;"f", evaluating toFalse;"!(expr)", evaluating to the logical NOT of the inner expressionexpr;"&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressionsexpr1, expr2, ...;"|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressionsexpr1, 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 <= 20000expression[i]consists of characters in{'(', ')', '&', '|', '!', 't', 'f', ','}.expressionis 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.
publicclassSolution
{
publicbool ParseBoolExpr(string expression)
{
if (expression.Equals("t")) returntrue;
if (expression.Equals("f")) returnfalse;
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) returnfalse;
}
returntrue;
}
if
(expression.StartsWith("|("))
{
LinkedList<string> exp =
ParseExpr(expression.Substring(2, expression.Length - 3));
foreach (string e in exp)
{
bool val =
ParseBoolExpr(e);
if (val) returntrue;
}
returnfalse;
}
returntrue;
}
privateLinkedList<string> ParseExpr(string expression)
{
LinkedList<string> retVal = newLinkedList<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;
}
elseif (expression[i] == '(')
{
countOpenBrackets++;
}
elseif (expression[i] == ')')
{
countOpenBrackets--;
}
token += expression[i].ToString();
}
return retVal;
}
}
Comments
This comment has been removed by a blog administrator.
Reply DeletePost a Comment
[γγ¬γΌγ ]