Infix - Postfix Konvertierung (arithmetische Ausdrücke auswerten)

    This site uses cookies. By continuing to browse this site, you are agreeing to our use of cookies. More details

    • Infix - Postfix Konvertierung (arithmetische Ausdrücke auswerten)


      Hier ein Rezept, welches Infix - zu Postfix Konvertierung verwendet, um arithmetische Ausdrücke wie ((8+2)*10)/5 auszuwerten.
      Es verwendet dazu den Datentyp Stack. Das Rezept funzt so wie es hier abgebildet ist NICHT bei Zahlen größer 10.
      Das ist hier nur zur Veranschaulichung und kann leicht geändert werden.

      Ein Ausdruck in Postfix wird ausgewertet, indem er von links nach rechts gelesen wird, wobei Operanden auf einen Stack gelegt werden. Wird ein x-stelliger Operator gelesen, werden x Elemente vom Stack entfernt, der Operator auf diese angewendet und das Ergebnis auf den Stack geschoben. Am Ende der Verarbeitung liegt das Gesamtergebnis der Berechnung auf dem Stack. Die Reihenfolge, in der die Operanden vom Stack entnommen werden, ist nicht beliebig. Sie ergibt sich direkt aus der Definition der Umwandlung von Infix-Ausdrücken in die Postfix-Notation. Bei nicht-kommutativen Operatoren kann eine falsche Operandenfolge zu einem falschen Ergebnis führen.

      Mehr Infos gibt es hier : Infix, Postfix, Stack

      Java Source Code

      1. /* ANMERKUNG :
      2. * Das Ganze wird erstmal versucht auszurechnen, tritt dann ein Fehler auf, werden globale Flags gesetzt
      3. * und die Bedingung in der Methode "istKorrektGeklammert" wird nicht erfüllt und der Text
      4. * "Bitte den Ausdruck �berarbeiten!" wird ausgegeben. Treten keine Fehler auf, wird das Ergebnis
      5. * aus einer globalen Variable geholt, welche von den Hilfsmethoden beschrieben wird.
      6. */
      7. package parser;
      8. // Importieren des vordefinierten Java ADTs "Stack" (da ja Stacks verwendet werden sollen)
      9. import java.util.Stack;
      10. public class Parser
      11. {
      12. /**************************************************************************************************
      13. ************************* Postfix ==> Infix Sachen *************************
      14. **************************************************************************************************
      15. */
      16. // Deklarationen
      17. private Stack<Character> charStack = new Stack<Character>(); // Stack zur Umwandlung von Infix-->Postfix
      18. private Stack<Long> LongStack = new Stack<Long>(); // Stack zur Berechnung des Postfix Ausdrucks
      19. private boolean correctEquation = true; // Flag, um falschen Ausdruck für Fehlerausgabe zu kennzeichnen
      20. private boolean DivByZero = false; // Division durch null oder andere Rechenfehler abfangen/kennzeichnen
      21. private StringBuffer Infix = new StringBuffer(); // konvertierter Postfix-Ausdruck
      22. private long result; // das globale Ergebnis (falls keine Fehler aufgetreten sind). Wird der Variablen
      23. // "ergebnis" zugewiesen
      24. // Methoden
      25. /**
      26. * Wandelt einen arithmetischen Ausdruck in eine "Stack-freundliche" Darstellung um
      27. * (aus "((8+7)*2)" mache "87+2*")
      28. * @param a --> char Array mit dem arithmetischen Ausdruck
      29. */
      30. private void InfixToPostfix(char[] a)
      31. {
      32. Infix.delete(0, Infix.length()); // evtl. vorhandene Einträge löschen
      33. correctEquation = true; // evtl. altes vorhandenes Flag zurücksetzen
      34. for (int i = 0; i < a.length; i++)
      35. {
      36. // Operatoren auf Stack legen, Operanden in StringBuffer schreiben
      37. try
      38. {
      39. if (a[i] == ')') // Teil-Ausdruck abeschlossen, hänge Operator an die im Infix stehenden Operanden
      40. {
      41. Infix.append( this.charStack.pop() );
      42. }
      43. if ( (a[i] == '+') || (a[i] == '*') || (a[i] == '-') || (a[i] == '/') )
      44. this.charStack.push(a[i]);
      45. if ((a[i] >= '0') && (a[i] <= '9'))
      46. Infix.append( a[i] );
      47. }catch(Exception e)
      48. {
      49. correctEquation = false; // "Falsche Klammerung"-Flag setzen
      50. }
      51. }
      52. if(!this.charStack.isEmpty()) Infix.append(this.charStack.pop());
      53. }
      54. /**
      55. * Wertet den Postfix auf dem Stack aus und liefert das Ergebnis zurück
      56. * ====================================================================
      57. * ABLAUF:
      58. * Wenn man auf Operator trifft, dann müssen laut Postfix-Notation mindestens 2 Operanden
      59. * auf dem Stack liegen. Wende den jeweiligen Operator auf Operanden an.
      60. * Trifft man auf einen Operanden, lege ihn auf den Stack, damit später bei einem Operator
      61. * ein "pop" ausgeführt werden kann.
      62. * @param a --> char Array mit dem arithmetischen Ausdruck in Postfix Notation
      63. * @return --> void, da Flag-Regelung und globale Variable
      64. */
      65. private void calcPostfix(char[] a)
      66. {
      67. // Deklarationen
      68. long first = 0, second = 0; // Bei "-" und "/" muss Reihenfolge eingehalten werden
      69. result = 0; // evtl. altes vorhandenes Ergebnis zurücksetzen
      70. DivByZero = false; // evtl. altes vorhandenes Flag zurücksetzen
      71. for (int i = 0; i < a.length; i++)
      72. {
      73. try
      74. {
      75. // Operatoren auswerten
      76. if(a[i] == '+')
      77. this.LongStack.push(this.LongStack.pop() + this.LongStack.pop());
      78. if(a[i] == '*')
      79. this.LongStack.push(this.LongStack.pop() * this.LongStack.pop());
      80. if(a[i] == '-')
      81. {first = this.LongStack.pop(); second = this.LongStack.pop(); this.LongStack.push(second - first);}
      82. if(a[i] == '/')
      83. {first = this.LongStack.pop(); second = this.LongStack.pop(); this.LongStack.push( (long)(second / first) );}
      84. // Operanden auswerten
      85. if ((a[i] >= '0') && (a[i] <= '9'))
      86. this.LongStack.push((long)(0));
      87. if((a[i] >= '0') && (a[i] <= '9'))
      88. this.LongStack.push(10*this.LongStack.pop() + (a[i]-'0'));
      89. }catch(Exception e) // z.B. "div / 0"
      90. {
      91. DivByZero = true; // "Rechenfehler"-Flag setzen
      92. break;
      93. }
      94. }
      95. // Ergebnis vom Stack holen (falls kein Fehler auftrat, also das Flag nicht gesetzt ist)
      96. if(!DivByZero) result = this.LongStack.pop();
      97. }
      98. //-------------------------------------------------------------------------------------------------
      99. /**************************************************************************************************
      100. ************************* Standardrahmen *************************
      101. **************************************************************************************************
      102. */
      103. boolean istKorrektGeklammert(String input)
      104. {
      105. // Deklarationen
      106. char[] a = input.toCharArray(); // Array, welches zum auswerten der Methode übergeben wird
      107. this.InfixToPostfix(a); // Infix zu Postfix konvertieren
      108. this.calcPostfix(this.Infix.toString().toCharArray()); // Rufe Hilfsmethode zur Postfix Auswertung auf
      109. // Auf Klammer-,Divisions- oder andere Rechenfehler prüfen)
      110. if( (correctEquation) && (!DivByZero) )
      111. return true; // falls Ausdruck korrekt und Rechnung fehlerfrei, gib true zurück, ansonsten false
      112. else
      113. return false;
      114. }
      115. String parse(String input)
      116. {
      117. if (istKorrektGeklammert(input))
      118. {
      119. long ergebnis=0;
      120. // Falls keine Flags gesetzt, hole das Ergebnis aus der globalen Variable "result"
      121. ergebnis = this.result;
      122. return Long.toString(ergebnis); // Ausgabe
      123. }else
      124. {
      125. return "Bitte den Ausdruck �berarbeiten!";
      126. }
      127. }
      128. public static void main(String[] args)
      129. {
      130. Parser p=new Parser();
      131. System.out.println(p.parse("((8+7)*2)")); // sollte 30 ausgeben
      132. System.out.println(p.parse("(8+(7-1))")); // sollte 14 ausgeben
      133. System.out.println(p.parse(")8+)1(())")); // sollte "Bitte den Ausdruck überarbeiten!" ausgeben
      134. System.out.println(p.parse("(8+())")); // sollte "Bitte den Ausdruck überarbeiten!" ausgeben
      135. System.out.println(p.parse("(8/(7-7))")); // sollte "Bitte den Ausdruck überarbeiten!" ausgeben
      136. }
      137. }
      Display All