W "aa67bc54c9", czy istnieje sposób drukowania "aa" 67 razy, "bc" 54 razy itd., Używając wyrażeń regularnych?

Question

Zostałem poproszony o to pytanie w wywiadzie dla stażu, a pierwszym rozwiązaniem, które zasugerowałem, było użycie wyrażenia regularnego (zwykle jestem trochę zaskoczony w wywiadach). Coś podobnego do tego:

(?P<str>[a-zA-Z]+)(?P<n>[0-9]+) 

Myślałem, że pasuje do napisów i zapisuje je w zmiennej "str" ​​oraz liczby w zmiennej "n". Jak nie byłem tego pewien.

Tak więc pasuje do ciągów typu "a1b2c3", ale problem polega na tym, że pasuje również do ciągów typu "a1b". Czy ktoś mógłby zaproponować rozwiązanie tego problemu?

Czy istnieje również inne wyrażenie regularne, które może rozwiązać ten problem?

Answer 1

jak about:

while ($line =~ s/^([a-z]+)(\d+)//i) 
{ 
    print $1 x $2; 
} 

Answer 2

Odpowiadając na zapytanie bezpośrednio:

• No, wyrażenia regularne tekst mecz i niczego nie drukuje, więc nie ma sposobu, aby to zrobić wyłącznie za pomocą wyrażeń regularnych .

Podane wyrażenie regularne będzie pasowało do jednej pary znaków/liczb; możesz następnie drukować to wielokrotnie, używając odpowiedniego mechanizmu. Rozwiązanie Perla z @tster jest tak kompaktowe, jak to tylko możliwe. (Nie używa nazw, które zastosowałeś w swoim regex, jestem prawie pewien, że to nie ma znaczenia.)

Pozostałe szczegóły zależą od języka implementacji.

Answer 3

Czy wiesz, dlaczego "wyrazy regularne" są nazywane "zwykłymi"? :-)

To byłoby zbyt długie, aby wytłumaczyć, po prostu zarysuję drogę. Aby dopasować wzorzec (to znaczy zdecydować, czy dany ciąg jest "prawidłowy" lub "nieprawidłowy"), teoretyczny informatyk użyłby finite state automaton. To abstrakcyjna maszyna, która ma skończoną liczbę stanów; przy każdym tiku odczytuje znak z wejścia i przeskakuje do innego stanu. Skala miejsca przeskakiwania z określonego stanu, gdy czytany jest dany znak, jest stała. Niektóre stany są oznaczone jako "OK", niektóre - jako "NIEPOWODZENIE", dzięki czemu sprawdzając stan maszyny, możesz sprawdzić, czy Twój tekst jest "ważny" (tj. Ważny e-mail).

Na przykład, maszyna ta przyjmuje tylko „nice” jako „ważny” słowo (PIC z Wikipedii):

Zestaw „ważny” słów taka maszyna teoretycznie można odróżnić od nieprawidłowy to "regular language". Nie każdy zbiór jest zwykłym językiem: na przykład, automaty skończone nie są w stanie sprawdzić, czy nawiasy w łańcuchu są zrównoważone.

Ale konstruowanie maszyn stanu było złożonym zadaniem, w porównaniu ze złożonością definiowania, co jest "poprawne". Tak więc matematycy (głównie S. Kleene) zauważyli, że każde regular language można opisać za pomocą "regular expression". Mieli * s i | s i były prototypami tego, co znamy teraz jako regexps.

---

Co to ma wspólnego z problemem?Problem w temacie jest zasadniczo nieregularny. Nie można go wyrazić za pomocą niczego, co działa jak automat skończony.

Najważniejsze jest to, że powinien zawierać komórkę pamięci zdolną do przechowywania dowolnej liczby (liczba powtórzeń w twoim przypadku). Automaty skończone i klasyczne wyrażenia regularne nie mogą tego zrobić.

Jednak współczesne wyrazy regularne są bardziej wyraziste i are said to be able to check balanced parentheses! Ale może to być dobrym przykładem, że nie powinieneś używać wyrażeń regularnych do zadań, które im nie odpowiadają. Nie mówiąc o tym, że zawiera fragmenty kodu; to sprawia, że ​​wyrażenie nie jest "regularne".

Odpowiedzi na pierwsze pytanie, nie można rozwiązać problemu za pomocą niczego "zwykłego" tylko. Jednakże, wyrażenia regularne mogą być pomóc w rozwiązaniu tego problemu, jak w tster's answer

---

Być może należy szukać bliżej tster's answer (zrobić „+1” Nie, proszę!) I pokazać, dlaczego nie jest to „normalne wyrażenie "rozwiązanie. Można pomyśleć, że tak jest, zawiera on tylko instrukcję print (nieistotną), a koncepcja loop-and-loop jest kompatybilna z skończoną automatyczną ekspresją automatu stanu. Ale jest jeszcze jedna nieuchwytny rzecz:

while ($line =~ s/^([a-z]+)(\d+)//i) 
{ 
    print $1 
      x # <--- this one 
       $2; 
} 

Zadaniem czyta ciąg i numer i drukowanie wielokrotnie ten ciąg podano liczbę razy, gdzie liczba jest dowolną liczbą całkowitą, to cofnąć w stanie skończonej maszyna bez dodatkowej pamięci. Używasz komórki pamięci, aby zachować tę liczbę i ją zmniejszyć, i sprawdzić, czy jest ona większa od zera. Ale ta liczba może być arbitralnie duża i jest sprzeczna z skończoną skończoną pamięcią dostępną dla maszyny stanowej skończonej.

Jednak nie ma nic złego w klasycznym wzorze /([abc]*){5}/, który pasuje do czegoś "regularnego" powtórzonego naprawiono liczbę razy. Zasadniczo mamy stany, które odpowiadają "dopasowanemu wzorowi raz", "dopasowanemu wzorowi dwa razy" ... "dopasowanemu wzorowi 5 razy". Jest ich skończona liczba i to jest istotna różnica.

Answer 4

Nie, to jest twoje podstawowe "podchwytliwe pytanie" - bez względu na to, jak na nie odpowiesz, ta odpowiedź jest błędna, chyba że masz dokładnie odpowiedź, że ankieter został przeszkolony do papugi. Zobacz przeróbkę problemu podanego przez Pavel Shved - zauważ, że wszystkie wywołania mają "nie" jako typowy warunek, narzędzie po prostu ślizga się: Nawet gdy zmienia stan, nie ma licznika w tym stanie.

Mam dość zaawansowana książka Kennetha C Loudena, który jest profesorem w tej dziedzinie, w której stwierdza się, że kwestia jest skodyfikowana jako "Regex nie może liczyć". Oczywistą odpowiedzią na to pytanie wydaje mi się być w tej chwili, że używam poprzedniej cechy Regexa ...

Prawdopodobnie zależy od tego, z jakiej wersji marki regex korzysta ankieter, co prawdopodobnie zależy od dynamiki lotu Piłki golfowe.

Answer 5

Dobre odpowiedzi do tej pory. Same wyrażenia regularne są zwykle traktowane jako sposób dopasowywania wzorów, a nie generowania wyników w sposób, o którym wspomniałeś.

Powiedziawszy to, istnieje sposób użycia regex jako części rozwiązania.@ Jonathan Leffler napisał dobry komentarz do tster's reply: "... może potrzebujesz lepszej biblioteki regex w swoim języku."

W zależności od wybranego języka i dostępnej biblioteki, można ją usunąć. Na przykład przy użyciu C# i .NET można to osiągnąć za pomocą Regex.Replace method. Jednak rozwiązanie to nie 100% regex ponieważ nadal opiera się na innych klas i metod (StringBuilder, string.join i Enumerable.Repeat) jak pokazano poniżej:

string input = "aa67bc54c9"; 
string pattern = @"([a-z]+)(\d+)"; 
string result = Regex.Replace(input, pattern, m => 
     // can be achieved using StringBuilder or String.Join/Enumerable.Repeat 
     // don't use both 
     //new StringBuilder().Insert(0, m.Groups[1].Value, Int32.Parse(m.Groups[2].Value)).ToString() 
     String.Join("", Enumerable.Repeat(m.Groups[1].Value, Int32.Parse(m.Groups[2].Value)).ToArray()) 
     + Environment.NewLine // comment out to prevent line breaks 
     ); 
Console.WriteLine(result); 

Jaśniejsza rozwiązaniem byłoby zidentyfikowanie mecze , wykonaj pętlę nad nimi i wstaw je za pomocą StringBuilder zamiast polegać na Regex.Replace. Inne języki mogą mieć kompaktowe idiomy do obsługi mnożenia napisów, które nie opierają się na innych klasach bibliotek.

Aby odpowiedzieć na pytanie dotyczące wywiadu, odpowiedziałbym: "jest to możliwe, jednak rozwiązanie nie byłoby samodzielnym podejściem opartym na 100% wyrażeń regularnych i polegałoby na innych funkcjach językowych i/lub bibliotekach w celu radzenia sobie z aspektem generowania pytanie, ponieważ samo wyrażenie regularne jest pomocne w dopasowywaniu wzorców, a nie generowaniu ich. "

I na podstawie innych odpowiedzi tutaj, możesz w razie potrzeby uzupełnić tę odpowiedź.