/******************************  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 {

  private static boolean is_operator(char c) {    // liefert true, 
    return (c=='+' || c=='-' || c=='*' || c=='/');// falls c ein Operator ist
  } 

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

    VerweisBaum l, r;                             // Hilfsbaeume
    char c;                                       // aktuelles Zeichen
 
    Keller k = new VerweisKeller();               // konstruiere einen Keller

    for (int i=0; i < ausdruck.length; i++) {     // durchlaufe Postfix-Ausdruck
        
      c = ausdruck[i];                            // aktuelles Zeichen
        
      if (!is_operator(c))                        // falls Operand,
        k.push(new VerweisBaum(new Character(c)));// lege als Baum auf Keller
      else {                                      // falls Operator,
        r = (VerweisBaum)k.top(); k.pop();        // hole rechten Sohn
        l = (VerweisBaum)k.top(); k.pop();        // hole linken Sohn 
        k.push(new VerweisBaum (l,                // konstruiere daraus
                                new Character(c), // einen VerweisBaum und lege
                                r));              // ihn auf den Keller 
      }
    }
    return (Baum)k.top();                         // gib Baum im Keller 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();
  }
}