Number of Atoms LeetCode solution in C++

1
class Solution {
2
 public:
3
  // helper functions
4
  bool isUpper(char ch) {
5
    return ch >= 65 && ch <= 90;
6
  }
7

8
  bool isLower(char ch) {
9
    return ch >= 97 && ch <= 122;
10
  }
11

12
  bool isLetter(char ch) {
13
    return isUpper(ch) || isLower(ch);
14
  }
15

16
  bool isNumber(char ch) {
17
    return ch >= 48 && ch <= 57;
18
  }
19

20
  void addKey(map<string, long int> &count, string key, long int value) {
21
    if (count.find(key) != count.end()) {
22
      count[key] = count[key] + value;
23
    } else {
24
      count[key] = value;
25
    }
26
  }
27

28
  // very specific utility function
29
  string buildName(string formula, int &i) {
30
    string name = "";
31
    name.push_back(formula[i]);
32
    if (isUpper(formula[i])) {
33
      return name;
34
    }
35
    if (i == formula.length() - 1) {
36
      return name;
37
    }
38
    while (isLower(formula[i - 1])) {
39
      name.push_back(formula[i - 1]);
40
      i--;
41
    }
42
    name.push_back(formula[i - 1]);
43
    i--;
44
    reverse(name.begin(), name.end());
45
    return name;
46
  }
47

48
  // very specific utility function
49
  long int buildCount(string formula, int &i, vector<long int> &stack) {
50
    long int num = formula[i] - '0';
51
    long int place = 1;
52
    if (i == 0) {
53
      return num;
54
    }
55
    while (isNumber(formula[i - 1])) {
56
      place = place * 10;
57
      num = (formula[i - 1] - '0') * place + num;
58
      i--;
59
    }
60
    return num;
61
  }
62

63
  string countOfAtoms(string formula) {
64
    string ans;
65
    map<string, long int> count;
66
    vector<long int> stack;
67
    long int factor = 1;
68
    string name = "";
69
    long int num = -1; // -1 indicates a number reset, ie, count = 1
70

71
    // iterator i is passed by reference to keep track of
72
    // the substrings that are builded, ie, atom
73
    // names or numbers
74
    int i = formula.length() - 1;
75
    while (i >= 0) {
76
      // here we need the number after the bracket close. This is
77
      // either 1 or num depending on whether we built a number before
78
      if (formula[i] == ')') {
79
        if (i + 1 <= formula.length() - 1 && isNumber(formula[i + 1])) {
80
          stack.push_back(num);
81
          factor = factor * num;
82
          num = -1;
83
        } else {
84
          stack.push_back(1);
85
        }
86
      }
87
      // here is why we need a stack. Remove latest factor that was added.
88
      else if (formula[i] == '(') {
89
        factor = factor / stack.back();
90
        stack.pop_back();
91
      }
92
      // once we detect a letter, we know it can only be a word. num gives us
93
      // the atom subscript and factor gives us the molecular count.
94
      else if (isLetter(formula[i])) {
95
        name = buildName(formula, i);
96
        if (num == -1) {
97
          addKey(count, name, 1 * factor);
98
        } else {
99
          addKey(count, name, num * factor);
100
        }
101
        num = -1; // reset number
102
      } else if (isNumber(formula[i])) {
103
        num = buildCount(formula, i, stack);
104
      }
105
      i--;
106
    }
107

108
    // arrange name and count in a string
109
    map<string, long int>::iterator it;
110
    for (it = count.begin(); it != count.end(); it++) {
111
      ans = ans + it->first;
112
      if (it->second != 1) {
113
        ans = ans + to_string(it->second);
114
      }
115
    }
116
    return ans;
117
  }
118
};