1106. Parsing A Boolean Expression LeetCode Solution
In this guide, you will get 1106. Parsing A Boolean Expression LeetCode Solution with the best time and space complexity. The solution to Parsing A Boolean Expression problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:
‘t’ that evaluates to true.
‘f’ that evaluates to false.
‘!(subExpr)’ that evaluates to the logical NOT of the inner expression subExpr.
‘&(subExpr1, subExpr2, …, subExprn)’ that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, …, subExprn where n >= 1.
‘|(subExpr1, subExpr2, …, subExprn)’ that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, …, subExprn where n >= 1.
Given a string expression that represents a boolean expression, return the evaluation of that expression.
It is guaranteed that the given expression is valid and follows the given rules.
Example 1:
Input: expression = “&(|(f))”
Output: false
Explanation:
First, evaluate |(f) –> f. The expression is now “&(f)”.
Then, evaluate &(f) –> f. The expression is now “f”.
Finally, return false.
Example 2:
Input: expression = “|(f,f,f,t)”
Output: true
Explanation: The evaluation of (false OR false OR false OR true) is true.
Input: expression = “!(&(f,t))”
Output: true
Explanation:
First, evaluate &(f,t) –> (false AND true) –> false –> f. The expression is now “!(f)”.
Then, evaluate !(f) –> NOT false –> true. We return true.
Constraints:
1 <= expression.length <= 2 * 104
expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.
Complexity Analysis
Time Complexity:
Space Complexity:
1106. Parsing A Boolean Expression LeetCode Solution in C++
class Solution {
public:
bool parseBoolExpr(string expression) {
int i = 0;
return parse(expression, i);
}
private:
bool parse(const string& exp, int& i) {
if (exp[i] == 't') {
++i;
return true;
}
if (exp[i] == 'f') {
++i;
return false;
}
if (exp[i] == '!') {
i += 2;
bool ans = !parse(exp, i);
++i;
return ans;
}
bool isAnd = exp[i] == '&';
bool ans = isAnd;
i += 2;
while (exp[i] != ')') {
bool parsed = parse(exp, i);
if (isAnd)
ans &= parsed;
else
ans |= parsed;
if (exp[i] == ',')
++i;
}
++i;
return ans;
}
}; /* code provided by PROGIEZ */
1106. Parsing A Boolean Expression LeetCode Solution in Java
class Solution {
public boolean parseBoolExpr(String expression) {
return dfs(expression, 0, expression.length() - 1);
}
private boolean dfs(final String expression, int s, int e) {
if (s == e)
return expression.charAt(s) == 't';
List<Boolean> exps = new ArrayList<>();
int layer = 0;
int left = 0;
char op = ' ';
for (int i = s; i <= e; ++i) {
char c = expression.charAt(i);
if (layer == 0 && (c == '!' || c == '&' || c == '|'))
op = c;
else if (c == '(' && ++layer == 1)
left = i + 1;
else if (c == ')' && --layer == 0)
exps.add(dfs(expression, left, i - 1));
else if (c == ',' && layer == 1) {
exps.add(dfs(expression, left, i - 1));
left = i + 1;
}
}
if (op == '&') {
boolean ans = true;
for (boolean exp : exps)
ans &= exp;
return ans;
}
if (op == '|') {
boolean ans = false;
for (boolean exp : exps)
ans |= exp;
return ans;
}
return !exps.get(0);
}
} // code provided by PROGIEZ
1106. Parsing A Boolean Expression LeetCode Solution in Python
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
def dfs(s: int, e: int) -> list[str]:
if s == e:
return True if expression[s] == 't' else False
exps = []
layer = 0
for i in range(s, e + 1):
c = expression[i]
if layer == 0 and c in '!&|':
op = c
elif c == '(':
layer += 1
if layer == 1:
left = i + 1
elif c == ')':
layer -= 1
if layer == 0:
exps.append(dfs(left, i - 1))
elif c == ',' and layer == 1:
exps.append(dfs(left, i - 1))
left = i + 1
if op == '|':
return functools.reduce(operator.or_, exps)
if op == '&':
return functools.reduce(operator.and_, exps)
if op == '!':
return not exps[0]
return dfs(0, len(expression) - 1) # code by PROGIEZ
