McCullochs merkwürdige Zahlenmaschine - Reguläre Ausdrücke

Zunächst die Bedienungsanleitung:

1. Eine Ziffernfolge X  ist eine beliebige Folge von Ziffernzeichen, z.B.  X="0123456789", oder X="0815", oder X="447711" usw.
2. Die Ziffernfolge 2X ist die Ziffer "2" gefolgt von der Ziffernfolge X,  z.B.  mit X="234" ist  2X="2234" , analoges gilt 3X, 4X oder auch 1X  usw.
3. Die Ziffernfolge 2X ist eine für die Maschine annehmbare Ziffernfolge,  ebenso 32X oder jede beliebige andere Ziffernfolge der Ziffer "3" gefolgt von 2X, z.B. auch  332X oder 333332X  usw.; Alle anderen Ziffernfolgen sind für die Maschine nicht annehmbar.
4. Die Eingabe-Ziffernfolge 2X   wird von der Maschine zur Ausgabe-Ziffernfolge X  verbeitet: z.B.   wird mit X="23"  die Ziffernfolge  2X  zu  "23" verarbeitet. McCulloch nennt das "2X  produziert X".
5. Wenn nun eine Ziffernfolge Y die Ziffernfolge X produziert ( z.B. Y=2X produziert X ) dann produziert die Eingabe-Ziffernfolge 3Y die Ausgabe-Ziffernfolge  Y2Y, welche McCulloch die "assoziierte Grösse" von Y nennt.  Die assoziierte Grösse von "3" wäre dann "323" oder die von "4711" wäre  "471124711" usw.

Eine Auswahl von McCullochs Rätseln:

• Welche Ziffernfolge N produziert sich selbst ( man gibt also N ein und bekommt N heraus)?
• Welche Ziffernfolge N produziert  die assoziierte Grösse von N, also  N2N ?
• Welche Ziffernfolge N produziert 7N ,  also die Ziffer "7" gefolgt von der Eingabe-Ziffernfolge?
• Für welche Ziffernfolge N produziert 3N die assoziierte Grösse von N,  man gibt also 3N ein und erhält N2N ?
• Für welche Ziffernfolge N produziert 3N die Ziffernfolge 3N?

Wer mehr von diesen Rätseln möchte oder die Lösungen der vorhergegangenen Rätsel-Auswahl nicht selbst finden will, der sollte einmal einen Blick in das Buch werfen. Dort wird auch noch eine erweiterte Zahlenmaschine beschrieben, deren Umsetzung jedoch den für diesen Artikel gesteckten Rahmen  gesprengt hätte, denn hier soll es lediglich um ein illustratives Beispiel für den Einsatz regulärer Ausdrücke in ActionScript 3 gehen.

Nachfolgend der komplette Verarbeitungs-Code der Zahlenmaschine:

function produziereZahl(eingabe:String):String
{
	var annehmbareZahl:RegExp=/^(?:3*2\d+)\d*$/;		
	var ausgabe:String="";
	if(annehmbareZahl.test(eingabe)){				
		ausgabe=eingabe.replace(annehmbareZahl,verarbeiteteAnnehmbareZahl);				
	}
	else{
		ausgabe=eingabe + "  ist keine annehmbare Ziffernfolge!";
	};			
	return ausgabe;
}
function verarbeiteteAnnehmbareZahl(...args):String
{
	var zerlegung:RegExp=/^(3+)2(\d+)|2(\d+)/;
	var zahl:String="";
	var arr:Array=zerlegung.exec(args[0]);
	if(arr[1]){
		zahl=arr[2];
		for(var i:int=1;i<=arr[1].length;i++){
			zahl=zahl+"2"+zahl;
		};
	}
	else{
		zahl=arr[3];
	};		
	return zahl;
}

In Zeile 5 wird getestet, ob die Eingabe eine annehmbare Zahl ( gemäss McCulloch's Definition ) ist , oder nicht.  Dem entsprechend  wird dann die annehmbare Zahl mittels der String-Methode "replace" durch die verarbeitete annehmbare Zahl ersetzt und in den Ausgabe-String geschrieben, oder aber es wird eine Rückmeldung in den Ausgabe-String geschrieben, dass die Eingabe keine annehmbare Zahl ist.

Die annehmbareZahl wird durch einen regulären Ausdruck definiert und  damit steht für die annehmbareZahl die Methode "test" zur Verfügung. Dieser Methode wird der Eingabe-String übergeben. Erfüllt der Eingabe-String den regulären Ausdruck "annehmbareZahl", dann liefert sie "wahr" zurück und ansonsten "falsch".

Nachfolgend wird der reguläre Ausdruck "annehmbareZahl" schrittweise aufgebaut.

Ein regulärer Ausdruck in ActionScript 3 wird von zwei Schrägstrichen geklammert:

/<regulärer ausdruck>/

Wesentlich für eine annehmbareZahl ist, wie die Ziffernfolge beginnt. Der Beginn einer Zeichenkette wird in regulären Ausdrücken durch das Caretzeichen  ^ gekennzeichnet. Eine annehmbareZahl beginnt mit einer Gruppe von 0 bis beliebig vielen Dreien. Eine Gruppe wird durch runde Klammern dargestellt und "0 bis beliebig viele" durch ein Sternchen. Das, was "0 bis beliebig oft" direkt hintereinander vorkommen darf, steht vor dem Sternchen, hier also "3".  Gruppen werden standardmässig zwischengespeichert und können deshalb referenziert werden. Leitet man eine  Gruppe, mit "?:" ein, so wird diese nicht zwischengespeichert und kann deshalb nicht referenziert werden. In dieser Weise lassen sich Gruppen gezielt aus der Referenzenliste ausblenden und diese damit kurz halten.

Ob die annehmbareZahl nun mit einer Dreier-Gruppe beginnt oder nicht, in jedem Fall muss die Anfangssequenz einer annehmbaren Zahl mit einer "2" gefolgt von mindestens einer weiteren Ziffer enden. Ein beliebiges Ziffernzeichen wird durch "\d", einer so genannten Meta-Sequenz, dargestellt. "Mindestens eins" wird durch das Plus-Zeichen + dargestellt. Das, was "mindestens einmal" vorkommen muss, steht vor dem Plus-Zeichen.  Damit hat man die für eine annehmbare Zahl erforderliche Anfangs-Sequenz beschrieben:

/^(?:3*2\d+)

Die Anfangs-Sequenz kann damit nur aus Ziffern-Zeichen bestehen; allerdings darf die annehmbareZahl auch nur aus Ziffernzeichen bestehen, also insbesondere darf sie ausschliesslich mit Ziffern enden. Der Anfangs-Sequenz dürfen also bis zum Ende noch "0 bis beliebig viele" weitere Ziffern folgen, also ausdrücklich keine Nicht-Ziffern. Das Ende einer Zeichenkette wird in regulären Ausdrücken durch das Dollarzeichen $ gekennzeichnet. Damit ist der reguläre Ausdruck für eine annehmbare Zahl komplett: Eine reine Ziffernfolge mit einer "2", der mindestens eine weitere Ziffer folgt und der beliebig oft die Ziffer "3" vorangestellt sein kann, aber nicht muss.

/^(?:3*2\d+)2\d*$/

Genau das sagt dieser reguläre Ausdruck aus.

Die String-Methode "replace" erwartet als ersten Parameter einen regulären Ausdruck und als zweiten Parameter entweder einen Ersetzungs-String oder aber eine Funktion, die den Ersetzungs-String liefert. In diesem einfachen Beispiel ist eine Ersetzungs-Funktion eigentlich nicht erforderlich, es wird zu Demonstrations-Zwecken dennoch eine verwendet.

Die Ersetzungs-Funktion hat eine variable Parameter-Liste:

function ersetzungsFunktion(...args):String{ <anweisungs-folge> }

Diese variable Parameter-Liste ist ein Array.  In "args[0]" wird die String-Entsprechung des regulären Ausdrucks des ersten Parameters der String-Methode "replace" übergeben. Im gegebenen Fall ist dies gerade die "annehmbareZahl". Für die Weiterverarbeitung soll die, vom Anfang der Folge gerechnete, der ersten Ziffer "2" folgende Zifferngruppe abgetrennt werden und ebenso die ggf. vorhandene führende Dreier-Gruppe.

Zu diesem Zweck wird ein regulärer Ausdruck "zerlegung" definiert:  Die abzutrennenden Ziffern-Gruppen  werden als "zwischengespeicherte Gruppen" dargestellt. Man kann sich die gespeicherten Gruppen anschaulich als in der Reihenfolge ihres Auftretens im regulären Ausdruck durchnummeriert vorstellen. Die erste Gruppe , hier  (3+), hat die Nummer 1, die nächste die Nummer 2 usw.  Die zwischengespeicherten Gruppen können also, wie weiter oben bereits angedeutet, referenziert werden, nämlich mittels Referenz-Nummern. Tatsächlich ist für die Referenzzählung der Gruppen aber jeweils die öffnende runde Klammer massgeblich, nicht die schliessende! Dadurch ergeben sich mit verschachtelten Gruppen gegenüber der einfachen Durchnummerierung von links nach rechts leicht abweichende Zählmuster! Also: Bitte einfach nur die öffnenden Klammern zählen.

Die beiden ersten gespeicherten Gruppen stehen vor einem Senkrechten Strich | . Dieser senkrechte Strich bedeutet  ODER.  Trifft der links vom ODER-Strich stehende Ausdruck zu, dann wird der rechts davon stehende nicht mehr ausgewertet. Da hier eine "annehmbareZahl" verarbeitet wird, trifft stets genau einer dieser beiden Ausdrücke zu. Das heisst, dass entweder die zwischengespeicherten Gruppen 1 und 2 nicht null sind und 3 ist null, oder aber die zwischengespeicherten Gruppen 1 und 2 sind null und 3 ist nicht null.

Da "zerlegung" als regulärer Ausdruck definiert ist, steht für "zerlegung" die Methode exec() zur Verfügung. Diese erwartet als Parameter einen String, auf den dann der reguläre Ausdruck angewandt wird. In diesem Fall wird args[0] übergeben, also die "annehmbareZahl".  Die Methode exec() liefert eine Referenzenliste als Array zurück. Dieses enthält an der Indexposition 0 die String-Entsprechung des auf den Parameter angewandten regulären Ausdrucks, in diesem Fall wieder die "annehmbareZahl". An der Indexposition 1 steht dann die String-Entsprechung der ersten zwischengespeicherten Gruppe, an Indexposition 2 die der zweiten zwischengespeicherten Gruppe usw.  Die Möglichkeit der Referenzierung zwischengespeicherter Gruppen nennt man "Rückverweis".  Diese Rückverweise werden nun bei der Verarbeitung der annehmbarenZahl angewendet.

An Indexposition 1 der Referenzenliste steht also ein String aus den führenden Dreien der annehmbarenZahl, sofern es eine führende Dreier-Gruppe gibt. Dann aber steht an der Indexposition 2 genau die der ersten Ziffer "2" nachfolgende Ziffern-Gruppe. In einer Schleife wird nun so oft daraus die "assoziative Grösse" gebildet, wie es Dreien in der führenden Dreier-Gruppe gibt, also gerade ensprechend der Länge des Strings an Indexposition 1 .

Gibt es keine führende Dreiergruppe, wenn also der Inhalt an Indexposition 1 == null ist, also auch Indexposition 2 == null,  so braucht lediglich noch die von der ersten Ziffer "2" abgetrennte Ziffern-Gruppe zurück gegeben werden, also gerade der String an Indexposition 3, der in diesem Fall nicht null sein kann.

Schliesslich wird, wie eingangs bereits gesagt, in der aufrufenden replace-Methode die annehmbareZahl durch den gerade zurückgegebenen String ersetzt und das Resultat in den Ausgabe-String geschrieben.