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

    Baum b;                                       // Hilfsbaum
    char c;                                       // Zeichen

    Keller k = new VerweisKeller();               // konstruiere einen Keller

    for (int i=0; i < ausdruck.length; i++) {     // durchlaufe Postfix-Ausdruck
      
      c = ausdruck[i];                            // besorge naechstes Zeichen
      b = new VerweisBaum();                      // erzeuge leeren Baum
      b.setValue(new Character(c));               // mache daraus ein Blatt
    
      if (c=='+' || c=='-' || c=='*'|| c=='/'){   // falls c ein Operator ist

        b.setRight((Baum)k.top()); k.pop();       // haenge rechten Sohn ein
        b.setLeft ((Baum)k.top()); k.pop();       // haenge linken Sohn ein
      
      }

      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();
  }
}