The idea is to use a stack to store the characters of the expression. We push every character except ) into the stack. When we encounter ), we pop the characters until we find (. Then we evaluate the expression inside the parentheses and push the result back to the stack.
We use
ANDto represent&,ORto represent|, andNOTto represent!for better readability.
s = AND(OR(t, f), NOT(t))
*
stack = [AND,(,OR,(,t,f]
// We pop the characters until we find `(`.
stack = [AND,(]
operator = OR
values = [t,f]
// Evaluate the expression inside the parentheses.
evaluated = t OR f = t
stack = [AND,t]
// We pop the characters until we find `(`.
so on...fun parseBoolExpr(expression: String): Boolean {
val stack = Stack<Char>()
for (c in expression) {
if (c == ')') {
// We use "true" and "false" to count 't' and 'f' respectively.
var tCount = 0
var fCount = 0
while (stack.isNotEmpty() && stack.peek() != '(') {
val c = stack.pop() // It might be 't' or 'f' or '(', or ','.
if (c == 't') tCount++
else if (c == 'f') fCount++
}
stack.pop() // Pop `(`
val logicalOperator = stack.pop()
val evaluated: Char = when (logicalOperator) {
'!' -> {
if (tCount > 0) 'f' else 't'
}
'&' -> {
if (fCount > 0) 'f' else 't'
}
'|' -> {
if (tCount > 0) 't' else 'f'
}
else -> 't'
}
stack.push(evaluated)
} else {
stack.push(c)
}
}
return if (stack.peek() == 't') true else false
}- Time Complexity:
O(n). - Space Complexity:
O(n).
For the expression, it's in a format of operator(exp1, exp2, exp3, ...), where exp1, exp2, exp3, ... are sub-expressions, which is a nested structure.
- Base case: The string is either
torf, we returntrueorfalserespectively. - Recursive case: We find the logical operator, and split the string into sub-expressions. We evaluate the sub-expressions recursively and apply the logical operator to the results.
Unit of work: "Evaluate exactly ONE logical expression and tell if it's
trueorfalse.
"OR(AND(t,f,t),NOT(t))"
OR( ← OR operator
AND(t,f,t), ← First operand (nested AND)
NOT(t) ← Second operand (nested NOT)
)
Parse tree:
OR
/ \
AND NOT
/||\ |
t f t t
Evaluation (bottom-up):
AND(t, f, t) = false
NOT(t) = false
OR(false, false) = false
// Recursive thinking:
eval("OR(AND(t,f,t),NOT(t))")
= OR(
eval("AND(t,f,t)"), ← Recursive call 1
eval("NOT(t)") ← Recursive call 2
)
= OR(
AND(t, f, t), ← Recursive call 1 returns false
NOT(t) ← Recursive call 2 returns false
)
= OR(false, false)
= falseprivate var i = 0 // `i` stops at the next start position of sub-expression.
fun parseBoolExpr(expression: String): Boolean {
val c = expression[i]
// Base case: The string is either `t` or `f`, we return `true` or `false` respectively.
if (c == 't') {
i++
return true
}
if (c == 'f') {
i++
return false
}
// Recursive case: We find the logical operator, and split the string into sub-expressions. We evaluate the sub-expressions recursively and apply the logical operator to the results.
val logicalOperator = c
i += 2 // Skip `operator` and `(`
val values = mutableListOf<Boolean>()
while (expression[i] != ')') {
values.add(parseBoolExpr(expression))
if (expression[i] == ',') i++ // Skip comma separator
}
i++ // Skip `)`
return when (logicalOperator) {
'!' -> values.first().not()
'&' -> values.all { it }
'|' -> values.any { it }
else -> false
}
}
// Or equivalent
fun parseBoolExpr(expression: String): Boolean {
when (expression[i]) {
't' -> {
i++ // Skip `t`
return true
}
'f' -> {
i++ // Skip `f`
return false
}
'!' -> {
i += 2 // Skip `!` and `(`
val result = parseBoolExpr(expression)
i++ // Skip `)`
return result.not()
}
'&' -> {
i += 2 // Skip `&` and `(`
var result = true
while (expression[i] != ')') {
result = parseBoolExpr(expression) && result
if (expression[i] == ',') i++
}
i++ // Skip `)`
return result
}
'|' -> {
i += 2 // Skip `|` and `(`
var result = false
while (expression[i] != ')') {
result = parseBoolExpr(expression) || result
if (expression[i] == ',') i++
}
i++ // Skip `)`
return result
}
else -> return false // Dummy return
}
} s = AND(OR(t, f), AND(NOT(f), t))
i ---->
eval(s) = AND( )
\ /
eval(OR(t, f)), eval(AND(NOT(f), t)) /
\ / \ /
OR(eval(t), eval(f)) AND(NOT(f), eval(t))
| | \ \
true false NOT(eval(f)) true
|
falseThis implementation is too complex, just skip it.
fun parseBoolExpr(expression: String): Boolean {
val n = expression.length
if (n == 1) {
return expression == "t"
}
// format: operator(exp1, exp2, exp3, ...)
val logicalOperator = expression[0] // opeator
// index 1 and n - 1 are '(' and ')'.
val substring = expression.substring(2, n - 1)
// We split the sub-expressions: exp1, exp2, exp3, ...
val splits = splitSubExpressions(substring)
// Evaluate the result based on operator and sub-expressions.
var result = true
if (logicalOperator == '!') {
// It should be a single character in the sub-expression.
return !parseBoolExpr(substring)
} else if (logicalOperator == '&') {
result = true
for (subExpr in splits) {
result = result && parseBoolExpr(subExpr)
}
} else if (logicalOperator == '|') {
result = false
for (subExpr in splits) {
result = result || parseBoolExpr(subExpr)
}
}
return result
}For the splitSubExpressions function, we need to split the sub-expressions based on the , character, but we need to consider the nested parentheses. For example:
// OR is the nested expression that contains comma as well, we can't simply split it by comma.
s = AND(t, OR(f, t), t), NOT(t), t, fHow to parse? There are two types in the string:
torf: We add it to the sub-expression list.operator(...): We find the matching parentheses and add it to the sub-expression list. We parse by finding outermost parentheses as same as 1021. Remove Outermost Parentheses
private fun splitSubExpressions(s: String): List<String> {
val subExprs = mutableListOf<String>()
var i = 0
while (i < s.length) {
val c = s[i]
if (c == 't' || c == 'f') {
subExprs.add(c.toString())
} else if (c == ',') {
// Skip comma
}
else {
// format: operator(...)
// `...` might contain nested parentheses.
var leftCount = 0
var start = i
var end = i
while (i < s.length) {
if (s[i] == '(') {
if (leftCount == 0) {
start = i
}
leftCount++
} else if (s[i] == ')') {
leftCount--
if (leftCount == 0) {
end = i
break
}
}
i++
}
// `start` is the `(` of the outermost parentheses, `end` is the `)` of the outermost parentheses.
subExprs.add(s.substring(start - 1, end + 1))
}
i++
}
return subExprs
}