/******************************  PostfixBaumBau.java  *************************/

import AlgoTools.IO;

/** Klasse PostfixBaumBau enthaelt statische Methode postfixBaumBau, 
 *  die einen Postfix-Ausdruck uebergeben bekommt 
 *  und den zugehoerigen Baum zurueckliefert.
 *  Verwendet wird ein Keller ueber Baeumen. 
 */

public class PostfixBaumBau {

  public static Baum postfixBaumBau (char[]ausdruck) { // konstruiert Baum 

    VerweisBaum b, l, r;                          // Baeume
    Object x;                                     // Objekt
    char c;                                       // Zeichen

    Keller k = new VerweisKeller();               // Keller

    for (int i=0; i < ausdruck.length; i++) {     // durchlaufe Postfix-Ausdruck
      
      c = ausdruck[i];                            // besorge naechstes Zeichen
      x = new Character(c);                       // erzeuge Objekt
    
      if (c!='+' && c!='-' && c!='*' && c!='/')   // falls c ein Operand ist
        b = new VerweisBaum(x);                   // erzeuge Blatt
      else {                                      // ansonsten ist c Operator
        r = (VerweisBaum)k.top(); k.pop();        // besorge rechten Sohn
        l = (VerweisBaum)k.top(); k.pop();        // besorge linken Sohn
        b = new VerweisBaum(l,x,r);               // erzeuge Baum
      }
      k.push(b);                                  // lege Baum auf Keller
    }
    return (Baum)k.top();                         // gib Ergebnisbaum zurueck
  }

  public static void main (String [] argv) {
    char [] zeile = IO.readChars("Bitte Postfix-Ausdruck: ");  // lies Postfix
    Baum wurzel = postfixBaumBau(zeile);          // konstruiere daraus Baum
    IO.print("Inorder lautet:         ");         // kuendige Traversierung an 
    Traverse.klammerinorder(wurzel);              // gib in Klammer-Inorder aus
    IO.println();
  }
}