Reg-Ex für gerade Anzahl von 0EN und 1en

Ich versuche, erstellen Sie einen regulären Ausdruck, der bestimmt, ob eine Zeichenfolge (jeder Länge) entspricht einem regex-Muster so, dass die Anzahl der 0EN in der Zeichenkette ist, selbst, und die Anzahl der 1en in der Zeichenfolge selbst. Kann mir jemand helfen, festzustellen, eine regex-Anweisung, die ich versuchen könnte, und überprüfen Sie die Zeichenfolge, die für dieses Muster?

  • Was haben Sie versucht?
  • gibt es irgendein limit, wie lange die Zeichenfolge (mit der binäre) sein könnte? wie viele bits?
  • Es gibt keine Begrenzung (außer für das, was der string-Zeichen-Grenze ist offensichtlich). 🙁
  • Sorry, ich verpasste Ihre erste post. Ich habe versucht, brechen Sie die Optionen unten, um wiederholbare 2,4,8 Charakter Abschnitten, haben aber versäumt, etwas zu finden, ist in der Lage, alle verfügbaren Optionen.
  • Warum müssen Sie regex verwenden? Es wäre einfacher, a) Ersetzen Sie alle diejenigen, die mit Leerzeichen/null-strings b) Erhalten Länge string/Zahl- > "L" c) Prüfen, ob L gerade ist.
  • hat die pumping-lemma-Arbeit? Nehmen Sie p = 4, und y zu sein, das erste vorkommen von 11 oder 00 (oder wenn das nicht auftreten, in den ersten 4 Zeichen: 1010 oder 0101), dann erfüllt er die Bedingung des pumping lemma (soweit ich das verstanden habe), und der Beweis durch Widerspruch misslingt.

InformationsquelleAutor canton | 2012-04-18
  1. 8

    Also völlig neu formuliert, meine Antwort zu spiegeln alle die änderungen:

    Dieser regex entsprechen würden alle Zeichenfolgen, die nur mit Nullen und Einsen und nur gleiche Mengen dieser

    ^(?=1*(?:01*01*)*$)(?=0*(?:10*10*)*$).*$

    Sehen es hier auf Regexr

    Arbeite ich hier mit positive lookahead-assertions. Der große Vorteil ist hier eine lookahead-assertion, dass es prüft die komplette Zeichenfolge, aber ohne die passende it, um die beiden lookaheads beginnen, überprüfen Sie die Schnur von Anfang an, aber für unterschiedliche Aussagen.

    1. (?=1*(?:01*01*)*$) überprüft, einen gleichen Betrag von 0 (einschließlich 0)

    2. (?=0*(?:10*10*)*$) überprüft, für eine gleiche Menge von 1 (einschließlich 0)

    3. .* hat dann eigentlich mit der Zeichenfolge

    Diese lookaheads überprüft:

    (?=
    1*    # match 0 or more 1
    (?:   # open a non capturing group
        0     # match one 0
        1*    # match 0 or more 1
        0     # match one 0
        1*    # match 0 or more 1
    )
    *     # repeat this pattern at least once
    $     # till the end of the string
)
    • Es funktioniert, obwohl es nicht erkennen 11 oder 1111, aber es funktioniert... Gut gemacht! 😉
    • Also ich bin gerade ein wenig verwirrt. Das ist ziemlich unglaublich. Aber wie geht das nicht akzeptieren, das Muster 00000? Denn wir haben abgestimmt 0 mit jedem Ihrer 3 separate [0^\s]* überprüft und zusätzlich eine 0 mit jeweils 0 überprüfen.
    • workaround zu ermöglichen, die völlig Abwesenheit von einer Ziffer.
    • Ich aktualisiert meine Lösung. Das war nur, weil es erwartet, dass mindestens 2 der einzelnen Ziffern. Jede dieser Behauptungen ist voll gefüllt.
    • Können nicht ändern Sie einfach die + in der "look ahead" zu * zu vermeiden, mit den | und noch akzeptieren 11 etc?
    • Nein, dann die lookahead-test würde für den leeren string, aber nicht für eine nicht vorkommen, dass Ziffer.
    • Nicht die $ es halt nur anpassen das leere Zeichenfolge (es sei denn, der string ist leer)?
    • Jede Behauptung muss wahr sein, wenn in (?=(?:[^0\s]*0[^0\s]*0[^0\s]*)*$) den äußeren * ist gleich null, Sie effektiv haben (?=$) das bedeutet, dass die Behauptung wahr ist, wenn nach dem start der Zeichenkette (wegen der ^ am start) folgt $, so seine true, wenn der string leer ist.
    • Ja, das verstehe ich. Können Sie es nicht erlauben, die lookaheads zu entsprechen, der leere string, und nur einschränken, nicht-leere mit Hilfe der nicht-lookahead-Abschnitt. d.h. + zu * im look-aheads (Vermeidung der |) und ändern Sie die (nicht-lookahead) [01]* zu [01]+. (Also, es ist nicht einmal klar, dass der leere string sollte scheitern: "" enthält 0 1s und 0 0s, und 0 ist gerade.)
    • Ich dachte wieder über meine Lösung und es gibt natürlich eine Lösung ohne Wechsel. Ich aktualisiert meine Antwort.
    • Wenn Sie nur gehst, um zu ermöglichen 0 und 1 sowieso (über den Teil der regex, der tatsächlich verbraucht die passenden Zeichen, nämlich die ^[01]*$ Teil, dann brauchen Sie nicht alle diese [^0\s]* und [^1\s]* - 1* und 0* wird genauso gut funktionieren.
    • Ich weiß, und ich aktualisierte meine Antwort einmal mehr.

    InformationsquelleAutor stema
  2. 4

    Auch für Gruppen von 0s, können Sie mit der folgenden regex, um sicherzustellen, dass die Anzahl der 0EN gerade ist. 

    ^(1*01*01*)*$

    Aber ich glaube, dass die Frage ist, haben beide eine gerade Anzahl von 0EN und auch eine gerade Anzahl von 1en. Da es möglich ist, konstruieren Sie einen nichtdeterministischen endlichen Automaten (NFA) für dieses problem, die Lösung ist eine regelmäßige und dargestellt werden kann, mit einem regex-Ausdruck. Die NFA ist vertreten über die Maschine unten ist S1 der start - /exit-Zustand.

    S1 ---1----->S2
|^ <--1----- |^
||           ||
00           00
||           ||
v|           v|
S3----1----->S4
  <---1------

    Von dort, es gibt einen Weg, um zu konvertieren NFAs zu regex-Ausdrücke, aber es ist schon eine Weile seit meiner Berechnung natürlich. Es gibt einige Hinweise unten, die scheinen hilfreich zu sein bei der Erklärung der Schritte zum umwandeln eines NFA zu einem regex.

    http://www.cs.uiuc.edu/class/sp09/cs373/lectures/lect_08.pdf

    • Auf dieser Basis, denke ich ^((1|0(11)*10)(00|0110)*(1|01(11)*0)|0(11)*0)*$ funktioniert. (Möglicherweise kann faktorisiert werden kleiner). regexr.com?30m8j
    • Ich arbeite schon an der Lösung als gut, aber das sieht mir Recht sein. Ich bin mir nicht sicher, was die Unterschiede sind zwischen der Verwendung des lookaheads. Jedoch ich vermute, dies ist ein Hausaufgaben problem (sonst gibt es viel einfachere Wege für die Bewältigung dieser Lösung).
    • NÖ, ich war falsch. Dass man nicht mit 10111101, aber dies bedeutet: ^((1|0(11)*10)(0(11)*0)*(1|01(11)*0)|0(11)*0)*$
    InformationsquelleAutor David Z.
  3. 4

    So, ich habe endlich eine Lösung für das problem:

    (11+00+(10+01)(11+00)\*(10+01))\*
    • +1. Clevere Lösung. Es würde so geschrieben werden, als ^(11|00|(10|01)(11|00)*(10|01))*$ im gemeinsamen regex flavors. Der trick hier ist zu erkennen, dass die Frage ist in der Tat äquivalent zu "geraden Anzahl von As in einem string der As und Bs", wo A wird ergänzt durch 10|01 und B wird ergänzt durch 11|00.
    InformationsquelleAutor canton
  4. 1

    RE-AKTUALISIERT WERDEN,

    Versuchen Sie dies : [ schauen Sie sich diese demo an : http://regexr.com?30m7c ]

    ^(00|11|0011|0110|1100|1001)+$

    Hinweis :

    die geraden zahlen sind durch 2 teilbar, also - in Binär - Sie enden immer in null (0)

    • Dies ist auch für binäre zahlen ... bedeutet nicht, dass count(0) ist auch die count(1) ist auch ...
    • Sieht aus wie du hast einen Punkt hier; ich falsch verstanden die Frage... Lass mich ein wenig darüber nachdenken...
    • Ja, @pst korrekt ist. Ich bin nicht auf der Suche auf den binären Wert; ich bin nur um die zahlen, die von 1s und 0s. Danke.
    • Gerade aktualisiert meine Antwort; check it out 😉
    • würde nicht zulassen, dass die string-0111? das würde nur behaupten, dass die Gesamtzahl der Zeichen ist auch, glaube ich.
    • Ich nur re-re-aktualisiert. Überprüfen Sie heraus. Baaah! Ich bin nahe; ich kann es fühlen! 🙂
    • Nun, wie wäre es für strings der Länge 6? 8? 10? 12? Das Problem ist, dass jeder neue Länge von 2 führt eine neuen - Muster nicht erstellen-können von der vorherigen.
    • Ich habe gedacht, so etwas in der Art, aber ich glaube, ich bin dann fehlt der string 11101110. und ich denke, es wächst exponentiell schlimmer, weil ich müsste noch ermöglichen die Möglichkeit, 1 verkettet mit jeder geraden Anzahl von wiederholt 0 und 1 am Ende (also "10000000000001" oder "10000001")
    • es ist wahr. wir sind immer noch fehlen diese; aaaaargh, gib mir eine Sekunde. Durchaus für ein problem, huh?! 🙂

    InformationsquelleAutor Dr.Kameleon
  5. 1

    Nicht einen regulären Ausdruck (was wahrscheinlich unmöglich ist, kann ich zwar nicht beweisen es: der Beweis durch Widerspruch über das pumping-lemma ausfällt), aber der "richtige" Lösung ist die Vermeidung einer komplizierten und ineffizienten regulären Ausdruck alle zusammen, und etwas wie (in Python):

    def even01(string):
     return string.count("1") % 2 == 0 and string.count("0") % 2 == 0

    Oder wenn der string bestehen nur aus 1s und 0s:

    import re
def even01(string):
     return not re.search("[^01]",string) and \
            string.count("1") % 2 == 0 and string.count("0") % 2 == 0
    InformationsquelleAutor huon
  6. 1
    ^(0((1(00)*1)*0|1(11|00)*01)|1((0(11)*0)*1|0(11|00)*10))*$

    Wenn ich nicht etwas übersehen, dies entspricht einem beliebigen bit-string, wo die Anzahl der 0EN ist auch und die Anzahl der 1en gerade ist, mit nur rudimentäre regex-Operatoren (*, ^, $). Es ist etwas einfacher, um zu sehen, wie es funktioniert, wenn wie folgt geschrieben:

    ^(0((1(00)*1)*0
   |1(11|00)*01)
 |1((0(11)*0)*1
   |0(11|00)*10))*$

    Den folgenden test-code soll dies verdeutlichen die Richtigkeit - wir vergleichen das Ergebnis der pattern-match gegen eine Funktion, die uns sagt, ob ein string eine gerade Anzahl von 0EN und 1en. Alle bit-strings der Länge 16 getestet.

    import re

balanced = lambda s: s.count('0') % 2 == 0 and s.count('1') % 2 == 0

pat = re.compile('^(0((1(00)*1)*0|1(11|00)*01)|1((0(11)*0)*1|0(11|00)*10))*$')

size = 16
num = 2**size
for i in xrange(num):
    binstr = bin(i)[2:].zfill(size)
    b, m = balanced(binstr), bool(pat.match(binstr))
    if b != m:
        print "balanced('%s') = %d, pat.match('%s') = %d" % (binstr, b, binstr, m)
        break
    elif i != 0 and i % (num / 10) == 0:
        # Python 2's `/` operator performs integer division
        print "%d percent done..." % (100 * i / num + 1)
    InformationsquelleAutor Sean Kelleher
  7. 0

    Wenn Sie versuchen, Sie zu lösen innerhalb den gleichen Satz (beginnend mit ^ und endend mit $), Sie sind in der tiefen Mühe. 🙂

    Können Sie sicherstellen, dass Sie eine gerade Anzahl von 0EN (mit ^(1*01*01*)*$, wie bereits von @david-z) ODER können Sie sicherstellen, dass Sie eine gerade Anzahl von 1en:

    ^(1*01*01*)*$|^(0*10*10*)*$

    Es Werke für Streicher mit kleinen Längen, als auch, wie "00" oder "101", gültige Zeichenfolgen.

    InformationsquelleAutor eduellery
  8. 0

    Habe ich auch gearbeitet lookaheads und lookbacks in meiner Freizeit, und mit lookahead-das problem kann gelöst werden, während der Einnahme auch der Grund für die Einzel-1s und/oder das Einzel-0s. So soll der Ausdruck auch für 11,1111,111111,... und auch für 00,0000,000000,....

    ^(((?=(?:1*01*01*)*$)(?=(?:0*10*10*)*$).*)|([1]{2})*|([0]{2})*)$

    Funktioniert für alle Fälle.
    Also, wenn der string besteht nur aus 1en oder nur 0EN:

    ([1]{2})*|([0]{2})*

    Wenn es enthält eine Mischung von 0s und 1s, die positive lookahead wird sich darum kümmern. 

    ((?=(?:1*01*01*)*$)(?=(?:0*10*10*)*$).*

    Kombination der beiden von Ihnen, es berücksichtigt alle Zeichenfolge mit einer geraden Anzahl von 0s und 1s.

    InformationsquelleAutor Biplob Manna
Schreibe einen Kommentar