Java | 5ms | Parsing backwards | O(nlogn)
Feel like I am getting better at parsing questions after grinding through over 5 hard parsing Qs on leetcode in the past 1-2 weeks.\n\nFor this problem, it is b
Feel like I am getting better at parsing questions after grinding through over 5 hard parsing Qs on leetcode in the past 1-2 weeks.\n\nFor this problem, it is better to parse backwards because the number is placed after each formula, not before. \nThat way we can avoid having to traverse through the formula just to get that number.\n\nAs a rule of thumb, whenever we see `\')\'`, we will place a new map on top of the stack and add all the result in between the next `\'(\'` to that.\nThen, when we encounter `\'(\'`, we pop the map off top of the stack and merge it with the top map on the stack.\n_____________________\n#### Edge Case\nSurpringly, only numbers!\nWe are reading it backwards, so remember to reverse the number and to handle cases like 50 where it may be read as 05 = 5.\n```Java\nclass Solution {\n    public String countOfAtoms(String A) {\n        Deque<Map<String, Integer>> stack = new ArrayDeque<>();\n        Deque<Integer> numStack = new ArrayDeque<>();\n        StringBuilder sb = new StringBuilder();\n        StringBuilder nsb= new StringBuilder();\n        stack.push(new HashMap<>());\n        long num = 0;\n        for (int i = A.length()-1;i>=0;--i){\n            if (A.charAt(i)==\')\'){\n                stack.push(new HashMap<>());\n                numStack.push(getnum(nsb));\n                nsb.setLength(0);\n            }else if (A.charAt(i)==\'(\'){\n                Map<String, Integer> top = stack.pop();\n                int mul = numStack.pop();\n                for (String key : top.keySet()){\n                    stack.peek().merge(key, top.get(key)*mul, Integer::sum);\n                }\n            }else if (Character.isDigit(A.charAt(i))){\n                nsb.append(A.charAt(i));\n            }else if (Character.isLowerCase(A.charAt(i))){\n                sb.append(A.charAt(i));\n            }else{ // upper case\n                sb.append(A.charAt(i));\n                stack.peek().merge(sb.reverse().toString(),getnum(nsb),Integer::sum);\n                nsb.setLength(0);\n                sb.setLength(0);\n            }\n        }\n\n        Map<String, Integer> res = stack.pop();\n        List<String> atoms = new ArrayList<>(res.keySet());\n        Collections.sort(atoms);\n        for (String key : atoms){\n            sb.append(key);\n            if (res.get(key)>1){\n                sb.append(res.get(key));\n            }\n        }\n        return sb.toString();\n    }\n\n    private int getnum(StringBuilder sb){\n        return sb.isEmpty()?1:Integer.parseInt(sb.reverse().toString());\n    }\n}\n```
['Stack', 'Java']