字符串是否总是包含空的子字符串?

6
这个问题源于这个答案的讨论。
简而言之:答案作者(0x499602D2)声称(现在我知道是正确的),当不跳过空格,但下一个字符是空格时,除了字符以外的所有提取都会失败。
我对此提出了质疑,因为我认为提取一个字符串不应该失败,因为流包含由开始处的空格字符分隔的空字符串。
这引发了关于字符串中是否存在空字符串的一般讨论,例如在字符串“ab”的a和b之间是否有空字符串(我说有,0x499602D2说没有)。 0x499602D2建议我把这个问题放在一个问题中,所以我在这里做了。
我从那个线程中复制了我的立场的主要论点(包括聊天部分)。
让我们首先看一下空字符串的常数。在 C 和 C++ 中,内容由引号限定开头和结尾。那么空字符串是什么样子的呢?你知道它是:""。你看,在初始引号(定界符)之后直接跟着最终引号(定界符)。空字符串位于两个引号之间,这两个引号直接紧挨着,因为空字符串没有字符。还要看看 C 表示法。那就是字符序列,后面跟着定界符'\0'。那么空字符串的表示是什么?嗯,是空字符串的字符后跟着定界符。也就是说,第一个字符是定界符(即与流情况完全相同)。现在考虑字符串的串联,例如第一个字符串是"a",第二个字符串是空的,第三个字符串是"b"。那么串联是什么呢?嗯,是"ab"。所以在"ab"中的ab之间明显有一个空字符串(我们明确地放在那里!)。当然,在a之前和b之后也是如此。也就是说,在字符串的任意两个字符之间都有一个空字符串(或者两个空字符串,或者一百万个)。
空字符串没有字符,在连续字符之间也没有字符。因此,在两个字符之间有一个空字符串。也可以看看我之前给出的其他论点。此外,考虑匹配空字符串的正则表达式: 它们也在任何地方匹配。
例如,/ab*c/匹配"ac",因为b*匹配a和c之间的空字符串。
在定界符(空格)之前有一个空字符串(即没有字符),就像空字符串的 C 表示法中,在\0定界符之前没有字符一样。还要注意 readline 与\n定界符一起使用时也是相同的:如果\n紧随其后,则不会失败,但会返回一个空字符串。
我感觉无法确定讨论中 0x499602D2 的主要论点,所以我也不试图避免在选择上无意中不公平。你应该能够在评论中看到它们(可能还可以在聊天室中看到——我不知道是否每个人都可以访问)。如果你想的话,你也可以在这段话之后添加你的主要论点。
这个问题的实际问题是:一个设计良好的字符串提取函数是否应该在定界符之前没有字符的情况下失败(与字符串的operator>>相同),还是成功并返回一个空字符串(如readline所做的那样)?

4
这并不是一个针对实际问题的提问。您是否有特定的算法、标准条款或函数需要解决,以使得这个问题成为一个好的 Stack Overflow 问题? - Yakk - Adam Nevraumont
@Yakk:我已经添加了一个有关与此相关的实际问题的段落。 - celtschk
@celtschk 你好。我认为kol的回答仅仅证明了这个概念,但并没有实际展示如何在实践中证明它。你能给我一个能够在实际应用中证明这一点的程序吗? - David G
你是否也会质疑 1 > 0 在“实际意义上”是真的,并要求编写程序来证明它?无论如何,我在右侧的链接中找到了这个。虽然不完全是同一个问题,但是它是一个特殊情况(即空字符串中的空字符串),并且有几个答案提供了明确的代码示例。 - celtschk
1个回答

10

定理

在字符串s中,空字符串ε可以出现在任何位置。

证明

1. 如果|s| = 0(即s的长度为零),那么s = ε,命题成立。

2. 如果|s| > 0,则s有两个边缘位置:第一个符号之前和最后一个符号之后。由于ε是连接运算的恒等元素,即εs = = s,因此该命题对于起始位置和结束位置都成立。

3. 如果|s| > 1,则s可以被写成两个非空字符串的连接:s = pq,其中|p| > 0且|q| > 0。利用ε的恒等元素属性,pεq = (pε)q = pq = s,这意味着该命题适用于将其分成部分pqs中的位置。该分割的位置可以是s的任何内部位置,因此该命题对于每个内部位置也成立。

推论

身份元素属性意味着 ε = εε = εεε = 等等。将上述证明中的 ε 替换为正整数 n 的幂 ε^n,我们发现任何字符串中的任何位置都有无限数量的空字符串。

注释

这里的“位置”指的是“插入符”(文本插入光标)的位置。插入符可以放在第一个符号之前(索引:0)、在连续符号之间以及最后一个符号之后(索引:|s|)。插入符的数量是|s|+1。

上述证明表明,可以将符号之间的这些“零宽度间隙”想象成用任意数量的 字符串填充。(这就像空集是每个集合的子集,包括它自己一样奇怪。)


在连续存储的两个相邻字符之间,如何存在一个可寻址的空字符串? - Thomas Matthews
@ThomasMatthews 我在我的答案末尾添加了一些注释,以澄清索引/寻址的问题。 - kol

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接