具有偶数个a和奇数个b的字符串的正则表达式

Question

我在解决这个问题时遇到麻烦：- 这是一个任务，我已经解决了它，但似乎太长而且含义模糊，请问有人能帮忙吗......

匹配由字符集{a, b}组成的偶数个a和奇数个b的字符串的正则表达式。

- Abu Mathew

---

请发布您的解决方案，这样人们就可以提出具体的改进建议。 - Ian Henry

正则表达式的目的是什么？有多少个“a”和“b”的序列？你能展示一下你是如何解决它的吗？这可能有助于确定一个可以完成相同任务的正则表达式。 - Lazarus

你不想在这里使用正则表达式 - 这个任务应该用一个简单的“不要！”和几行代码来解决。 - atamanroman

从我的回答中获取灵感：如何使用Arden定理为DFA编写正则表达式 - Grijesh Chauhan

Answer 1

其中一种方法是将其通过两个正则表达式，确保它们都匹配（假设您确实想要使用正则表达式，请参见下面的替代方案）：

^b*(ab*ab*)*$
^a*ba*(ba*ba*)*$

除此以外的任何东西（实际上，即使是这样）都很可能只是试图聪明，但通常是巨大的失败。

第一个正则表达式确保在混合物中（之前、之后和之间），a 和 b 的数量是偶数。

第二个也类似，但通过起始的 a*ba* 确保 b 的数量是奇数。

---

一个远更好的方法是完全忽略正则表达式，并按以下方式遍历字符串：

def isValid(s):
    set evenA to true
    set oddB to false
    for c as each character in s:
        if c is 'a':
            set evenA to not evenA
        else if c is 'b':
            set oddB to  not oddB
        else:
            return false
    return evenA and oddB

虽然正则表达式是一个很棒的工具，但并不适用于所有情况。当其可读性和可维护性降低时，它们的效用也会大大降低。

---

值得一提的是，单个正则表达式的答案为：

(aa|bb|(ab|ba)(aa|bb)*(ba|ab))*(b|(ab|ba)(bb|aa)*a)

但是，如果我发现我的团队中有人实际上使用像那样的丑陋东西，他们将被送回去重新做。

这句话来自Greg Bacon的一篇论文。请参见这里获取实际的内部工作原理。

- paxdiablo

Answer 2

Even-Even = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

（Even-Even包含偶数个a和b）

偶数个a和奇数个b = Even-Even b Even-Even

这应该可以工作

- Veenu

Answer 3

这个正则表达式匹配所有包含偶数个a和偶数个b的字符串。

r1=((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

现在需要获取仅包含偶数个a和奇数个b的正则表达式。

r2=(b+a(aa+bb)*(ab+ba))((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

- Pooja Consul

Answer 4

1. (bb)*a(aa)*ab(bb)*
2. ab(bb)* a(aa)*
3. b(aa)*(bb)* .
   .
   .
   .
   .
   .

可能会有许多这样的正则表达式。您是否有任何其他条件，例如“以a开头”或类似条件（除了奇数个'b'和偶数个'a'）？

- vandanak

---

我正在寻找偶数个b和奇数个a，所以我修改了你的正则表达式 (aa)*b(bb)*ba(aa)*，现在对我有效了，谢谢啊伙计。 - Khurram Ali

Answer 5

对于a和b的数量均为偶数，我们有正则表达式：

E = { (ab + ba) (aa+bb)* (ab+ba) }*

对于偶数个a和奇数个b，我们只需要在上面的表达式E中添加一个额外的b即可。

所需的正则表达式为：

E = { ((ab + ba) (aa+bb)* (ab+ba))* b ((ab + ba) (aa+bb)* (ab+ba))* }

- Abhinav Rastogi

Answer 6

一个高层次的建议：为该语言构建一个确定性有限自动机——非常容易，将a和b的数量的奇偶性编码到状态中，其中q0编码了偶数个a和偶数个b，并相应地进行转换——，然后将DFA转换为正则表达式（可以使用已知的算法或“从头开始”）。

这里的想法是利用DFA（正则语言的算法描述）和正则表达式（正则语言的代数描述）之间的众所周知的等价关系。

- blazs

Answer 7

我会按照以下方式进行：

• 正则表达式even匹配符号a，然后是一系列的b，再次是符号a，然后是另一个b序列，使得b的数量为偶数：

even -> (a (bb)* a (bb)* | a b (bb)* a b (bb)*)

• 正则表达式odd使用奇数个b执行相同操作：

odd -> (a b (bb)* a (bb)* | a (bb)* a b (bb)*)

一个由偶数个a和奇数个b组成的字符串，要么：

• 以奇数个b开头，并在偶数个偶数模式中间跟随奇数个奇数模式；
• 或以偶数个b开头，并在奇数个偶数模式中间跟随奇数个奇数模式。

请注意，偶数对于字符串中a/b的奇偶性没有影响。

正则表达式 -> (

b (bb)* even* (odd even* odd)* even*

|

(bb)* even* odd even* (odd even* odd)* even*

（bb）*偶数奇数偶数（奇数偶数奇数）*偶数

)

当然，可以在最终的正则表达式中替换每个even和odd的出现次数，以获得单个正则表达式。

很容易看出，满足此正则表达式的字符串确实具有偶数个a（因为符号a仅出现在even和odd子正则表达式中，并且这些子正则表达式各使用了两个a），以及奇数个b（第一种情况：1个b+偶数个b+偶数个odd；第二种情况：偶数个b+奇数个odd）。

具有偶数个a和奇数个b的字符串将满足此正则表达式，因为它以零个或多个b开头，然后是[一个a，零个或多个b，再加上一个a和零个或多个b]，重复零次或多次。

- Fabian Pijcke

Answer 8

以下是正则表达式：

    (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*b)*

- rashedcs

Answer 9

结构化的方法是制作一个转换图并从中构建正则表达式。 在这种情况下，正则表达式将是

(a((b(aa)*b)*a+b(aa)*ab)+b((a(bb)*a)*b+a(bb)*ba))b(a(bb)*a)*

看起来很复杂，但它涵盖了可能出现的所有情况。

- Ricky

Answer 10

答案是 (aa+ab+ba+bb)* b (aa+ab+ba+bb)*

- Nishant Chaturvedi

---

它可以接受具有奇数个a和偶数个b的baaab。 - Daniel.V