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

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

Пример:

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

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

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

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

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

😎 Решение:

import java.util.*;

public class Solution {
    public String countOfAtoms(String formula) {
        Stack<Map<String, Integer>> stack = new Stack<>();
        stack.push(new HashMap<>());
        int n = formula.length();
        int i = 0;
        
        while (i < n) {
            if (formula.charAt(i) == '(') {
                stack.push(new HashMap<>());
                i++;
            } else if (formula.charAt(i) == ')') {
                Map<String, Integer> top = stack.pop();
                i++;
                int start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
                for (String name : top.keySet()) {
                    int count = top.get(name);
                    stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count * multiplicity);
                }
            } else {
                int start = i;
                i++;
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String name = formula.substring(start, i);
                start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
                stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);
            }
        }
        
        Map<String, Integer> countMap = stack.pop();
        StringBuilder sb = new StringBuilder();
        for (String name : new TreeMap<>(countMap).keySet()) {
            sb.append(name);
            int count = countMap.get(name);
            if (count > 1) {
                sb.append(count);
            }
        }
        return sb.toString();
    }
}

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