leetcode

commit b5d04334931cf217697c36889b65adf7bb3669c1
parent 20d5f52949381ac4f7ec635b5a2906809137144f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 14 Jul 2024 22:59:25 +0200

Daily Problem

Diffstat:
A
Problems/0726.cpp
 | 
99
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 100 insertions(+), 0 deletions(-)
diff --git a/Problems/0726.cpp b/Problems/0726.cpp
@@ -0,0 +1,99 @@
+class Solution {
+    enum Type {
+        Atom,
+        Number,
+        Extra,
+    };
+
+  public:
+    string countOfAtoms(const string &formula) const {
+        string res;
+
+        vector<string> tokens;
+        string crnt;
+        Type type = Extra;
+
+        for (const char c : formula) {
+            if (c == '(' || c == ')') {
+                tokens.push_back(crnt);
+                type = Extra;
+                crnt = "";
+            } else if (isdigit(c)) {
+                if (type != Number) {
+                    tokens.push_back(crnt);
+                    type = Number;
+                    crnt = "";
+                }
+            } else {
+                if (type != Atom || isupper(c)) {
+                    tokens.push_back(crnt);
+                    type = Atom;
+                    crnt = "";
+                }
+            }
+
+            crnt += c;
+        }
+        tokens.push_back(crnt);
+
+        using map_t = map<string, long long>;
+
+        map_t last_count;
+        stack<map_t> count;
+        string last_atom;
+
+        type = Extra;
+        count.push({});
+        tokens.erase(tokens.begin());
+        for (const auto &token : tokens) {
+            if (token[0] == '(') {
+                if (type == Atom) count.top()[last_atom]++;
+                count.push({});
+                type = Extra;
+            } else if (token[0] == ')') {
+                if (type == Atom) count.top()[last_atom]++;
+                last_count = std::move(count.top());
+                count.pop();
+                type = Extra;
+            } else {
+                if (isdigit(token[0])) {
+                    const auto value = stoll(token);
+                    if (type == Extra) {
+                        for (auto &[_, v] : last_count)
+                            v *= value;
+                    } else {
+                        count.top()[last_atom] += value;
+                    }
+                }
+
+                if (type == Extra) {
+                    for (const auto &[k, v] : last_count) {
+                        count.top()[k] += v;
+                    }
+                    last_count = {};
+                }
+
+                if (isdigit(token[0]))
+                    type = Number;
+                else {
+                    if (type == Atom) count.top()[last_atom]++;
+                    last_atom = token;
+                    type = Atom;
+                }
+            }
+        }
+
+        if (type == Extra) {
+            for (const auto &[k, v] : last_count)
+                count.top()[k] += v;
+        } else if (type == Atom)
+            count.top()[last_atom]++;
+
+        for (const auto &[e, c] : count.top()) {
+            res += e;
+            if (c > 1) res += to_string(c);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -475,6 +475,7 @@ for solving problems.
 |  0720  |   Medium   | [Longest Word in Dictionary](Problems/0720.cpp)                                                    |
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                              |
 |  0725  |   Medium   | [Split Linked List in Parts](Problems/0725.cpp)                                                    |
+|  0726  |    Hard    | [Number of Atoms](Problems/0726.cpp)                                                               |
 |  0729  |   Medium   | [My Calendar I](Problems/0729.cpp)                                                                 |
 |  0733  |    Easy    | [Flood Fill](Problems/0733.cpp)                                                                    |
 |  0735  |   Medium   | [Asteroid Collision](Problems/0735.cpp)                                                            |