应用编程/正则表达式

正则表达式

在编程中，正则表达式指的是一系列字符，可以用来指定搜索功能。它们允许以健壮且强大的方式搜索大量数据，而无需创建冗余或重复的代码行。正则表达式（简称 regex）就像代码中的 Ctrl+F，允许我们轻松地检索数据模式，例如电子邮件地址、域名、电话号码；实际上，任何我们可以归因于模式的数据。

正则表达式字符由特殊元字符和用于指定要匹配字符串元素的某些标准字符的组合构成。

元字符

元字符是一个对计算机程序（如 Shell 解释器或正则表达式 (regex) 引擎）具有特殊意义的字符。

字符

• []

一组字符

 import re
 
 txt = "The rain in Spain"
 
 #Find all lower case characters alphabetically between "a" and "m":
 
 x = re.findall("[a-m]", txt)
 print(x)

输出

['h', 'e', 'a', 'i', 'i', 'a', 'i']

• \

表示特殊序列（也可以用于转义特殊字符）

 import re
 
 txt = "That will be 59 dollars"
 
 #Find all digit characters:
 
 x = re.findall("\d", txt)
 print(x)

输出

['5', '9']

• .

任何字符（换行符除外）

 import re
 
 txt = "hello world"
 
 #Search for a sequence that starts with "he", followed by two (any) characters, and an "o":
 
 x = re.findall("he..o", txt)
 print(x)

输出

['hello']

• ^

以…开头

 import re
 
 txt = "hello world"
 
 #Check if the string starts with 'hello':
 
 x = re.findall("^hello", txt)
 if x:
   print("Yes, the string starts with 'hello'")
 else:
   print("No match")

输出

Yes, the string starts with 'hello'

• $

以…结尾

 import re
 
 txt = "hello world"
 
 #Check if the string ends with 'world':
 
 x = re.findall("world$", txt)
 if x:
   print("Yes, the string ends with 'world'")
 else:
   print("No match")

输出

Yes, the string ends with 'world'

• *

零个或多个出现

 import re
 
 txt = "The rain in Spain falls mainly in the plain!"
 
 #Check if the string contains "ai" followed by 0 or more "x" characters:
 
 x = re.findall("aix*", txt)
 
 print(x)
 
 if x:
   print("Yes, there is at least one match!")
 else:
   print("No match")

输出

['ai', 'ai', 'ai', 'ai']
Yes, there is at least one match!

• +

一个或多个出现

 import re
 
 txt = "The rain in Spain falls mainly in the plain!"
 
 #Check if the string contains "ai" followed by 1 or more "x" characters:
 
 x = re.findall("aix+", txt)
 
 print(x)
 
 if x:
   print("Yes, there is at least one match!")
 else:
   print("No match")

输出

[]
No match

• {}

指定数量的出现

 import re
 
 txt = "The rain in Spain falls mainly in the plain!"
 
 #Check if the string contains "a" followed by exactly two "l" characters:
 
 x = re.findall("al{2}", txt)
 
 print(x)
 
 if x:
   print("Yes, there is at least one match!")
 else:
   print("No match")

输出

['all']
Yes, there is at least one match!

• |

两者之一

 import re
 
 txt = "The rain in Spain falls mainly in the plain!"
 
 #Check if the string contains either "falls" or "stays":
 
 x = re.findall("falls|stays", txt)
 
 print(x)
 
 if x:
   print("Yes, there is at least one match!")
 else:
   print("No match")

输出

['falls']
Yes, there is at least one match!

其他示例

在某些环境中，某些其他字符可能具有特殊含义。

• 在某些 Unix Shell 中，分号 (";") 是语句分隔符。
• 在 XML 和 HTML 中，与号 ("&") 引入 HTML 实体。它在 MS-DOS/Windows 命令提示符中也具有特殊含义。
• 在某些 Unix Shell 和 MS-DOS/Windows 命令提示符中，小于号和大于号 ("<" 和 ">") 用于重定向，重音符/反引号 ("`") 用于命令替换。
• 在许多编程语言中，字符串使用引号 (" 或 ') 定界。在某些情况下，转义字符（和其他方法）用于避免定界符冲突，例如 "他说，"你好""。
• 在 printf 格式字符串中，百分号 ("%") 用于引入格式说明符，必须转义为 "%%" 才能按字面意义解释。在 SQL 中，百分号用作通配符。
• 在 SQL 中，下划线 ("_") 用于匹配任何单个字符。

贪婪算法

贪婪是一种算法范式，它逐段构建解决方案，始终选择提供最明显和最直接好处的下一段。因此，选择局部最优也导致全局解决方案的问题最适合贪婪。

以下是使用贪婪方法的原因

• 贪婪方法有一些权衡，这可能使其适合优化。
• 一个突出的原因是立即获得最可行的解决方案。在活动选择问题中（如下所述），如果可以在完成当前活动之前执行更多活动，则可以在同一时间内执行这些活动。
• 另一个原因是根据条件递归地划分问题，而无需组合所有解决方案。
• 在活动选择问题中，"递归划分"步骤是通过仅扫描项目列表一次并考虑某些活动来实现的。

贪婪算法有一些优点和缺点

1. 提出贪婪算法（甚至多个贪婪算法）非常容易。
2. 分析贪婪算法的运行时间通常比其他技术（如分治法）容易得多。对于分治法，目前尚不清楚该技术是快还是慢。这是因为在每次递归级别上，大小都会变小，子问题数量会增加。
3. 困难的部分是，对于贪婪算法，您必须更努力地理解正确性问题。即使使用正确的算法，也很难证明为什么它是正确的。证明贪婪算法是正确的更像是一门艺术，而不是一门科学。它需要大量的创造力。

活动

1) 编写一个程序，使用正则表达式解析包含单个电子邮件地址的文本文件，并将它们排序到字典中，其中键是电子邮件地址的句柄，值是域。

示例：包含'[email protected]' 和 '[email protected]' 的文件将导致["johndoe": "aol", "janedoe": "yahoo"]。

2) 编写一个程序，使用正则表达式查找并替换字符串中所有元音的出现，并将它们替换为句点。仅在 'y' 是单词中唯一的元音时才替换 'y'。

示例："The quick brown fox jumped over the lazy dog" 将导致 "Th. q..ck br.wn f.x j.mp.d .v.r th. l.zy d.g"

3) 编写一个程序，使用正则表达式将 dd-mm-yyyy 格式的日期转换为 yy-mm-dd 格式。

示例：06-04-1992 将导致 92-06-04。

4) 编写一个程序，使用正则表达式分解 URL 并将信息排序到字典中。键应该是主要域，而值应该是子页面的列表。

示例："https://www.wikipedia.org/wiki/Computer_programming" 将导致["wikipedia": ['wiki', 'Computer_programming']]

关键词

近似字符串匹配算法 - （也称为模糊字符串搜索）搜索输入字符串的子字符串。

转义字符 - 用于绕过可能为元字符的符号并按字面意义表达符号的字符。

精确字符串匹配算法 - 在大型字符串（文本或序列）中查找一个、多个或所有已定义字符串（模式）的出现，以使每个匹配都完美。

贪婪算法 - 一种算法范式，它逐段构建解决方案，始终选择提供最明显和最直接好处的下一段。

Kleene 星号 - 提供与字符串集串联相关的结果的编程资源。使用 Kleene 星号，开发人员和其他人员可以评估如何根据输入过滤给定结果。

元字符 - 对计算机程序（如 Shell 解释器或正则表达式 (regex) 引擎）具有特殊意义的字符。

幺半群 - 一个集合，它配备了结合的二元运算和单位元。

模式 - 一个正则表达式，用来匹配或捕获文本。

量词 - 修饰符，它跟随另一个正则表达式标记，枚举预期出现的次数。

正则表达式处理器 - 将以上语法中的正则表达式转换为内部表示的处理器，可以执行并与表示要搜索文本的字符串进行匹配。

正则表达式 - 正则表达式（简称 regex 或 regexp）是一种描述搜索模式的特殊文本字符串。

通配符 - 代表任何内容的通用字符。