迷你语法分析器

难度:

标签:

题目描述

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

列表中的每个元素只可能是整数或整数嵌套列表

示例 1：

输入：s = "324",
输出：324
解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

输入：s = "[123,[456,[789]]]",
输出：[123,[456,[789]]]
解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

提示：

1 <= s.length <= 5 * 10⁴
s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
用例保证 s 是可解析的 NestedInteger
输入中的所有值的范围是 [-10⁶, 10⁶]

代码结果

运行时间: 28 ms, 内存: 18.4 MB

/*
题目思路：
1. 与传统Java解法类似，但我们将使用Java Stream API来进行数据处理。
2. 将字符串解析为流，并使用Stream的操作来处理字符和数字。
3. 使用分区操作处理数字的提取与嵌套列表的构建。
*/
 
import java.util.*;
import java.util.stream.Collectors;
 
class NestedInteger {
    private Integer value;
    private List<NestedInteger> list;
 
    public NestedInteger() {
        this.list = new ArrayList<>();
    }
    public NestedInteger(int value) {
        this.value = value;
    }
    public void setInteger(int value) {
        this.value = value;
    }
    public void add(NestedInteger ni) {
        if (this.list == null) this.list = new ArrayList<>();
        this.list.add(ni);
    }
    public boolean isInteger() {
        return value != null;
    }
    public Integer getInteger() {
        return value;
    }
    public List<NestedInteger> getList() {
        return list;
    }
}
 
public class Solution {
    public NestedInteger deserialize(String s) {
        if (s.isEmpty()) return null;
        if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }
 
        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger curr = null;
        int l = 0;
 
        List<Character> chars = s.chars().mapToObj(e -> (char) e).collect(Collectors.toList());
 
        for (int r = 0; r < chars.size(); r++) {
            char ch = chars.get(r);
            if (ch == '[') {
                if (curr != null) {
                    stack.push(curr);
                }
                curr = new NestedInteger();
                l = r + 1;
            } else if (ch == ']') {
                String num = s.substring(l, r);
                if (!num.isEmpty()) {
                    curr.add(new NestedInteger(Integer.parseInt(num)));
                }
                if (!stack.isEmpty()) {
                    NestedInteger pop = stack.pop();
                    pop.add(curr);
                    curr = pop;
                }
                l = r + 1;
            } else if (ch == ',') {
                if (chars.get(r - 1) != ']') {
                    String num = s.substring(l, r);
                    curr.add(new NestedInteger(Integer.parseInt(num)));
                }
                l = r + 1;
            }
        }
        return curr;
    }
}

解释

方法:

这个题解使用了栈来解析嵌套列表。它逐个字符遍历输入字符串 s，根据不同的字符进行相应的操作： 1. 如果当前字符是数字，就更新当前的数字 num。 2. 如果当前字符是 '-'，就将 flag 设为 -1，表示当前数字是负数。 3. 如果当前字符是 '['，就在栈中添加一个新的 NestedInteger 对象。 4. 如果当前字符是 ',' 或 ']'，且前一个字符是数字，就将当前数字 num 转换成 NestedInteger 对象，并将其添加到栈顶的 NestedInteger 中，然后将 num 和 flag 重置。 5. 如果当前字符是 ']'，且栈中有多个元素，就将栈顶的 NestedInteger 对象弹出，并将其添加到新的栈顶 NestedInteger 中。 6. 最后，栈中唯一剩下的 NestedInteger 对象就是解析后的结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在解析算法中，如果输入字符串是空或者只包含空格，该算法如何处理？

▷

题解中的算法没有直接处理输入字符串为空或只含空格的情况。在实际应用中，这样的输入应当被认为是无效的。如果需要容错处理，可以在函数开始时添加条件检查，如果输入字符串为空或全为空格，则返回一个空的NestedInteger对象或抛出一个异常。

🦆

题解中提到使用栈来处理嵌套结构，为什么选择栈而不是其他数据结构如队列或链表？

▷

栈是一种后进先出的数据结构，非常适合处理具有嵌套结构的数据，例如本题中的嵌套列表。使用栈可以方便地处理和回溯嵌套关系，因为一旦完成内层列表的解析，可以立刻将其加入到上一层的列表中。而使用队列或链表虽然也可实现，但在处理嵌套的回溯上更复杂，效率可能也较低。

🦆

在处理数字时，如何确保解析的正确性，特别是在遇到多位数或负数时？

▷

题解中通过连续读取数字字符并使用累乘和累加的方式（num = num * 10 + int(letter)）构建多位数，这确保了多位数可以被正确解析。同时，通过引入flag变量，当遇到负号时，将flag设置为-1，这样在添加数字到NestedInteger对象时，可以通过乘以flag来处理负数情况，确保数字的正负正确。

🦆

题解中未详细说明如何处理连续的','字符或错误格式的输入，这类情况应如何处理？

▷

题解中确实没有详细说明如何处理格式错误的输入，包括连续的','字符。理想的做法是在解析过程中增加对输入格式的校验。例如，可以检查连续的','是否出现，或者在不应出现数字的地方出现数字等情况，并在发现格式错误时抛出异常或返回错误信息。这样可以避免解析非法格式的输入，增强代码的鲁棒性。

相关问题

扁平化嵌套列表迭代器

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
int next() 返回嵌套列表的下一个整数。
boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

提示：

1 <= nestedList.length <= 500
嵌套列表中的整数值在范围 [-10⁶, 10⁶] 内

三元表达式解析器

删除注释

给一个 C++ 程序，删除程序中的注释。这个程序source是一个数组，其中source[i]表示第 i 行源码。这表示每行源码由 '\n' 分隔。

在 C++ 中有两种注释风格，行内注释和块注释。

字符串// 表示行注释，表示//和其右侧的其余字符应该被忽略。
字符串/* 表示一个块注释，它表示直到下一个（非重叠）出现的*/之间的所有字符都应该被忽略。（阅读顺序为从左到右）非重叠是指，字符串/*/并没有结束块注释，因为注释的结尾与开头相重叠。

第一个有效注释优先于其他注释。

如果字符串//出现在块注释中会被忽略。
同样，如果字符串/*出现在行或块注释中也会被忽略。

如果一行在删除注释之后变为空字符串，那么不要输出该行。即，答案列表中的每个字符串都是非空的。

样例中没有控制字符，单引号或双引号字符。

比如，source = "string s = "/* Not a comment. */";" 不会出现在测试样例里。

此外，没有其他内容（如定义或宏）会干扰注释。

我们保证每一个块注释最终都会被闭合，所以在行或块注释之外的/*总是开始新的注释。

最后，隐式换行符可以通过块注释删除。有关详细信息，请参阅下面的示例。

从源代码中删除注释后，需要以相同的格式返回源代码。

示例 1:

输入: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
输出: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]
解释: 示例代码可以编排成这样:
/*Test program */
int main()
{ 
  // variable declaration 
int a, b, c;
/* This is a test
   multiline  
   comment for 
   testing */
a = b + c;
}
第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
编排后: 
int main()
{ 
  
int a, b, c;
a = b + c;
}

示例 2:

输入: source = ["a/*comment", "line", "more_comment*/b"]
输出: ["ab"]
解释: 原始的 source 字符串是 "a/*comment\nline\nmore_comment*/b", 其中我们用粗体显示了换行符。删除注释后，隐含的换行符被删除，留下字符串 "ab" 用换行符分隔成数组时就是 ["ab"].

提示:

1 <= source.length <= 100
0 <= source[i].length <= 80
source[i] 由可打印的 ASCII 字符组成。
每个块注释都会被闭合。
给定的源码中不会有单引号、双引号或其他控制字符。

打乱数组字典序排数