package week02;

import java.util.Map;

import java.util.Stack;

import java.util.TreeMap;

/**

* @创建人 luoxiang

* @创建时间 2019/6/12 16:04

* @描述 LeetCode : 726. 原子的数量 https://leetcode-cn.com/problems/number-of-atoms/

*/

public class NumberOfAtoms726 {

public static void main(String[] args) {

String str = "Mg(OH)2";

String str2 = "K4(ON(SO3)2)2";

new NumberOfAtoms726().countOfAtoms(str);

new NumberOfAtoms726().countOfAtoms(str2);

}

/**

* 思考方式简单，实现比较麻烦

* Method 1 : 使用 堆栈 + map 解决

* 拆解为三种情况：

* 1、 ( 左括号，压栈

* 2、 ) 右括号，出栈

* 3、 字符串

* 判断是否为 小写

* 判断是否为 数字

* 时间复杂度 : O(N) ;

* 空间复杂度 : O(N) ;

*/

public String countOfAtoms(String formula) {

int n = formula.length();

Stack<Map<String, Integer>> stack = new Stack<>();

stack.push(new TreeMap<>());

for (int i = 0; i < n; ) {

if (formula.charAt(i) == '(') {

stack.push(new TreeMap<>());

i++;

} else if (formula.charAt(i) == ')') {

Map<String, Integer> top = stack.pop();

int start = ++i;

while (i < n && Character.isDigit(formula.charAt(i))) i++;

int multi = (i == start ? 1 : Integer.parseInt(formula.substring(start, i)));

for (String s : top.keySet()) {

Integer sum = top.get(s);

stack.peek().put(s, stack.peek().getOrDefault(s, 0) + sum * multi);

}

} else {

int start = i++;

while (i < n && Character.isLowerCase(formula.charAt(i))) i++;

String key = formula.substring(start, i);

start = i;

while (i < n && Character.isDigit(formula.charAt(i))) i++;

int multi = (i == start ? 1 : Integer.parseInt(formula.substring(start, i)));

// 当前 括号 内可能有重复的元素

stack.peek().put(key, stack.peek().getOrDefault(key, 0) + multi);

}

}

StringBuilder sb = new StringBuilder();

for (String s : stack.peek().keySet()) {

Integer num = stack.peek().get(s);

sb.append(s);

if (num > 1) sb.append(num);

}

return sb.toString();

}

}