Parser

Mini Parser

解法一：Stack

1. 不含'['，那就return nested integer。
2. 建一个stack，在stack里放一个空的nested integer。
   1. 如果遇到数字，就把数字加到stack.peek()里
   2. 如果遇到逗号，就index + 1
   3. 如果遇到'['，就压一个新的空的nested integer list到stack上
   4. 如果遇到']'，就pop一个nested integer list出来，并且把这个pop出来的加到stack.peek()里

/**
 * // 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 null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) {
            return new NestedInteger();
        } else if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }

        NestedInteger n = new NestedInteger();
        Stack<NestedInteger> stack = new Stack<NestedInteger>();
        stack.push(n);
        int i = 1;
        while (i < s.length() - 1) {
            char c = s.charAt(i);
            if (c == '+' || c == '-' || Character.isDigit(c)) {
                int j = i;
                int sign = 1;
                if (c == '+' || c == '-') {
                    if (c == '-') {
                        sign = -1;
                    }
                    j++;
                }

                int num = 0;
                while (j < s.length() - 1 && Character.isDigit(s.charAt(j))) {
                    num = num * 10 + s.charAt(j) - '0';
                    j++;
                }

                stack.peek().add(new NestedInteger(sign * num));
                i = j;
            } else if (c == ',') {
                i++;
            } else if (c == '[') {
                stack.push(new NestedInteger());
                i++;
            } else {
                NestedInteger nn = stack.pop();
                stack.peek().add(nn);
                i++;
            }
        }
        return stack.pop();
    }
}

解法二：同样维护一个count变量，每当count == 0时，同时当前的character是",“或者index == lastIndex时，dfs从startIndex到当前character的index - 1。如果c == '['，count++; 如果c == ']', count--。

/**
 * // 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 null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) {
            return new NestedInteger();
        } else if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }

        NestedInteger n = new NestedInteger();
        if (s.length() > 2) {
            int start = 1, count = 0;
            for (int i = 1; i < s.length(); i++) {
                char c = s.charAt(i);
                if (count == 0 && (c == ',' || i == s.length() - 1)) {
                    n.add(deserialize(s.substring(start, i)));
                    start = i + 1;
                }
                if (c == '[') {
                    count++;
                } else if (c == ']') {
                    count--;
                }
            }
        }
        return n;
    }
}

Ternary Expression Parser

跟上一题一样，一样是维护一个count变量，在遇到”?“时count++，遇到”:“时count--。当遇到":"后如果count == 0，我们可以把当前的string划分成result, first, 和second这三个substring。根据result的结果来决定返回first还是second。

public class Solution {
    public String parseTernary(String expression) {
        if (expression == null || expression.length() <= 1) {
            return expression;
        }

        int count = 0, start = -1;
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '?') {
                if (start == -1) {
                    start = i + 1;
                }
                count++;
            } else if (c == ':') {
                count--;
                if (count == 0) {
                    String result = expression.substring(0, start - 1);
                    String first = parseTernary(expression.substring(start, i));
                    String second = parseTernary(expression.substring(i + 1));
                    return result.equals("T") ? first : second;
                }
            }
        }
        return "";
    }
}