17

我在解决问题时遇到了问题：- 这是一个作业，我解决了，但它似乎太长太模糊了，请任何人帮助我......

具有偶数个 a 和奇数个 b 的字符串的正则表达式，其中字符集={a,b}。

4

13 回答 13

21

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

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

其他任何事情（事实上，即使如此）很可能只是试图变得聪明，这通常是一个巨大的失败。

第一个正则表达式确保在混合中的任何地方（之前、之后和中间）都有偶数个awith 。b

第二个是类似的，但确保有一个奇数的b凭借 start a*ba*。

一个更好的方法是完全忽略正则表达式并简单地遍历字符串，如下所示：

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 的一篇论文。有关实际的内部工作原理，请参见此处。

于 2010-09-13T07:59:49.157 回答
6 
Even-Even = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

（Even-Even 有偶数个 Aas 和 b 都有）

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

这应该有效

于 2018-09-09T17:12:31.617 回答
2

此正则表达式采用偶数 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))*
于 2017-10-10T13:37:16.483 回答
1
  1. (bb)*a(aa)*ab(bb)*
  2. ab(bb)* a(aa)*
  3. b(aa)*(bb)* .
    .
    .
    .
    .
    .

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

于 2010-09-13T08:00:44.367 回答
1

对于偶数的 a's 和 b's ，我们有正则表达式：

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

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

所需的正则表达式将是：

E = { ((ab + ba) (aa+bb)* (ab+ba))* b ((ab + ba) (aa+bb)* (ab+ba))* }
于 2018-11-23T09:45:22.300 回答
0

我会这样做：

  • 正则表达式甚至匹配符号a，然后是b序列，然后是符号a，然后是另一个b序列，这样就有偶数个b：

偶数-> ( a ( bb )* a ( bb )* | a b ( bb )* a b ( bb )*)

  • 正则表达式奇数对奇数个b的总数相同：

奇数-> ( a b ( bb )* a ( bb )* | a ( bb )* a b ( bb )*)

由偶数个a和奇数个b组成的字符串：

  • 以奇数个b开始，然后是偶数模式中的偶数个奇数模式；
  • 或以偶数个b开始，然后是偶数模式中的奇数个奇数模式。

请注意，even与字符串中a / b的偶数/奇数无关。

正则表达式 -> (

b ( bb )*偶数* (奇数 偶数* 奇数)*偶数*

|

( bb )*偶数* 奇数 偶数* (奇数 偶数* 奇数)*偶数*

)

当然，可以替换最终正则表达式中出现的偶数和奇数，以获得单个正则表达式。

很容易看出，满足这个正则表达式的字符串确实会有偶数个a（因为符号a只出现在偶数和奇数子正则表达式中，并且每个都使用两个a）和奇数个b ' s（第一种情况：1 b + b的偶数 + 奇数的偶数；第二种情况：b的偶数 + 奇数的奇数）。

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

于 2016-10-21T10:45:16.590 回答
0

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

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

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

于 2019-02-02T05:25:16.940 回答
0

一个高级建议：为该语言构造一个确定性有限自动机——非常简单，编码状态中as 和bs的数量的奇偶校验，q0甚至编码 nr。as 甚至 nr 。s，并相应地b转换---，然后将 DFA 转换为正则表达式（通过为此使用众所周知的算法或“从头开始”）。

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

于 2016-12-13T13:39:17.123 回答
0

正则表达式如下：

    (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*b)*
于 2017-12-01T18:05:12.523 回答
-1

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

于 2014-11-30T12:07:41.200 回答
-1

(bb)* b (aa)* + (aa)* b (bb)*

这是处理所有带有奇数 b 甚至 a 的字符串的答案。

于 2016-02-25T09:41:44.430 回答
-2

所有包含偶数 a 和奇数 b 的字符串 (((aa+bb) * b(aa+bb) * ) + (A +((a+b)b(a+b)) *)) *

这里 A 是空字符串。A 可以忽略不计。

如果有任何错误请指出。

于 2017-04-09T05:20:37.930 回答
-2

如果是偶数个 a 后跟奇数个 b (aa)*b(bb)* 应该可以

如果它以任何顺序 (aa)*b(bb)* + b(bb) (aa)应该工作

于 2016-12-18T03:51:12.000 回答