0722-删除注释

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给一个 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 **\n** line **\n** more_comment*/b", 其中我们用粗体显示了换行符。删除注释后，隐含的换行符被删除，留下字符串 "ab" 用换行符分隔成数组时就是 ["ab"].

提示:

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

​​​​​​

方法一：模拟

思路与算法

我们需要逐行分析源代码。每个字符有两种情况，要么在一个注释内要么不在。因此我们用 in_block 变量来标记状态，该变量为 true 表示在注释内，反之则不在。

假设此刻不在注释块内：

  • 遇到 `/*’，则将状态改为在注释块内，继续遍历后面第三个字符。
  • 遇到 `//‘，则直接忽略该行后面的部分。
  • 遇到其他字符，将该字符记录到 new_line 中。

假设此刻在注释块内，遇到 `*/‘，则将状态改为不在注释块内，继续遍历后面第三个字符。

我们用 new_line 记录新的一行，当遍历到每行的末尾时，如果不在注释块内并且 new_line 不为空，就把它放入答案中。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<string> removeComments(vector<string>& source) {
        vector<string> res;
        string new_line = "";
        bool in_block = false;
        for (auto& line : source) {
            for (int i = 0; i < line.size(); i++) {
                if (in_block) {
                    if (i + 1 < line.size() && line[i] == '*' && line[i + 1] == '/') {
                        in_block = false;
                        i++;
                    }
                } else {
                    if (i + 1 < line.size() && line[i] == '/' && line[i + 1] == '*') {
                        in_block = true;
                        i++;
                    } else if (i + 1 < line.size() && line[i] == '/' && line[i + 1] == '/') {
                        break;
                    } else {
                        new_line += line[i];
                    }
                }
            }
            if (!in_block && new_line != "") {
                res.push_back(new_line);
                new_line = "";
            }
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<String> removeComments(String[] source) {
        List<String> res = new ArrayList<String>();
        StringBuilder newLine = new StringBuilder();
        boolean inBlock = false;
        for (String line : source) {
            for (int i = 0; i < line.length(); i++) {
                if (inBlock) {
                    if (i + 1 < line.length() && line.charAt(i) == '*' && line.charAt(i + 1) == '/') {
                        inBlock = false;
                        i++;
                    }
                } else {
                    if (i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '*') {
                        inBlock = true;
                        i++;
                    } else if (i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '/') {
                        break;
                    } else {
                        newLine.append(line.charAt(i));
                    }
                }
            }
            if (!inBlock && newLine.length() > 0) {
                res.add(newLine.toString());
                newLine.setLength(0);
            }
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public IList<string> RemoveComments(string[] source) {
        IList<string> res = new List<string>();
        StringBuilder newLine = new StringBuilder();
        bool inBlock = false;
        foreach (string line in source) {
            for (int i = 0; i < line.Length; i++) {
                if (inBlock) {
                    if (i + 1 < line.Length && line[i] == '*' && line[i + 1] == '/') {
                        inBlock = false;
                        i++;
                    }
                } else {
                    if (i + 1 < line.Length && line[i] == '/' && line[i + 1] == '*') {
                        inBlock = true;
                        i++;
                    } else if (i + 1 < line.Length && line[i] == '/' && line[i + 1] == '/') {
                        break;
                    } else {
                        newLine.Append(line[i]);
                    }
                }
            }
            if (!inBlock && newLine.Length > 0) {
                res.Add(newLine.ToString());
                newLine.Length = 0;
            }
        }
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define MAX_LINE_LEN 80

char ** removeComments(char ** source, int sourceSize, int* returnSize) {
    char **res = (char **)calloc(sourceSize, sizeof(char *));
    char new_line[sourceSize * MAX_LINE_LEN + 1];
    int pos = 0, new_line_pos = 0;
    bool in_block = false;
    for (int j = 0; j < sourceSize; j++) {
        char *line = source[j];
        int line_size = strlen(line);
        for (int i = 0; i < line_size; i++) {
            if (in_block) {
                if (i + 1 < line_size && line[i] == '*' && line[i + 1] == '/') {
                    in_block = false;
                    i++;
                }
            } else {
                if (i + 1 < line_size && line[i] == '/' && line[i + 1] == '*') {
                    in_block = true;
                    i++;
                } else if (i + 1 < line_size && line[i] == '/' && line[i + 1] == '/') {
                    break;
                } else {
                    new_line[new_line_pos++] = line[i];
                }
            }
        }
        if (!in_block && new_line_pos > 0) {
            new_line[new_line_pos] = '\0';
            res[pos] = (char *)calloc(new_line_pos + 1, sizeof(char));
            strcpy(res[pos], new_line);
            pos++;
            new_line_pos = 0;
        }
        *returnSize = pos;
    }
    return res;
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def removeComments(self, source: List[str]) -> List[str]:
        res = []
        new_line = []
        in_block = False
        for line in source:
            i = 0
            while i < len(line):
                if in_block:
                    if i + 1 < len(line) and line[i] == '*' and line[i + 1] == '/':
                        in_block = False
                        i += 1
                else:
                    if i + 1 < len(line) and line[i] == '/' and line[i + 1] == '*':
                        in_block = True
                        i += 1
                    elif i + 1 < len(line) and line[i] == '/' and line[i + 1] == '/':
                        break
                    else:
                        new_line.append(line[i])
                i += 1
                
            if  not in_block and len(new_line) > 0:
                res.append(''.join(new_line))
                new_line = []
        return res
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var removeComments = function(source) {
    let res = [];
    let newLine = '';
    let inBlock = false;
    for (let line of source) {
        for (let i = 0; i < line.length; i++) {
            if (inBlock) {
                if (i + 1 < line.length && line[i] === '*' && line[i + 1] === '/') {
                    inBlock = false;
                    i++;
                }
            } else {
                if (i + 1 < line.length && line[i] === '/' && line[i + 1] === '*') {
                    inBlock = true;
                    i++;
                } else if (i + 1 < line.length && line[i] === '/' && line[i + 1] === '/') {
                    break;
                } else {
                    newLine += line[i];
                }
            }
        }
        if (!inBlock && newLine.length > 0) {
            res.push(newLine);
            newLine = '';
        }
    }
    return res;
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func removeComments(source []string) []string {
    res := []string{}
    new_line := []byte{}
    in_block := false
    for _, line := range source {
        for i := 0; i < len(line); i++ {
            if in_block {
                if i + 1 < len(line) && line[i] == '*' && line[i + 1] == '/' {
                    in_block = false
                    i++
                }
            } else {
                if i + 1 < len(line) && line[i] == '/' && line[i + 1] == '*' {
                    in_block = true
                    i++
                } else if i + 1 < len(line) && line[i] == '/' && line[i + 1] == '/' {
                    break
                } else {
                    new_line = append(new_line, line[i])
                }
            }
        }
        if  !in_block && len(new_line) > 0 {
            res = append(res, string(new_line))
            new_line = []byte{}
        }
    }
    return res
}

复杂度分析

  • 时间复杂度：O(nm)，其中 n 是 source 的长度，m 是 source}[i] 的最大长度。

  • 空间复杂度：O(nm)。在极端情况下，每一行的隐式换行符都被块注释删除，new_line 的长度将会达到 O(nm)。

 Comments
On this page
0722-删除注释