Expression Expand

update Aug 24,2017 17:43

LintCode

Given an expression s includes 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] return abcaaa
    s = 3[abc] return abcabcabc
    s = 4[ac]dy, return acacacacdy
    s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz

Challenge Can you do it without recursion?

Basic Idea:

思路1：recursive dfs 就是利用recursion，把每一层括号内的内容都直接丢给下级函数去做。但是要注意实现细节。

java:

    // recursive solution
    public class Solution {
        /**
         * @param s  an expression includes numbers, letters and brackets
         * @return a string
         */
        public String expressionExpand(String s) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); ++i) {
                // 普通字母
                char c = s.charAt(i);
                if (Character.isLetter(c)) {
                    sb.append(c);
                }
                // 数字
                else if (Character.isDigit(c)) {
                    // 记录数字
                    String fact = c + "";
                    while (Character.isDigit(s.charAt(i + 1))) {
                        fact += s.charAt(i + 1);
                        i++;
                    }
                    int factor = Integer.parseInt(fact);
                    // 读取后续括号内的串, 方法是计数左右括号数量的差，左记为-1，右记为+1，
                    // 当right=0时，表示这次数字后面的串读完
                    i += 2; // 跳过 '['
                    String inner = "";
                    int right = -1;
                    while (true) {
                        if (s.charAt(i) == '[') right -=1;
                        else if (s.charAt(i) == ']') right += 1;
                        inner += s.charAt(i);
                        if (right == 0) break;
                        i++;
                    }
                    // 把inner解析之后的内容重复factor次
                    String inner_expanded = expressionExpand(inner);
                    for (int j = 0; j < factor; ++j) {
                        sb.append(inner_expanded);
                    }
                }
            }   
            return sb.toString();
        }
    }

python

    # recursive solution
    class Solution:
        # @param {string} s  an expression includes numbers, letters and brackets
        # @return {string} a string
        def expressionExpand(self, s):
            res = []
            i = 0
            while i < len(s):
                # 普通字符
                if s[i].isalpha():
                    res.append(s[i])
                    i += 1
                # 数字
                elif s[i].isdigit():
                    dig = s[i]
                    i += 1
                    while s[i].isdigit():
                        dig += s[i]
                        i += 1
                    factor = int(dig) # 系数得到了

                    # 接下来获取之后括号内的内容
                    i += 1  # 跳过'['
                    right = -1
                    inner = []
                    while right != 0:
                        if s[i] == '[':
                            right -= 1
                        elif s[i] == ']':
                            right += 1
                        if right == 0:
                            break
                        inner.append(s[i])
                        i += 1

                    #  处理inner
                    inner_expanded = self.expressionExpand(inner)
                    res += list(inner_expanded * factor)
                else:
                    i += 1
            return ''.join(res)

思路2：using stack 使用stack可以模拟recursion的过程，但是要特别注意实现细节，跟踪好每一步之后指针 i 的位置。

Java:

    // non-recusive solution
    public class Solution {
        /**
         * @param s  an expression includes numbers, letters and brackets
         * @return a string
         */
        public String expressionExpand(String s) {
            Deque<Object> stack = new LinkedList<>();
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < s.length(); ++i) {
                Character c = s.charAt(i);
                // 如果是数字，则找到完整数字，并压栈
                if (Character.isDigit(c)) {
                    Integer factor = 0;
                    String dig = c + "";
                    i++;
                    while (Character.isDigit(s.charAt(i))) {
                        dig += s.charAt(i++);
                    } // 此时i指向数字之后的'['
                    factor = Integer.valueOf(dig);
                    stack.addLast(factor);
                }
                else if (Character.isLetter(c)) {
                    stack.addLast(c);
                }
                if (c == ']' || i == s.length() - 1) {
                    // 在stack中拿出最近的直到数字的字符串，处理之后放回stack中
                    // 便于后面的处理
                    int factor = 1;
                    StringBuilder inner_sb = new StringBuilder();
                    while (! stack.isEmpty()) {
                        if (stack.peekLast().getClass() == Integer.class) {
                            factor = (Integer)(stack.removeLast());
                            break;
                        }
                        inner_sb.append((Character)(stack.removeLast()));
                    }
                    String inner = inner_sb.reverse().toString();
                    for (int j = 0; j < factor; ++j) {
                        for (char ch : inner.toCharArray()) {
                            stack.addLast(ch);
                        }
                    }
                }
            }
            // 把stack中的内容放入stringbuilder，因为这里使用的stack是Deque，可以从
            // 两端pop，很方便
            while (! stack.isEmpty()) {
                sb.append(stack.removeFirst());
            }
            return sb.toString();
        }
    }

update 2018-07-19 22:20:02

Update: recursion 模块化解法 java

注意模块化的思路，很多逻辑看似复杂，可以交给一个helper function 稍后实现，这样可以专注核心逻辑。

public class Solution {
    /**
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
    public String expressionExpand(String s) {
        char[] arr = s.toCharArray();
        return expand(arr, 0, arr.length - 1);
    }

    private int getNumber(char[] arr, int start) {
        int ret = 0;
        int i = start;
        while (arr[i] >= '0' && arr[i] <= '9') {
            ret = ret * 10 + arr[i++] - '0';
        }
        return ret;
    }

    // 从当前‘【’出发，找到与之匹配的‘】’
    private int getNextPos(char[] arr, int start) {
        int left = 0, right = 0;
        for (int i = start; i < arr.length; ++i) {
            if (arr[i] == '[') left++;
            else if (arr[i] == ']') right++;
            if (left == right) return i;
        }
        return -1;
    }

    private String expand(char[] arr, int start, int end) {
        StringBuilder sb = new StringBuilder();
        int i = start;
        while (i <= end) {
            if (arr[i] >= 'a' && arr[i] <= 'z' ||
                arr[i] >= 'A' && arr[i] <= 'Z') {
                sb.append(arr[i++]);
            } else if (arr[i] >= '0' && arr[i] <= '9') {
                int num = getNumber(arr, i);
                // 跳过数字
                while (arr[i] != '[') i++;
                // 得到对应‘]’ 的index
                int nextPos = getNextPos(arr, i);
                String str = expand(arr, i + 1, nextPos - 1);
                for (int k = 0; k < num; ++k) sb.append(str);
                i = nextPos + 1;
            } else {
                return "error,";
            }
        }
        return sb.toString();
    }
}