Show problems as
Classic problem #726HardHash TableStringStackSorting

Number of Atoms

Real-world version: Flat-Pack Parts Tally
Tracked in this browser only
Read Number of Atoms on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A furniture workshop writes the contents of a flat-pack kit in a compact notation, given to you as formula.

  • A part code is one capital letter followed by zero or more small letters, such as "K", "Nut" or "Bba".
  • A part code standing on its own means one of that part. A part code followed immediately by a whole number means that many of it, so "Nut2" means two nuts.
  • Any run of the notation may be wrapped in round brackets. A bracketed run followed by a whole number means the entire run is packed that many times, so "(BoltNut)3" packs three bolts and three nuts. A bracketed run with no number after it is packed once.
  • Bracketed runs may sit inside other bracketed runs, and the numbers multiply through.

Write the kit's total contents in the workshop's tidy form: every distinct part code exactly once, the codes in dictionary order, and each code followed immediately by its total quantity. A quantity of exactly one is left off, so a kit holding one hinge and five screws is written "HingeScrew5".

Return the tidy form of formula as a string. Every number written in the notation is at least 2 and carries no leading zero, and formula is always well formed.

Examples

Example 1

Input
formula = "(BoltNut)3Washer"
Output
"Bolt3Nut3Washer"

The bracketed run is packed three times, giving three bolts and three nuts, and one washer follows it. In dictionary order the codes are Bolt, Nut, Washer, and the washer's quantity of one is left off.

Example 2

Input
formula = "((Cam2Pin)3Rod)2"
Output
"Cam12Pin6Rod2"

The inner run holds two cams and one pin and is packed three times, so six cams and three pins, joined by one rod. All of that is packed twice, giving twelve cams, six pins and two rods.

Example 3

Input
formula = "BAb2"
Output
"Ab2B"

The notation names one B and two Ab. Dictionary order puts Ab before B, and B's quantity of one is left off.

Example 4

Input
formula = "(Ab2)12"
Output
"Ab24"

Two Ab sit inside the brackets and the run is packed twelve times, so the kit holds twenty-four of them.

Example 5

Input
formula = "K"
Output
"K"

A single part code with no number and no brackets, so the kit holds one K and the quantity is left off.

Constraints

  • 1 <= formula.length <= 1000
  • formula consists of English letters, digits, '(' and ')'.
  • formula is always a well formed kit notation.
  • Every number appearing in formula is at least 2 and has no leading zero.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_of_atoms(formula: str) -> str:
Java
public String countOfAtoms(String formula)

More on the same topics