🌕🌕 385. 迷你语法分析器

难度: 🌕🌕

问题描述

---

解法 1 - 递归

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        // 思路：
        // 多位数字的解析 + 递归
        int len = s.length();
        return mySol(s, 0, len - 1);
    }

    private NestedInteger mySol(String s, int left, int right) {
        NestedInteger res = new NestedInteger();
        char c = s.charAt(left);
        if(c != '[') {
            // 123,456,[788,799,833],[[]],10,[] 不满足要求，说明如果初始不是左中括号的话，后面只能跟一个整数
            int num = getNumber(s, left, right);
            res.setInteger(num);
            // System.out.println(s.charAt(left) + "  " + num);
            return res;
        }
        // c == '[' 
        // 说明是个嵌套对象
        // 遍历，进行拆分，是整数就添加整数，遇到嵌套递归
        left ++;
        right --; // 去掉最外层中括号
        int i = left;
        int j = left;
        while(i <= right) {
            // 如果左边界为左括号，只有 左括号与右括号正好抵消时递归
            // 如果左边界不为左括号，说明是数字，遇到 逗号递归
            if(s.charAt(i) == '[') {
                int count = 1; // 从 i 开始往右找左括号的数量
                j = i + 1;
                while(j <= right && count != 0) {
                    if(s.charAt(j) == '[') {
                        count ++;
                    }
                    if(s.charAt(j) == ']') {
                        count --;
                    }
                    j ++;
                }
                res.add(mySol(s, i, j - 1));
            } else {
                j = i;
                while(j <= right && s.charAt(j) != ',') {
                    j ++;
                }
                res.add(mySol(s, i, j - 1));
            }
            i = j + 1;
        }
        return res;
    }

    private int getNumber(String s, int left, int right) {
        int res = 0;
        boolean flag = true;
        for(int i = left; i <= right; i ++) {
            char c = s.charAt(i);
            if(c == '-') {
                flag = false;
            } else {
                int cur = c - '0';
                res = res * 10 + cur;
            }
        }
        return flag ? res : -res;
    }
}

---

输出 1

---

解法 2 - 栈

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    NestedInteger monitor = new NestedInteger(-1); // 标志元素，表示左括号压入的元素，当遇到右括号时遇到它终止
    public NestedInteger deserialize(String s) {
        // 思路：
        // 栈
        // 遍历字符串
        // 遇到 '[' 压入一个新的 NestedInteger()
        // 遇到 ']' 依次取出栈中元素，直到遇到一个 NestedInteger() 而非 NestedInteger(int value)
        // 遇到 ',' 跳过
        // 遇到 数字，找到数字边界，压入 NestedInteger(int value)
        int len = s.length();
        LinkedList<NestedInteger> stack = new LinkedList<>();
        int index = 0;
        while(index < len) {
            char c = s.charAt(index);
            if(c == ',') {
                index ++;
                continue;
            } else if(c == '-' || (c >= '0' && c <= '9')) {
                // 数字
                int j = index;
                while(j < len && (s.charAt(j) == '-' || (s.charAt(j) >= '0' && s.charAt(j) <= '9'))) {
                    j ++;
                }
                int num = getNumber(s, index, j - 1);
                stack.push(new NestedInteger(num));
                index = j;
            } else if(c == '[') {
                // 左中括号
                stack.push(new NestedInteger());
                stack.push(monitor);
                index ++;
            } else if(c == ']') {
                // 右中括号
                // 依次弹栈，直到遇到第一个与之匹配的左括号，弹出的元素也需要保存，这些元素是单整数
                ArrayList<NestedInteger> list = new ArrayList<>();
                while(!stack.isEmpty() && stack.peek() != monitor) {
                    list.add(stack.pop());
                }
                if(!stack.isEmpty()) {
                    stack.pop(); // 弹出标志元素
                    NestedInteger cur = stack.pop(); // 压入的空元素
                    // 将 list 的元素逆序压入 cur
                    int size = list.size();
                    for(int k = size - 1; k >= 0; k --) {
                        cur.add(list.get(k));
                    }
                    // 将 cur 重新压入栈中
                    stack.push(cur);
                }
                index ++;
            }
            // System.out.println(s.charAt(index));
        }
        return stack.peek();
    }

    private int getNumber(String s, int left, int right) {
        int res = 0;
        boolean flag = true;
        for(int i = left; i <= right; i ++) {
            char c = s.charAt(i);
            if(c == '-') {
                flag = false;
            } else {
                int cur = c - '0';
                res = res * 10 + cur;
            }
        }
        return flag ? res : -res;
    }
}

---

输出 2