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
Solution: Recursion
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua class Solution { public: bool parseBoolExpr(string expression) { int s = 0; return parse(expression, s); } private: bool parse(const string& exp, int& s) { char ch = exp[s++]; if (ch == 't') return true; if (ch == 'f') return false; if (ch == '!') { bool ans = !parse(exp, ++s); ++s; return ans; } bool is_and = (ch == '&'); bool ans = is_and; ++s; while (true) { if (is_and) ans &= parse(exp, s); else ans |= parse(exp, s); if (exp[s++] == ')') break; } return ans; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { private int s; private char[] exp; public boolean parseBoolExpr(String expression) { exp = expression.toCharArray(); s = 0; return parse() == 1; } private int parse() { char ch = exp[s++]; if (ch == 't') return 1; if (ch == 'f') return 0; if (ch == '!') { ++s; int ans = 1 - parse(); ++s; return ans; } boolean is_and = (ch == '&'); int ans = is_and ? 1 : 0; ++s; while (true) { if (is_and) ans &= parse(); else ans |= parse(); if (exp[s++] == ')') break; } return ans; } } |