【Leetcode】Mini Parser

题目链接：https://leetcode.com/problems/mini-parser/
题目：

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits 0-9, [, - ,, ].

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

思路：

用栈维护一个包含关系，类似于用栈维护带 ‘(‘ 的表达式。

思路不难想到，有个坑爹的细节要注意：添加一个数到list type的nestedInteger时 要将该数封装为integer type的NestedInteger，然后用add方法添加该nestedInteger，不能直接用setInteger，否则会把list type的nestedInteger定义为一个integer type，会出错。

还可以用递归来做，思路大致是：没处理完一个token，遇到 [  递归处理 返回该层list结尾下标。好像有点麻烦。。留坑日后待填。

算法：

	public NestedInteger deserialize(String s) {
		Stack<NestedInteger> stack = new Stack<NestedInteger>();
		String tokenNum = "";

		for (char c : s.toCharArray()) {
			switch (c) {
			case '['://[代表一个list
				stack.push(new NestedInteger());
				break;
			case ']'://list结尾
				if (!tokenNum.equals(""))//前面token为数字 
					stack.peek().add(new NestedInteger(Integer.parseInt(tokenNum)));//将数字加入到本层list中
				NestedInteger ni = stack.pop();//本层list结束
				tokenNum = "";
				if (!stack.isEmpty()) {//栈内有更高层次的list
					stack.peek().add(ni);
				} else {//栈为空，遍历到字符串结尾
					return ni;
				}
				break;
			case ',':
				if (!tokenNum.equals("")) //将数字加入到本层list中
					stack.peek().add(new NestedInteger(Integer.parseInt(tokenNum)));
				tokenNum = "";
				break;
			default:
				tokenNum += c;
			}
		}
		if (!tokenNum.equals(""))//特殊case: 如果字符串只包含数字的情况
			return new NestedInteger(Integer.parseInt(tokenNum));
		return null;
	}

【Leetcode】Mini Parser

原文：http://blog.csdn.net/yeqiuzs/article/details/52208388