Given an expressionsincludes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression).Please expand expression to be a string.

Example

s =abc3[a]returnabcaaa
s =3[abc]returnabcabcabc
s =4[ac]dy, returnacacacacdy
s =3[2[ad]3[pf]]xyz, returnadadpfpfpfadadpfpfpfadadpfpfpfxyz

Solution: 1个stack存数字,1个stack存字母,遇到]时弹出stack。注意数字>9时

    public String expressionExpand(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        StringBuilder ans = new StringBuilder();
        StringBuilder temp1 = new StringBuilder();
        Stack<Character> stack2 = new Stack<Character>();
        Stack<Integer> stack = new Stack<Integer>();

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if((c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') && stack.empty()){
                ans.append(c);
                continue;
            }
            if(c >= '0' && c <= '9'){
                int val = 0;
                while(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                    val = val * 10 + s.charAt(i) - '0';
                    i++;
                }
                stack.push(val);
                i--;
                continue;
            }
            if(c == ']'){
                int count = stack.pop();
                while(stack2.peek() != '['){
                    temp1.append(stack2.pop());
                }
                stack2.pop();
                if(stack.empty()){
                    for(int j = 0; j < count; j++){
                        for(int k = temp1.length() - 1; k >= 0; k--){
                            ans.append(temp1.charAt(k));
                        }
                    }
                } else{
                    for(int j = 0; j < count; j++){
                        for(int k = temp1.length() - 1; k >= 0; k--){
                            stack2.push(temp1.charAt(k));
                        }
                    }
                }
                temp1.delete(0, temp1.length());
                continue;

            }
            stack2.push(c);
        }
        return ans.toString();
    }

results matching ""

    No results matching ""