To find the count of each atom, we have to scan the formula from left to right, extract the atom name which may be followed by a number A, A123, Axxx or Axx123. We need to parse them and store the result in a map. The parenthesis represents the beginning of the nested formula, and the count of the nested formula will be multiplied by the number after the parenthesis (Axxx2)5 = Axxx 10.
Atom pattern:
- Atom name: Uppercase + 0 or more lowercase + 0 or more digits.
- Nested: Atoms can be grouped in parentheses
(...)with an optional multiplier after the closing parenthesis.
"HO" // H * 1, O * 1
"HO2" // H * 1, O * 2
"(HO)" // Same as HO
// All possible cases
A
A2
Axxx
Axxx234
(Axxx)
(Axxx)567
(...) // Nested
(...) // Multiple nestedWe can use a stack to store the atoms and their counts for nested atoms. Then try to parse the formula from left to right:
While i < formula.length:
if char == uppercase:
→ Parse full atom name, parse optional number, add to current count map
if char == '(':
→ Push a "sentinel" for left parenthesis to indicate a nested atom.
if char == ')':
→ Pop the stack as previous count map, parse number after ')', multiply, merge into previous count mapIn the following implementation,
iwill always stop at the last element of the atom name or the last digit of the number so that we can unify the parsing logic.
fun countOfAtoms(formula: String): String {
val n = formula.length
val stack = Stack<HashMap<String, Int>>()
var i = 0
fun parseName(): String {
val name = StringBuilder(formula[i].toString())
while (i + 1 < n && formula[i + 1].isLowerCase()) {
i++
name.append(formula[i])
}
return name.toString()
}
fun parseNumber(): Int {
var num = 0
while (i + 1 < n && formula[i + 1].isDigit()) {
i++
num = num * 10 + (formula[i] - '0')
}
// If the number is missing, we assume it is 1.
return maxOf(num, 1)
}
while (i < n) {
val c = formula[i]
if (c.isUpperCase()) {
val count = HashMap<String, Int>()
val name = parseName()
val number = parseNumber()
count[name] = number
stack.push(count)
} else if (c == '(') {
// We push a "sentinel" for left parenthesis to indicate a nested atom.
stack.push(hashMapOf("(" to -1))
} else if (c == ')') {
val number = parseNumber()
val totalCount = HashMap<String, Int>()
// We pop the stack until we find a "sentinel" for left parenthesis.
while (stack.isNotEmpty() && "(" !in stack.peek() ) {
val count = stack.pop()
for ((k, v) in count) {
totalCount[k] = (totalCount[k] ?: 0) + v * number
}
}
stack.pop() // Pop left {"(", -1}
stack.push(totalCount) // Push the merged count map
}
i++
}
// Sort the result by atom name lexicographically.
val resultCount = TreeMap<String, Int>()
while (stack.isNotEmpty()) {
val count = stack.pop()
for ((k, v) in count) {
resultCount[k] = (resultCount[k] ?: 0) + v
}
}
val result = StringBuilder()
for ((k, v) in resultCount) {
result.append(k)
if (v > 1) result.append(v.toString())
}
return result.toString()
}For the pattern (Axxx)567, we can parse the Axxx recursively, multiply the result by 567, then return the result to previous level to merge the count.
Please note that the
iis the index of the current character, and it will be the next character of the last character of the atom name or the last digit of the number. (Different from the stack solution)
Global:
- Parse atom "K", number = 4
→ {"K": 4}
- Encounter '(', enter group:
Group Level 1:
- Parse atom "O", number = 1
→ {"O": 1}
- Parse atom "N", number = 1
→ {"O": 1, "N": 1}
- Encounter '(', enter group:
Group Level 2:
- Parse atom "S", number = 1
- Parse atom "O", number = 3
→ {"S": 1, "O": 3}
- Exit group, multiplier = 2
→ {"S": 2, "O": 6}
- Merge Level 2 into Level 1:
→ {"O": 1 + 6 = 7, "N": 1, "S": 2}
- Exit group, multiplier = 4
→ {"O": 28, "N": 4, "S": 8}
- Merge into Global:
→ {"K": 4, "O": 28, "N": 4, "S": 8}| Step | Token | Action | Stack/Context |
|---|---|---|---|
| 1 | K |
Parse atom "K" |
{"K": 4} ← parseNumber = 4 |
| 2 | ( |
Start sub-group | recurse into new map |
| 3 | O |
Parse atom "O" |
{"O": 1} |
| 4 | N |
Parse atom "N" |
{"O": 1, "N": 1} |
| 5 | ( |
Start nested group | recurse into new map |
| 6 | S |
Parse atom "S" |
{"S": 1} |
| 7 | O |
Parse atom "O" |
{"S": 1, "O": 3} ← parseNumber = 3 |
| 8 | ) |
End nested group | Multiply by 2 → {"S": 2, "O": 6} |
| 9 | Merge with outer group | {"O": 1+6 = 7, "N": 1, "S": 2} |
|
| 10 | ) |
End outer group | Multiply by 4 → {"O": 28, "N": 4, "S": 8} |
| 11 | Merge with top-level | {"K": 4, "O": 28, "N": 4, "S": 8} |
fun countOfAtoms(formula: String): String {
var i = 0
val n = formula.length
// Parse the atom name, `i` will be the next character of the last character of the atom name.
fun parseName(): String {
val name = StringBuilder(formula[i].toString())
i++
while (i < n && formula[i].isLowerCase()) {
name.append(formula[i])
i++
}
return name.toString()
}
// Parse the number, `i` will be the next character of the last character of the number.
fun parseNumber(): Int {
var num = 0
while (i < n && formula[i].isDigit()) {
num = num * 10 + (formula[i] - '0')
i++
}
return maxOf(num, 1)
}
fun parse(): HashMap<String, Int> {
val count = HashMap<String, Int>()
while (i < n) {
when(val c = formula[i]) {
'(' -> {
i++ // skip `(`
val nestedCount = parse()
val multipler = parseNumber()
for ((k, v) in nestedCount) {
count[k] = (count[k] ?: 0) + v * multipler
}
}
')' -> {
i++ // skip `)`
return count
}
else -> {
val name = parseName()
val number = parseNumber()
count[name] = (count[name] ?: 0) + number
}
}
}
return count
}
val resultCount = TreeMap<String, Int>(parse())
val result = StringBuilder()
for ((k, v) in resultCount) {
result.append(k)
if (v > 1) result.append(v.toString())
}
return result.toString()
}TODO: Check https://leetcode.com/problems/number-of-atoms/editorial/#approach-4-reverse-scanning