Schreiben Sie ein Programm zum Suchen nach doppelten Klammern in einem Ausdruck. Zum Beispiel:
%Vor%Ein mir bekannter Ansatz beinhaltet die folgenden zwei Schritte:
Ich möchte nicht den gesamten Vorgang der Konvertierung von einer Darstellung in eine andere durchführen und sie dann zurück konvertieren.
Ich möchte das mit Stapeln machen, aber in einem einzigen Durchgang. Ist es möglich?
Bitte schlagen Sie einen Algorithmus vor oder teilen Sie den Code.
Sie können einen rekursiven Abstiegsparser verwenden. Dies verwendet den Funktionsaufrufstapel implizit, aber nicht explizit einen Java-Stack. Es kann wie folgt implementiert werden:
%Vor% Wenn Sie einen expliziten Stapel verwenden möchten, können Sie den Algorithmus von einem rekursiven in einen iterativen Algorithmus umwandeln, indem Sie einen Stapel ähnlich der inneren Klasse Result verwenden.
Tatsächlich konvertiert der Java-Compiler / JVM jeden rekursiven Algorithmus in einen stackbasierten Algorithmus, der die lokalen Variablen auf einen Stack setzt.
Aber rekursive anständige Parser sind für Menschen leicht lesbar, daher würde ich die oben dargestellte Lösung bevorzugen.
Wenn Sie sich nur für doppelte Klammern interessieren (wie die Frage zu implizieren scheint) und nicht für diejenigen, die aufgrund der Vorrangstellung des Bedieners als notwendig erachtet werden (wie die anderen Antworten zu sagen scheinen), können Sie tatsächlich einen Stapel verwenden Verfolgen Sie, welche Klammern Sie gefunden haben, und entscheiden Sie, dass alle Nicht-Leerzeichen-Zeichen für jedes Klammerpaar von Bedeutung sind, wodurch Sie ein viel einfacheres iteratives Traversal mit einem Stapel erhalten:
%Vor%Was Sie mit dem folgenden
testen können %Vor%Habe es nicht programmiert, aber es könnte so aussehen:
geben Sie den Operationen + / - den Wert 1 geben Sie die Operationen * & amp; / der Wert 2 geben Sie die Operation) (der Wert 2 (wie das gleiche wie *)
%Vor%Sie sind fertig, wenn zwischen zwei Schritten keine Änderungen vorgenommen werden
hoffe das hat geholfen .. Wenn Sie eine Lösung haben, lassen Sie es mich bitte wissen. Wenn das nicht geholfen hat, lass es mich auch wissen:)
Grüße
Es ist in einem Durchgang möglich. Die Idee besteht darin, nach einer vorherigen / nächsten Operation um jeden () -Block zu suchen und Assoziationsregeln anzuwenden. Hier ist eine kleine Tabelle mit Ja / Nein-Markierungen, wenn () notwendig ist.
%Vor%Hier ist C ++ - Code (ich bin mir nicht sicher, ob es einige Fälle nicht vermisst - es ist nur eine Idee):
%Vor%Innerhalb jedes Blocks verfolgen wir die letzte Operation und verfolgen auch, ob der Inhalt zusammengesetzt ist (a + b * c).
Test:
%Vor%Ergebnis:
%Vor%Ich persönlich denke, es gibt mindestens zwei Möglichkeiten:
Baum
Aus dem Eingabeausdruck kann ein Baum erstellt werden. Nachdem der Baum erstellt wurde, kann er ohne die unnötigen Klammern
abgeflacht werdenPolnische Schreibweise
(( a + b ) + (( c + d ))) wird (+ (+ a b) (+ c d))
(( a + b ) * (( c + d ))) wird (* (+ a b) (+ c d))
Von hier aus können Sie die einzelnen Operanden und die Faktoren vergleichen, um zu sehen, ob sie die gleiche Priorität bei der Lösung der arithmetischen Gleichung haben
Ich würde mit dem Baum gehen.
Tags und Links java stack data-structures