学历提升报名_微信开发者模式_百家号优化_百度指数下载

385. Mini Parser

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.

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

Example 1:

Input: s = “324”
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:

Input: s = “[123,[456,[789]]]”
Output: [123,[456,[789]]]
Explanation: 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

Constraints:

• $1<=s.length<=5\ast 10^4$
• s consists of digits, square brackets “[]”, negative sign ‘-’, and commas ‘,’.
• s is the serialization of valid NestedInteger.
• All the values in the input are in the range $[-10^6,10^6]$.

From: LeetCode
Link: 385. Mini Parser

---

Solution:

Ideas:

• Handling integers: If s doesn’t start with a [, it’s a single integer, so we parse it using atoi and return a NestedInteger containing that integer.
• Handling lists: We traverse through the string character by character.
  • When encountering [, we initialize a new NestedInteger and push the current one onto a stack if necessary.
  • When encountering ], we pop from the stack and add the current NestedInteger to the parent.
  • When encountering digits (or - for negative numbers), we parse the number and add it to the current list.
• Memory management: We use a stack to keep track of nested structures, and when we close a nested list (]), we pop the stack and add the nested structure to its parent.

Code:

/*** ********************************************************************** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* *********************************************************************** // Initializes an empty nested list and return a reference to the nested integer.* struct NestedInteger *NestedIntegerInit();** // Return true if this NestedInteger holds a single integer, rather than a nested list.* bool NestedIntegerIsInteger(struct NestedInteger *);** // Return the single integer that this NestedInteger holds, if it holds a single integer* // The result is undefined if this NestedInteger holds a nested list* int NestedIntegerGetInteger(struct NestedInteger *);** // Set this NestedInteger to hold a single integer.* void NestedIntegerSetInteger(struct NestedInteger *ni, int value);** // Set this NestedInteger to hold a nested list and adds a nested integer elem to it.* void NestedIntegerAdd(struct NestedInteger *ni, struct NestedInteger *elem);** // Return the nested list that this NestedInteger holds, if it holds a nested list* // The result is undefined if this NestedInteger holds a single integer* struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);** // Return the nested list's size that this NestedInteger holds, if it holds a nested list* // The result is undefined if this NestedInteger holds a single integer* int NestedIntegerGetListSize(struct NestedInteger *);* };*/struct NestedInteger* deserialize(char* s) {// Handle a special case where the input is just a single integerif (s[0] != '[') {// Single integer casestruct NestedInteger* ni = NestedIntegerInit();NestedIntegerSetInteger(ni, atoi(s));return ni;}// Stack to hold NestedInteger objectsstruct NestedInteger** stack = (struct NestedInteger**)malloc(50000 * sizeof(struct NestedInteger*));int top = -1;  // Stack top pointerint i = 0, n = 0, negative = 0;struct NestedInteger* curr = NULL;while (s[i]) {char ch = s[i];if (ch == '[') {// Start a new NestedInteger liststruct NestedInteger* ni = NestedIntegerInit();if (curr != NULL) {stack[++top] = curr;}curr = ni;} else if (ch == ']') {// End of current NestedInteger list, pop from stack and add to parent if existsif (top != -1) {struct NestedInteger* parent = stack[top--];NestedIntegerAdd(parent, curr);curr = parent;}} else if (ch == ',') {// Skip commas} else {// Handle number parsingint num = 0;negative = 0;if (s[i] == '-') {negative = 1;i++;}while (isdigit(s[i])) {num = num * 10 + (s[i] - '0');i++;}if (negative) num = -num;// Set this as a NestedInteger containing a single integerstruct NestedInteger* ni = NestedIntegerInit();NestedIntegerSetInteger(ni, num);// Add it to the current listNestedIntegerAdd(curr, ni);// Move the index back by one as the outer loop will increment iti--;}i++;}free(stack);return curr;
}