Implementierung von Instanzparsing-Java-Infix-Ausdrücken

Dieser Artikel vermittelt Ihnen relevantes Wissen über Java, das hauptsächlich den Infix-Ausdruck als allgemeine Ausdrucksmethode für arithmetische oder logische Formeln vorstellt. Infix-Ausdrücke können von Computern nicht einfach analysiert werden, werden jedoch dennoch von vielen Programmiersprachen verwendet, da sie dem allgemeinen menschlichen Sprachgebrauch entsprechen. Schauen wir es uns gemeinsam an, ich hoffe, es wird für alle hilfreich sein.

Empfohlenes Lernen: „Java-Video-Tutorial“

1. Konzept

Was ist ein Infix-Ausdruck und was ist ein Suffix-Ausdruck?

Die vier Rechenoperationen, die Sie seit der Grundschule gelernt haben, zum Beispiel: 3+( 5*(2+3)+7) Ein Ausdruck wie dieser ist ein Infix-Ausdruck. Infix-Ausdrücke sind für das menschliche Gehirn leicht zu verstehen, und die Priorität jedes Operators ist für das menschliche Gehirn auch leicht zu beurteilen. Berechnen Sie zuerst die Einsen in Klammern, dann *, dann +, -

, aber diese Art von Ausdruck ist es Sehr ungünstig für Computer. Konvertieren Sie den Präfixausdruck auf irgendeine Weise in einen Suffixausdruck, um die Computerberechnung zu erleichtern. Der Suffixausdruck von 3+(5*(2+3)+7) ist beispielsweise 3,5,2. 3,+,* ,7,+, +. Dieser Ausdruck ist für Computer leicht zu berechnen. Durch Algorithmusablauf 2 erhalten Sie ein tiefgreifendes Verständnis.

2. Algorithmusprozess

Wie konvertiert man beispielsweise einen Infix-Ausdruck in einen Postfix-Ausdruck?

Operatorpriorität:

• +, - ist kleiner als *, /
• + ist gleich -
• * ist gleich /

Linke Klammern und rechte Klammern werden als spezielle Operatoren behandelt. (Wenn Sie auf „(“ stoßen, müssen Sie die Priorität nicht beurteilen und direkt zum Operatorstapel wechseln. Wenn Sie auf „)“ stoßen, müssen Sie die Priorität nicht beurteilen und verlassen den Operator direkt Stapel)

Der grobe Algorithmus beherrscht die folgenden Prozesse:

Bereiten Sie zwei Stapel vor, einer ist der Zahlenstapel A, der andere ist der Operatorstapel (+,-,*,/(,))B usw.

1.0 Wenn beim Zahlenstapel A eine Zahl angetroffen wird, wird diese direkt in den Stapel A verschoben.

2.0 Für den Operatorstapel B gibt es mehrere Situationen.

2.1 Wenn Sie auf den Operator „(“ stoßen, schieben Sie ihn direkt auf den Stapel.

2.2 Wenn Sie auf den Operator „)“ stoßen, öffnen Sie so lange den Operatorstapel B, bis er auftrifft. )'. (Schieben Sie die Popup-Operatoren zwischen „(“ und „)“ nacheinander in Stapel A.)

2.3 Wenn Sie auf „+,-,*/“ stoßen, vergleichen Sie das aktuelle Element (vorausgesetzt, das aktuelle Element ist aktuell) mit der Operation auf dem top of stack B Die Priorität des Symbols (vorausgesetzt, das oberste Element des Stacks ist top). Schleife und Strom werden auf den Stapel verschoben A

Folgen Sie dem obigen Algorithmus, um den Prozess von 3+(5*(2+) von 3)+7 zu demonstrieren):

1, wenn es auf 3 trifft, geht 3 in Stapel A [3,]

2, wenn es Trifft es auf +, geht es in Stapel B [+,]

3, wenn es auf ( trifft, geht es auf Stapel B [ +,(]

4, wenn es auf 5 trifft, schiebe es in Stapel A [3,5]

5, Bei Begegnung mit * ist die Priorität von * größer als (, in Stapel B schieben [+,(,*]

6, bei Begegnung mit (, Gehe zu Stapel B [+,(,*,(]

7, Begegnung 2, gehe zu Stapel A [3,5,2]
8, begegne +, gehe zu Stapel B [+,(,*,(,+]
9, wenn du auf 3 triffst, schiebe es in Stapel A [3,5,2 ,3]
10, wenn Sie auf ) stoßen, öffnen Sie Stapel B, gehen Sie direkt zu „(“ und legen Sie den gepoppten Operator in Stapel A ab. B:[ +, (,*] A:[3,5,2,3 ,+]
11, wenn auf + gestoßen wird, ist die Priorität von + kleiner als die des obersten Elements * von B, also reißt * den Stapel von B ab, legt ihn in A und legt + in B ein. B:[ +,(, +] A:[3,5,2,3,+,*]
12, Begegnung 7, in Stapel legen A [3,5,2,3,+,*,7 ]
13, bei Begegnung), Pop Gehen Sie im B-Stapel direkt zu „(“ und legen Sie den entfernten Operator in den A-Stapel ein. B:[ +] A:[3,5,2,3,+,*,7,+ ]
14, scannen Sie die gesamte Zeichenfolge und bestimmen Sie, ob B leer ist. Wenn es nicht leer ist, fügen Sie das Element des B-Stapels in A ein. Es ist derzeit nicht leer, daher ist das letzte Element des A-Stapels A:[3,5,2, 3,+ ,*,7,+, +]


Der endgültige Suffixausdruck von A ist also 3,5,2,3,+,*,7,+, +

Wie wird der Computer berechnen, wenn er das erhält? Der Vorgang ist wie folgt:

Wenn eine Zahl gefunden wird, wird sie direkt in den Stapel verschoben. Wenn sie auf einen Operator trifft, werden die beiden obersten Elemente des Stapels direkt angezeigt, über den Operator berechnet und verschoben Ergebnis auf den Stapel.

Berechnet durch die Schleife der Schritte 1 und 2, und schließlich wird es nur ein Element im Stapel geben, und dies ist das Ergebnis des Ausdrucks

Üben wir es:
• 1, wann Wenn Sie auf die Zahlen 3,5,2,3 stoßen, schieben Sie sie direkt in den Stapel A[3,5,2,3]. Die Summe ist 5. Schieben Sie A[3,5,5] auf den Stapel
3. Wenn * angetroffen wird, werden 5 und 5 von der Oberseite des Stapels angezeigt, und die Summe ist 25. Schieben Sie A[3,25]

4, wenn Sie auf 7 stoßen, schieben Sie es direkt in den Stapel A[3,25,7]

5, wenn Sie auf + stoßen, öffnen Sie die Oberseite des Stapels 25,7, addieren Sie 32, schieben Sie es in den Stapel A[3, 32]

6 Wenn + angetroffen wird, öffnen Sie die obersten 3 und 32 des Stapels und addieren Sie sie zu 35. Drücken Sie A[35]

Aus dem Obigen können wir erkennen, dass der Computer leicht zu berechnen ist. und das Ergebnis kann durch Scannen von links nach rechts erhalten werden. 3-Code-Implementierung

//优先级
bool cmpPriority(char top, char cur)//比较当前字符与栈顶字符的优先级，若栈顶高，返回true
{
	if ((top == '+' || top == '-') && (cur == '+' || cur == '-'))
		return true;
	if ((top == '*' || top == '/') && (cur == '+' || cur == '-' || top == '*' || top == '/'))
		return true;
	if (cur == ')')
		return true;
	return false;
}

basierend auf dem Betreiber. Empfohlenes Lernen: „
Java-Video-Tutorial
“

Das obige ist der detaillierte Inhalt vonImplementierung von Instanzparsing-Java-Infix-Ausdrücken. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!