Postfix-notation-Validierung?

Was wäre ein guter Weg, um bewerten zu string(array, etwas) enthält, die einen postfix-Ausdruck(ex: 3 5 +), um die Gültigkeit überprüfen?

  • Bitte genauer, was du meinst, von 'gültig' oder 'ungültig', vielleicht mit Beispielen.
InformationsquelleAutor | 2009-04-25
  1. 13

    Gehe ich davon aus, dass hier, was meinst du gültig ist, dass die Ausführung des code wird nie Unterlauf stack und verlassen ein einziger Wert auf dem stack. Wenn Sie einen strengeren Begriff der Gültigkeit, müssen Sie eine mehr anspruchsvolle checker.

    Wenn Sie möchten, zu prüfen, diese Art von Gültigkeit, es ist nicht notwendig, um zu bewerten die Zeichenfolge, und Sie können verwenden Sie einen Zähler, kein stack. Der Zähler verfolgt die Anzahl der Werte, die wäre auf den Stapel, wenn Sie ausgewertet. Zur Vereinfachung, nehmen wir an, Sie haben nur Literale, binäre Operatoren, und unäre Operatoren. Dieser Algorithmus verwendet eine spezielle Dekrement Betrieb: wenn Sie den Dekrement-Zähler, der geht unter null, ist der string ungültig ist:

    1. Initialisieren Sie den Zähler auf 0.
    2. Wenn Sie sehen, ein literal, Inkrementieren Sie den Zähler.
    3. Wenn Sie sehen, ein binärer operator Dekrementieren der Zähler zweimal, dann erhöht es.
    4. Wenn Sie sehen, ein unärer operator dekrementiert den Zähler, dann erhöht es.
    5. Am Ende der Zeichenfolge, wenn der Zähler 1 ist, und wenn es ging nie unter 0, wird die Zeichenfolge gültig ist.
    • So, nach Ihren Vorgaben, in jeder Alternative-literal, der Zähler sollte verringert werden, zweimal und dann erhöht? Ich Frage deshalb, weil ich nicht ganz, Sie zu erhalten.
    • Ich denke, du meintest "unärer operator" in Punkt #4.
    • Beachten Sie, dass bei Schritt 3 und 4 wird der Zähler wieder um eins erniedrigt und dann erhöht. Dies ist für einen Grund. Sie haben zu prüfen, ob der Zähler ging unter 0, nachdem jedes mal, wenn ein Zähler wurde um eins verringert. Ansonsten ist es möglich, zu überprüfen ungültig RPN, z.B.: [2, +, 2] wäre gültig.
    InformationsquelleAutor Norman Ramsey
  2. 1

    Algorithmus: pflegen einen Stapel zu Scannen und die
    postfix-Ausdruck von Links nach rechts
    – Wenn das element eine Zahl ist, drücken Sie ihn in die
    stack
    – Wenn das element ein operator O, pop-zweimal
    und erhalten A und B jeweils. Berechnen
    BOA, und schieben Sie es wieder auf den Stapel
    – Wenn der Ausdruck beendet ist, wird die Anzahl
    in dem Stapel ist die Letzte Antwort

    //Für Gültigkeit, Wenn Sie mit der linken sind nur eine Zahl im Stack seine richtige Ausdruck

    //Wenn Sie Links mit mehr als einer Nummer in der stack-und kein Betreiber dann seine falschen

    //Wenn Sie eine oder keine Zahl im stack und Betreiber Links, dann seine falschen

    InformationsquelleAutor insanely_sin
  3. 1

    Einen postfix-Ausdruck ist gültig, wenn und nur wenn:

    1) Die ersten zwei Elemente sind die Operanden(Werte), und

    2) Das Letzte element ist ein operator, und

    3) Für jedes n die Werte n-1 operator(s), und

    4) In einer Liste von n Elementen, beginnend mit index i = 0 für i < n-1 (die zweite letzten element), jede Gruppe von Elementen, bestehend aus k-Werten( k > 1 ) folgt (k-1) Betreiber. Wenn k = 1, die Anzahl der Operatoren, folgt = k = 1.

    InformationsquelleAutor Yoshi
  4. 0

    Zu prüfen, ob ein postfix-Ausdruck gültig ist oder nicht:(wenn Eingabe in char-array)
    1.Anzahl der Operanden müssen gleich keine. der Operatoren + 1.
    Um dies zu überprüfen, kontrollieren variable.
    check=0. Erhöhen Sie diesen für jeden Operanden-und Dekrement-für jeden Betreiber.Wenn schließlich der Wert ist 1,dann-Ausdruck gültig ist.

    2.Die ersten 2 Elemente des Arrays werden müssen Operanden.Kein postfix-Ausdruck operator als 1. oder 2. element.
    Überprüfen Sie dies durch eine if-Anweisung.

    InformationsquelleAutor Neel Kapadia
Schreibe einen Kommentar