/*****************************  Postfix.java  *********************************/

import AlgoTools.IO;

/** Wandelt Infix-Ausdruck in Postfix-Ausdruck um.
 *  Vorausgesetzt wird eine syntaktisch korrekte Eingabe, 
 *  bestehend aus den Operatoren +,-,*,/ sowie den Operanden a,b,...,z
 *  und den oeffnenden und schliessenden Klammern. Beispiel:(a+b)*c-d/f
 *  Ausgabe ist der aequivalente Postfixausdruck.  Beispiel: ab+c*df/-
 *  Verwendet wird ein Character-Keller, der die bereits gelesenen
 *  oeffnenden Klammern sowie die Operatoren speichert.
 */

public class Postfix {

  public static void main(String[] argv) {

    CharKeller k = new CharKeller();                  // Character-Keller
    char[] infix;                                     // Eingabezeile
    char c;                                           // aktuelles Zeichen

    infix = IO.readChars("Bitte Infix-Ausdruck (+,-,*,/,a,...,z): ");
    IO.print("umgewandelt in Postfix:                 ");

    for (int i=0; i<infix.length; i++) {              // durchlaufe Infixstring

        c = infix[i];                                 // aktuelles Zeichen 
        switch (c) {

            case '('  :  k.push(c);                   // '(' auf den Stack
                         break;


            case ')'  :  while ( k.ctop() != '(' ) {  // Keller bis vor '('
                             IO.print(k.ctop());      // ausgeben
                             k.pop();                 // und leeren 
                         } 
                         k.pop();                     // und '(' entfernen 
                         break;                


            case '+'  :
            case '-'  :  while (!k.empty()            // Keller bis vor erste
                                && k.ctop() != '(') { // oeffnende Klammer
                             IO.print(k.ctop());      // ausgeben
                             k.pop();                 // und leeren
                         } 
                         k.push(c);                   // lege letztes Zeichen ab
                         break;

 
            case '*'  : 
            case '/'  :  if (!k.empty()               // solange Keller
                             && (k.ctop()=='*'        // * enthaelt
                             || k.ctop()=='/')) {     // oder / enthaelt
                                 IO.print(k.ctop());  // gib Operator aus
                                 k.pop();             // und entferne ihn
                         } 
                         k.push(c);                   // lege letztes Zeichen ab
                         break;
                              

            default   :  if (c>='a' && c<='z')        // falls Operand vorliegt 
                             IO.print(c);             // direkt ausgeben 
        }
    }

    while (!k.empty()) {                              // beim Eingabeende    
        IO.print(k.ctop());                           // Keller ausgeben
        k.pop();                                      // und leeren
    } 
    IO.println();
  }
}