1106 added.

liuyubobobo · liuyubobobo · commit c826de225f1c · 2019-07-07T19:05:44.000-07:00
diff --git a/1106-Parsing-A-Boolean-Expression/cpp-1106/CMakeLists.txt b/1106-Parsing-A-Boolean-Expression/cpp-1106/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.14)
+project(D)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(D main.cpp)
diff --git a/1106-Parsing-A-Boolean-Expression/cpp-1106/main.cpp b/1106-Parsing-A-Boolean-Expression/cpp-1106/main.cpp
@@ -0,0 +1,86 @@
+/// Source : https://leetcode.com/problems/parsing-a-boolean-expression/
+/// Author : liuyubobobo
+/// Time   : 2019-06-30
+
+#include <iostream>
+#include <cassert>
+#include <vector>
+
+using namespace std;
+
+
+/// Recursion
+/// Time Complexity: O(n^2)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    bool parseBoolExpr(string exp) {
+
+        return parse(exp, 0, exp.size() - 1);
+    }
+
+private:
+    bool parse(const string& exp, int l, int r){
+
+        if(l == r) return exp[l] == 't' ? true : false;
+
+        if(exp[l] == '!') return !parse(exp, l + 2, r - 1);
+
+        vector<int> comma = get_comma(exp, l + 2, r - 1);
+
+        if(comma.size() == 0) return parse(exp, l + 2, r - 1);
+
+        vector<bool> subs = {parse(exp, l + 2, comma[0] - 1)};
+        for(int i = 0; i < comma.size(); i ++)
+            subs.push_back(parse(exp, comma[i] + 1, i + 1 == comma.size() ? r - 1 : comma[i + 1] - 1));
+
+        bool res = subs[0];
+        if(exp[l] == '&')
+            for(int i = 1; i < subs.size(); i ++) res = res && subs[i];
+        else
+            for(int i = 1; i < subs.size(); i ++) res = res || subs[i];
+        return res;
+    }
+
+    vector<int> get_comma(const string& exp, int l, int r){
+
+        vector<int> res;
+        int stack = 0;
+        for(int i = l; i <= r; i ++)
+            if(exp[i] == '(') stack ++;
+            else if(exp[i] == ')') stack --;
+            else if(exp[i] == ',' && !stack) res.push_back(i);
+        return res;
+    }
+};
+
+
+void print_bool(bool res){
+    cout << (res ? "True" : "False") << endl;
+}
+
+int main() {
+
+    string exp1 = "!(f)";
+    print_bool(Solution().parseBoolExpr(exp1));
+    // true
+
+    string exp2 = "|(f,t)";
+    print_bool(Solution().parseBoolExpr(exp2));
+    // true
+
+    string exp3 = "&(t,f)";
+    print_bool(Solution().parseBoolExpr(exp3));
+    // false
+
+    string exp4 = "|(&(t,f,t),!(t))";
+    print_bool(Solution().parseBoolExpr(exp4));
+    // false
+
+    string exp5 = "!(&(!(t),&(f),|(f)))";
+    print_bool(Solution().parseBoolExpr(exp5));
+    // true
+
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -746,13 +746,14 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 1093 | [Statistics from a Large Sample](https://leetcode.com/problems/statistics-from-a-large-sample/) | [无] | [C++](1093-Statistics-from-a-Large-Sample/cpp-1093/) | | |
 | 1094 | [Car Pooling](https://leetcode.com/problems/car-pooling/) | [无] | [C++](1094-Car-Pooling/cpp-1094/) | | |
 | 1095 | [Find in Mountain Array](https://leetcode.com/problems/find-in-mountain-array/) | [无] | [C++](1095-Find-in-Mountain-Array/cpp-1095/) | | |
-| 1096 | [Brace Expansion II](https://leetcode.com/problems/brace-expansion-ii/) | [无] | [C++](1096-Brace-Expansion-II/cpp-1096/) | | |
+| 1096 | [Brace Expansion II](https://leetcode.com/problems/brace-expansion-ii/) | [无]<br/>[缺：非递归算法] | [C++](1096-Brace-Expansion-II/cpp-1096/) | | |
 | | | | | | |
 | 1099 | [Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/) | [无] | [C++](1099-Two-Sum-Less-Than-K/cpp-1099/) | | |
 | | | | | | |
 | 1103 | [Distribute Candies to People](https://leetcode.com/problems/distribute-candies-to-people/) | [solution](https://leetcode.com/problems/distribute-candies-to-people/solution/) | [C++](1103-Distribute-Candies-to-People/cpp-1103/) | | |
 | 1104 | [Path In Zigzag Labelled Binary Tree](https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/) | [无] | [C++](1104-Path-In-Zigzag-Labelled-Binary-Tree/cpp-1104/) | | |
 | 1105 | [Filling Bookcase Shelves](https://leetcode.com/problems/filling-bookcase-shelves/) | [无] | [C++](1105-Filling-Bookcase-Shelves/cpp-1105/) | | |
+| 1106 | [Parsing A Boolean Expression](https://leetcode.com/problems/parsing-a-boolean-expression/) | [无]<br/>[缺：非递归算法] | [C++](1106-Parsing-A-Boolean-Expression/cpp-1106/) | | |
 | | | | | | |
 | 1108 | [Defanging an IP Address](https://leetcode.com/problems/defanging-an-ip-address/) | [无] | [C++](1108-Defanging-an-IP-Address/cpp-1108/) | | |
 | 1109 | [Corporate Flight Bookings](https://leetcode.com/problems/corporate-flight-bookings/) | [无] | [C++](1109-Corporate-Flight-Bookings/cpp-1009/) | | |
