[Java] [Queue/Map] Elegant recursion
There are many problems to parse string, and this one is imo the trickiest one as the format is postfixed, i.e., we need to see more to actually get how many co
There are many problems to parse string, and this one is imo the trickiest one as the format is postfixed, i.e., we need to see more to actually get how many counts are there to duplicate. So a little aggressive while loops are used here.\n\nYou see, there are only two occasions that `count` is associated with:\n1. With formula surrounded by parenthesis\n2. With a single atom\n\n```\nclass Solution {\n    public String countOfAtoms(String formula) {\n        Queue<Character> queue = new LinkedList<>();\n        \n        for (char c : formula.toCharArray()) {\n            queue.add(c);\n        }\n        \n        Map<String, Integer> result = countOfAtoms(queue);\n        \n        return transform(result);\n        \n    }\n    \n    private String transform(Map<String, Integer> map) {\n        List<String> atomNames = new ArrayList<>(map.keySet());\n        Collections.sort(atomNames);\n        \n        StringBuilder sb = new StringBuilder();\n        \n        for (String atom : atomNames) {\n            int count = map.get(atom);\n            sb.append(atom).append(count == 1 ? "" : count);\n        }\n        \n        return sb.toString();\n    }\n    \n    private Map<String, Integer> countOfAtoms(Queue<Character> queue) {\n        Map<String, Integer> map = new HashMap<>();\n        int num = 0;\n        \n        while (!queue.isEmpty()) {\n            char c = queue.poll();\n            \n            if (Character.isUpperCase(c)) {\n                StringBuilder sb = new StringBuilder();\n                sb.append(c);\n                \n                while (!queue.isEmpty() && Character.isLowerCase(queue.peek())) {\n                    sb.append(queue.poll());\n                }\n                \n                while (!queue.isEmpty() && Character.isDigit(queue.peek())) {\n                    num = (num * 10 + queue.poll() - \'0\');\n                }\n                \n                if (num == 0) num++;\n                String atom = sb.toString();\n                \n                map.put(atom, map.getOrDefault(atom, 0) + num);\n                num = 0;\n            }\n            \n            else if (c == \'(\') {\n                Map<String, Integer> sub = countOfAtoms(queue);\n                \n                while (!queue.isEmpty() && Character.isDigit(queue.peek())) {\n                    num = (num * 10 + queue.poll() - \'0\');\n                }\n                \n                if (num == 0) num++;\n\t\t\t\t\n\t\t\t\t// Merge two hash maps\n                for (Map.Entry<String, Integer> e : sub.entrySet()) {\n                    map.put(e.getKey(), map.getOrDefault(e.getKey(), 0) + (e.getValue() * num));\n                }\n                \n                num = 0;\n            }\n            \n            else if (c == \')\') {\n                break;\n            }\n        }\n        \n        return map;\n    }\n}\n```
['Recursion', 'Queue', 'Java']