Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

👨‍💻 Алгоритм:

1⃣Используйте стек для отслеживания текущего уровня скобок.

2⃣Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее число, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

function countOfAtoms($formula) {
    $stack = [array()];
    $n = strlen($formula);
    $i = 0;

    while ($i < $n) {
        if ($formula[$i] == '(') {
            array_push($stack, array());
            $i++;
        } else if ($formula[$i] == ')') {
            $top = array_pop($stack);
            $i++;
            $i_start = $i;
            while ($i < $n && is_numeric($formula[$i])) {
                $i++;
            }
            $multiplicity = $i > $i_start ? intval(substr($formula, $i_start, $i - $i_start)) : 1;
            foreach ($top as $name => $count) {
                $stack[count($stack) - 1][$name] = ($stack[count($stack) - 1][$name] ?? 0) + $count * $multiplicity;
            }
        } else {
            $i_start = $i;
            $i++;
            while ($i < $n && ctype_lower($formula[$i])) {
                $i++;
            }
            $name = substr($formula, $i_start, $i - $i_start);
            $i_start = $i;
            while ($i < $n && is_numeric($formula[$i])) {
                $i++;
            }
            $multiplicity = $i > $i_start ? intval(substr($formula, $i_start, $i - $i_start)) : 1;
            $stack[count($stack) - 1][$name] = ($stack[count($stack) - 1][$name] ?? 0) + $multiplicity;
        }
    }

    $countMap = $stack[0];
    ksort($countMap);
    $result = '';
    foreach ($countMap as $name => $count) {
        $result .= $name;
        if ($count > 1) {
            $result .= $count;
        }
    }
    return $result;
}

Ставь 👍 и забирай 📚 Базу знаний