LeetCode 726. Number of Atoms
Given a chemical formula (given as a string), return the count of each atom.
An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.
1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example,
H2O
andH2O2
are possible, butH1O2
is impossible.Two formulas concatenated together produce another formula. For example,
H2O2He3Mg4
is also a formula.A formula placed in parentheses, and a count (optionally added) is also a formula. For example,
(H2O2)
and(H2O2)3
are formulas.Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
Formula =
K4(ON(SO3)2)2
Output:
K4N2O14S4
Solution:
There are three cases then needs to be handled:
In case it is
)
then next character can be either(
or a digit. In both cases we multiply by either 1 or the digit. Before multiplying, add all the elements till(
is encountered in stack.In case of
(
then just add to stack.In case of any other character then just add to stack in the form of dictionary with its count added as value and element as key.
In the end just add all elements in the stack and sort it.
import re
class Solution:
def countOfAtoms(self, formula):
def add_up(formulas):
''' add up all the elements provided in a list'''
result = {}
for i in range(len(formulas)):
result = {f: formulas[i].get(f, 0) + result.get(f, 0) for f in set(result).union(formulas[i])}
return result
def mul_up(formula, factor):
'''multiply the formula with the factor'''
result = {}
for k, v in formula.iteritems():
result[k] = v*factor
return result
def get_matches(regex, string):
return re.match(regex, string)
formula = "(" + formula + ")"
stack = []
i = 0
while i < len(formula):
c = formula[i]
if c == "(":
stack.append(c)
i += 1
continue
elif (c == ")" and i == len(formula)-1):
cc = stack.pop()
list_add_open_element = []
while cc != "(":
list_add_open_element.append(cc)
cc = stack.pop()
stack.append(add_up(list_add_open_element))
i += 1
continue
elif (c == ")" and (i+1 < len(formula) and formula[i+1].isdigit())) or (c == ")" and (i+1 < len(formula) and formula[i+1] == "(")):
cc = stack.pop()
list_add_open_element = [] #list to add all element up to (
while cc != "(":
list_add_open_element.append(cc)
cc = stack.pop()
r = add_up(list_add_open_element)
j = i+1
factor = ""
while j < len(formula) and formula[j].isdigit():
factor += formula[j]
j += 1
if not factor:
factor = 1
i += 1
else:
i = j
cc = mul_up(r, int(factor))
stack.append(cc)
continue
element = get_matches(ur"([A-Z][a-z]?\d*)", formula[i:])
key = get_matches(ur"([A-Z][a-z]?)", element.group())
value = re.search(ur"([0-9]+)", element.group())
stack.append({key.group():(1 if not value else int(value.group()))})
i += len(key.group()) + (len(value.group()) if value else 0)
result = [(k, v) for k, v in stack[0].iteritems()]
result.sort()
return "".join(str(i) + (str(j) if int(j) > 1 else "") for i,j in result)