commit 02c169ae54d6f01f54881bd5be3af25073b9165a parent c019d3b4af649862b7562a91c8de9426b63997ff Author: Dimitrije Dobrota <mail@dimitrijedobrota.com> Date: Sun, 20 Oct 2024 17:23:33 +0200 Daily Problem Diffstat:
| A | Problems/1106.cpp | | | 45 | +++++++++++++++++++++++++++++++++++++++++++++ |
| M | README.md | | | 1 | + |
2 files changed, 46 insertions(+), 0 deletions(-)
diff --git a/Problems/1106.cpp b/Problems/1106.cpp @@ -0,0 +1,45 @@ +class Solution { + public: + bool parseBoolExpr(const string &expression) const { + bool state = false; + stack<char> op; + + const auto flush = [&](int &i) { + for (int count = 0; i < size(expression); i++) { + if (expression[i] == '(') + count++; + else if (expression[i] == ')' && count-- == 0) + break; + } + op.pop(); + }; + + for (int i = 0; i < size(expression); i++) { + switch (expression[i]) { + case 't': state = true; break; + case 'f': state = false; break; + case '!': + case '&': + case '|': op.push(expression[i]); break; + case ',': + // lazy evaluation + switch (op.top()) { + case '&': + if (!state) flush(i); + break; + case '|': + if (state) flush(i); + break; + } + break; + case ')': + if (op.top() == '!') state = !state; + + op.pop(); + break; + } + } + + return state; + } +}; diff --git a/README.md b/README.md @@ -698,6 +698,7 @@ for solving problems. | 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) | | 1104 | Medium | [Path In Zigzag Labelled Binary Tree](Problems/1104.cpp) | | 1105 | Medium | [Filling Bookcase Shelves](Problems/1105.cpp) | +| 1106 | Hard | [Parsing A Boolean Expression](Problems/1106.cpp) | | 1109 | Medium | [Corporate Flight Bookings](Problems/1109.cpp) | | 1110 | Medium | [Delete Nodes And Return Forest](Problems/1110.cpp) | | 1111 | Medium | [Maximum Nesting Depth of Two Valid Parentheses Strings](Problems/1111.cpp) |