10 模式匹配

10.1 模式匹配相关函数

10.1.1 函数 string.find

函数string.find具有两个可选参数。第三个参数是一个索引，用于说明从目标字符串的哪个位置开始搜索。第 4 个参数是一个布尔值，用于说明是否进行简单搜索。

> string.find("a [word]","[")
stdin:1: malformed pattern (missing ']')
stack traceback:
        [C]: in function 'find'
        stdin:1: in main chunk
        [C]: ?
> = string.find("a [word]", "[", 1, true)
3       3
>

由于 '[' 在模式中具有特殊含义，因此第 1 个函数调用会报错。在第 2 个函数调用中，函数只是把 '[' 当作简单字符串。请注意，如果没有第 3 个参数，是不能传入第 4 个参数的。

10.2 模式

字符	匹配
.	任意字符
%a	字母
%c	控制字符
%d	数字
%g	除空格外的可打印字符
%l	小写字母
%p	标点符号
%s	空白字符
%u	大写字母
%w	字母和数字
%x	十六进制数字

所谓的控制字符指的是换行、退格、删除、转义、制表等等，空格并不包含在控制字符中

str = [[
first line
second line
third line
]]

print(string.gsub(str, "%c", "1"))    -->    控制字符替换为1

--> first line1second line1third line1  3

模式的字母改成大写就表示类的补集，例如，'%A'表示任意非字母的字符。

在模式匹配中，还有一些被称为魔法字符的字符具有特殊含义。Lua 语言的模式所使用的魔法字符包括：

() . % + - * ? [] ^ $

在这些字符前面加百分号可以用来转移这些字符。我们不仅可以用百分号对魔法字符进行转义，还可以将其用于其他所有字母和数字外的字符。当不确定是否需要转义的时候，为了保险起见就可以使用转义符。

10.6 练习

练习 10.1：请编写一个函数 split，该函数接收两个参数，第 1 个参数是字符串，第 2 个参数是分隔符模式，函数的返回值是分隔符分割后的原始字符串中每一部分的序列：

t = split("a whole new world", " ")    -->    t = {"a", "whole", "new", "world"}

你编写的函数是如何处理空字符串的呢？特别是，一个空字符串究竟是空序列，还是一个具有空字符串的序列呢？

思考了一下，题目最后的意思应该是，如果有一个空字符串应该返回 {} 还是 {""}，如果从分割这个词本身的含义出发，如果它没有找到与模式匹配的字符，就应该不对原串做任何操作而原样返回，因此，如果是一个空字符串的话，应该返回 {""}。

---@return table
---@param str string
---@param pattern string
function split(str, pattern)
    local t = {}
    local startPos = 1
    local endPos = 1

    while true do
        endPos = string.find(str, pattern, startPos, true)

        if (endPos == nil) then
            table.insert(str)
            break
        elseif (endPos == startPos) then
            table.insert(t, "")
        else
            table.insert(t, string.sub(str, startPos, endPos -1))
        end
        startPos = endPos + 1
    end
    table.insert(t, string.sub(str, startPos, #str))
    return t
end

由于空字符串没法打印出来，所以只能通过 Debug 查看表的内容。

table中的空字符串

可见，在我的写法中，如果传入一个空字符串最后会返回一个有一个元素为空字符串的表。

练习 10.2：模式 '%D' 和 '[^%d]' 是等价的，那么模式 '[^%d%u]' 和 '[%D%U]' 呢？

先吐槽一下，这题目颇有一种 "已知 1 + 1 = 2，求证相对论" 的那种感觉了。
我们可以用反证法来证明，如果我要证明这两者不等价，我应该举一个反例，在开始找反例之前，我猜测这个 ^ 符号只作用于其后一个模式，第二个没有效果，所以我应该尝试一下找一个非数字大写字符，如果前面可以匹配后面不能匹配，就说明二者不等价，试一下：

str = "DDDDD"

print(string.match(str,"[^%d%u]"))    -->    nil
print(string.match(str,"[%D%U]"))    -->    D

从结果可以看出，我的猜测是正确的，^ 符号只能作用于离它最近的一个模式，验证一下后面如果也加上 ^ 对不对。

测试之后发现并不对，这说明虽然结论没错，但是还没有找到这二者不等价的真正原因。

str = "1234567890QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm"

print(string.gsub(str, "[%d%u]", ""))
print(string.gsub(str, "[%D%U]", ""))
print(string.gsub(str, "[^%d%u]", ""))

-----------------------
qwertyuiopasdfghjklzxcvbnm  36
    62
1234567890QWERTYUIOPASDFGHJKLZXCVBNM    26

这说明问题可能跟集合的运算有关。
经过测试 [^%d%u] 代表的是数字和大写字母合集的补集，所以匹配的应该是除了数字和大写字母以外的字符，而 [%D%U] 是补集的合集，由于数字和大写字母的集合并不相交，所以他们补集的合集就是全集，所以可以匹配任何字符。

当把 [^%d%u] 替换为 [%u^%d] 以后， ^ 的效果直接失效了，并且它被识别为一个字符。

str = "1234567890QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm!@#$%^&*()"

print(string.gsub(str, "[^%d%u]", ""))
print(string.gsub(str, "[%D%U]", ""))
print(string.gsub(str, "[%u^%d]", ""))
print(string.gsub(str, "[%u%d]", ""))

-----------------------
1234567890QWERTYUIOPASDFGHJKLZXCVBNM    36
    72
qwertyuiopasdfghjklzxcvbnm!@#$%&*() 37
qwertyuiopasdfghjklzxcvbnm!@#$%^&*()    36

可见这段程序中，^被当作一个字符对待且被替换了。

感觉这个模式的匹配规则很复杂，目前就找到这么多问题，如果以后还能发现更多的特殊情况再来考虑吧。

练习 10.3：请编写一个函数 transliterate，该函数接收两个参数，第 1 个参数是字符串，第 2 个参数是一个表。函数 transliterate 根据第二个参数中的表使用一个字符替换字符串中的字符。如果表中将 a 映射为 b，那么该函数则将所有 a 替换为 b。如果表中将 a 映射为 false，那么该函数则把结果中的所有 a 移除。

从 10.4节中我们知道，如果 gsub 第三个参数传入一个表，那么函数就会按照表的映射关系自动替换结果，我们首先要看一下键对应的值为 false 时是什么样的效果。

t = {a = "1", b = "2", c = "3", d = false}
str = "aaabbbcccddd"

print(string.gsub(str, ".", t))

---------------------

111222333ddd    12

可以看见 false 的情况并未处理，所以当某个键对应的值是 false 时，需要单独处理。

---@return string
---@param str string
---@param pattern table
function tansliterate(str, pattern)
    local s = ""
    for k,v in pairs(pattern) do        --先把 值为 false 的键的值替换为 ""
        if (v == false) then
            pattern[k] = ""
        end
    end
    s = string.gsub(str, ".", pattern)      --捕获任意字符，然后根据表进行替换
    return s
end

str = "aabbccdd"
t = {a = "1", b = "2", c = "3", d = false}

print(tansliterate(str,t))    -->    112233

练习 10.4：在 10.3 节的最后，我们定义了一个 trim 函数。由于该函数使用了回溯，所以对于某些字符串来说，该函数的时间复杂度是 O(n²) 。例如，在笔者的新机器上，针对一个 100KB 大小字符串的匹配可能会耗费52秒。
- 构造一个可能会导致 trim 耗费 O(n²) 时间复杂度的字符串。
- 重写这个函数使得其时间复杂度为 O(n)

先把 trim 函数抄写过来

---@return string
---@param s string
function trim(s)
    s = string.gsub(s, "^%s*(.-)%s*$","%1")
    return s
end

这个函数的作用是剔除字符串两端的空格，如果所有的字符都是空格，那么每一个位置都需要检验，就会达到 O(n²)。