LeetCode Mini Parser

LeetCode 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.

给定一个嵌套的字符串,要求把它解析成一个NestedInteger。

解法1,使用栈。遇到左括号时,增加一个空的NestedInteger实例,压栈。遇到逗号时,把前面的数add到栈顶的NestedInteger中。遇到右括号时,把栈顶的NestedInteger弹栈,并add到新的栈顶(相当于前一个)NestedInteger中。最后栈顶只有一个元素,返回该元素即可。

代码如下:

class Solution {
public:
	NestedInteger deserialize(string s) {
		auto isnumber = [](char c) {return c == '-' || isdigit(c); };
		stack<NestedInteger> stk;
		stk.push(NestedInteger());
		for (auto it = s.begin(); it != s.end();) {
			if (isnumber(*it)) {
				auto it2 = find_if_not(it, s.end(), isnumber);
				int v = stoi(string(it, it2));
				stk.top().add(NestedInteger(v));
				it = it2;
			}
			else {
				if (*it == '[') {
					stk.push(NestedInteger());
				}
				else if (*it == ']') {
					NestedInteger tmp = stk.top();
					stk.pop();
					stk.top().add(tmp);
				}
				++it;
			}
		}
		return stk.top().getList().front();
	}
};

本代码提交AC,用时19MS。

解法2,递归法。如果当前的字符串是一个裸的整数的话,类似于样例1,则直接返回以该数为参数的NestedInteger;否则剥掉左括号[,递归反序列化,把递归的结果add到当前的NestedInteger中。

代码如下:

class Solution {
private:
	NestedInteger deserialize(istringstream &in) {
		int number;
		if (in >> number)
			return NestedInteger(number);
		in.clear();
		in.get();
		NestedInteger list;
		while (in.peek() != ']') {
			list.add(deserialize(in));
			if (in.peek() == ',')in.get();
		}
		in.get();
		return list;
	}
public:
	NestedInteger deserialize(string s) {
		istringstream in(s);
		return deserialize(in);
	}
};

本代码提交AC,用时19MS。

参考1,栈:https://discuss.leetcode.com/topic/54904/c-non-recursive-one-pass-solution-using-stack-a-possible-implementation-of-nestedinteger

参考2,递归:https://discuss.leetcode.com/topic/54258/python-c-solutions/10

Leave a Reply

Your email address will not be published. Required fields are marked *