/******************************  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 VerweisBaum
      }
      k.push(b);                                 // lege Verweisbaum 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();
  }
}