Solution using an LL(1) grammar
This is not the shortes nor the most readable solution, but I forced my self to use this apprach to brush up my skills in compiler theory. The main advantage of
This is not the shortes nor the most readable solution, but I forced my self to use this apprach to brush up my skills in compiler theory. The main advantage of this approach is that most of it can be automated with [well-tested and mature tools](https://en.wikipedia.org/wiki/Comparison_of_parser_generators).\n\nIf we can find an [LL(1) grammar](https://en.wikipedia.org/wiki/LL_grammar) to describe all possible formulas, it is very easy to use well-know techniques in compiler theory to parse the formula and to do all sort of analysis on it, including couting each atom.\n\nThis is the LL1 grammar that I used:\n```\nF \u2192  EF | \u03B5\nE \u2192 (F) | AN\nA \u2192 <Atom>\nN \u2192 <Number>\n```\n\nIn this grammer\n* `F` is a formula. E.g. `C5H6N2` or `Mg1(O1H)2`.\n* `E` is either\n\t* a subgroup in a formula. E.g. `(NH3)2` in `PtCl2(NH3)2`,\n\t* or element with a count after it. E.g. `Cl2` in `PtCl2(NH3)2`.\n* `A` is an atom. E.g. `C` in `C5H6N2`\n* `N` is a number following an atom or a subgroup. E.g. `6` in `C5H6N2`.\n\nOne tweek I did before parsing was that, I added the missing counts of 1\'s. For example I changed `H2O` to `H2O1` and I changed `Mg(OH)2` to `Mg1(O1H)2`.\n\nOnce the formula is parsed into an [Abstract Synax Tree (AST)](https://en.wikipedia.org/wiki/Abstract_syntax_tree), the rest is easy.\n```scala\nobject Solution {\n\n  private case class Parser(tokens: Array[String]) {\n    private var index = 0\n\n    private def consume(token: String): String = {\n      index += 1\n      tokens(index - 1)\n    }\n\n    private def lookAhead: String = if (index >= tokens.length) "$" else tokens(index)\n\n    def parseA: String = consume(lookAhead)\n\n    def parseN: Int = consume(lookAhead).toInt\n\n    def parseE: E = lookAhead match {\n      case "(" =>\n        consume("(")\n        val f = parseF\n        consume(")")\n        E1(f, parseN)\n      case _ =>\n        E2(parseA, parseN)\n    }\n\n    def parseF: F = lookAhead match {\n      case "$" | ")" => FNil\n      case _ => F1(parseE, parseF)\n    }\n  }\n\n  def countOfAtoms(formula: String): String = {\n    val tokens = (splitPattern.findAllIn(formula).toArray :+ "$")\n      .sliding(2, 1)\n      .flatMap(addMissingCounts).toArray\n\n    Parser(tokens).parseF.elementCounts.toList.map {\n      case (e, 1) => s"$e"\n      case (e, n) => s"$e$n"\n    }.sorted.mkString\n  }\n\n  // Boilerplate code that can be auto-generated from the grammar\n\n  private val splitPattern = """([A-Z]{1}[a-z]?|\\(|\\)|\\d+)""".r\n\n  private trait AST {\n    def elementCounts: Map[String, Int]\n  }\n\n  private abstract class F extends AST\n\n  private case class F1(e: E, f: F) extends F {\n    override def elementCounts: Map[String, Int] = {\n      e.elementCounts ++ f.elementCounts.map { case (k, v) => k -> (v + e.elementCounts.getOrElse(k, 0)) }\n    }\n  }\n\n  private object FNil extends F {\n    override def elementCounts: Map[String, Int] = Map.empty.withDefaultValue(0)\n  }\n\n  private abstract class E extends AST\n\n  private case class E1(f: F, n: Int) extends E {\n    override def elementCounts: Map[String, Int] = f.elementCounts.mapValues(v => v * n)\n  }\n\n  private case class E2(a: String, n: Int) extends E {\n    override def elementCounts: Map[String, Int] = Map[String, Int](a -> n).withDefaultValue(0)\n  }\n\n\n  private final def isAtom(token: String): Boolean = token.head.isLetter\n\n  private final def isNumber(token: String): Boolean = token.head.isDigit\n\n  private final def addMissingCounts(tokenParis: Array[String]): Array[String] = {\n    tokenParis match {\n      case Array(t1, t2) if (isAtom(t1) && !isNumber(t2)) =>\n        Array(t1, "1")\n      case Array(")", t2) if !isNumber(t2) =>\n        Array(")", "1")\n      case Array(t1, _) =>\n        Array(t1)\n    }\n  }\n}\n\n```\n
[]