leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0726.cpp (2753B)

      1 class Solution {
      2     enum Type {
      3         Atom,
      4         Number,
      5         Extra,
      6     };
      7 
      8   public:
      9     string countOfAtoms(const string &formula) const {
     10         string res;
     11 
     12         vector<string> tokens;
     13         string crnt;
     14         Type type = Extra;
     15 
     16         for (const char c : formula) {
     17             if (c == '(' || c == ')') {
     18                 tokens.push_back(crnt);
     19                 type = Extra;
     20                 crnt = "";
     21             } else if (isdigit(c)) {
     22                 if (type != Number) {
     23                     tokens.push_back(crnt);
     24                     type = Number;
     25                     crnt = "";
     26                 }
     27             } else {
     28                 if (type != Atom || isupper(c)) {
     29                     tokens.push_back(crnt);
     30                     type = Atom;
     31                     crnt = "";
     32                 }
     33             }
     34 
     35             crnt += c;
     36         }
     37         tokens.push_back(crnt);
     38 
     39         using map_t = map<string, long long>;
     40 
     41         map_t last_count;
     42         stack<map_t> count;
     43         string last_atom;
     44 
     45         type = Extra;
     46         count.push({});
     47         tokens.erase(tokens.begin());
     48         for (const auto &token : tokens) {
     49             if (token[0] == '(') {
     50                 if (type == Atom) count.top()[last_atom]++;
     51                 count.push({});
     52                 type = Extra;
     53             } else if (token[0] == ')') {
     54                 if (type == Atom) count.top()[last_atom]++;
     55                 last_count = std::move(count.top());
     56                 count.pop();
     57                 type = Extra;
     58             } else {
     59                 if (isdigit(token[0])) {
     60                     const auto value = stoll(token);
     61                     if (type == Extra) {
     62                         for (auto &[_, v] : last_count)
     63                             v *= value;
     64                     } else {
     65                         count.top()[last_atom] += value;
     66                     }
     67                 }
     68 
     69                 if (type == Extra) {
     70                     for (const auto &[k, v] : last_count) {
     71                         count.top()[k] += v;
     72                     }
     73                     last_count = {};
     74                 }
     75 
     76                 if (isdigit(token[0]))
     77                     type = Number;
     78                 else {
     79                     if (type == Atom) count.top()[last_atom]++;
     80                     last_atom = token;
     81                     type = Atom;
     82                 }
     83             }
     84         }
     85 
     86         if (type == Extra) {
     87             for (const auto &[k, v] : last_count)
     88                 count.top()[k] += v;
     89         } else if (type == Atom)
     90             count.top()[last_atom]++;
     91 
     92         for (const auto &[e, c] : count.top()) {
     93             res += e;
     94             if (c > 1) res += to_string(c);
     95         }
     96 
     97         return res;
     98     }
     99 };