import java.util.*;
/**
 * Transforme une expression arithmétique en notation postfixe (notation
 * dite polonaise inverse) en notation infixe (notation usuelle).
 * Le principe est que dans la pile on représente e1 op e2 sous la forme
 * e1,e2,op, par conséquent on commence par dépiler quelque chose.
 * S'il s'agit d'un opérateur ce que l'on devra dépiler c'est toute
 * l'expression à droite PUIS toute l'expression à gauche...
 *
 * Pour la conversion inverse, j'empile l'expression infixe mais du
 * coup lorsqu'on retire les éléments de la pile ils sont inversés
 * e1 op e2 est empilé mais on le dépile en retirant d'abord e2, puis
 * l'opérateur, puis e1...
 *
 * Pour d'autres détails on peut se reporter à la page Wikipédia sur la 
 * "polonaise inverse".
 * @author JBY
 */
public class TD4EX4 {
  /**
   * Convertit une pile polonaise inverse en chaîne de caractères représentant
   * la même expression en notation infixe...
   */
  public static String convertPostfixToInfix(Stack<String> pile) {
    // System.out.println(pile); // debug!
    if (pile.empty()) return "";
    String e = pile.pop();
    char c = e.charAt(0);
    if (c=='*' || c=='/' || c=='+' || c=='-') { // c'est un opérateur!!!
      String aDroite = convertPostfixToInfix(pile); // Allez on extrait la partie droite
      String aGauche = convertPostfixToInfix(pile); // puis la partie gauche
      return "( "+aGauche+" "+e+" "+aDroite+" )"; // On recombine le tout en infixe
    } else { // c'est un nombre alors...c'est facile non ?
      return e;
    }
  }
  public static String convertInfixToPrefix(String s) {
    StringTokenizer in = new StringTokenizer(s);
    Stack<Character> pile = new Stack<Character>();
    StringBuffer exp = new StringBuffer();
    while (in.hasMoreTokens()) {
      String e = in.nextToken();
      char c = e.charAt(0);
      if (c=='(') {
        pile.push(c);
        continue;
      }
      if (c==')') { // il faut dépiler jusqu'à l'ouvrante...
        while ((c=pile.pop())!='(') {
          if (exp.length()!=0) exp.append(" "); // un espace au bon endroit
          exp.append(c);            
        }
       continue;
      }
      if (c=='+' || c=='-' || c=='*' || c=='/') { // c'est un opérateur
        while (!pile.empty()) { // il faut examiner la pile...
          char t = pile.peek();
          // si l'opérateur lu est prioritaire on doit l'empiler et continuer
          // la lecture
          if (t=='(' || ((t=='+' || t=='-') && (c=='*' || c=='/'))) break;
          // sinon il faut sortir les opérateurs stockés
          if (exp.length()!=0) exp.append(" "); // un espace au bon endroit
          exp.append(pile.pop());
        }
        pile.push(c); // on empile l'opérateur en attendant la partie droite
        continue;
      }
      // Les valeurs sont toujours sorties (dans l'ordre d'apparition)
      if (exp.length()!=0) exp.append(" "); // un espace au bon endroit
      exp.append(e);
    }
    // On vide la pile de tous les opérateurs qui restaient...
    while (!pile.empty()) {
        if (exp.length()!=0) exp.append(" ");
        exp.append(pile.pop());
    }
    return exp.toString();
  }
  public static void main(String []args) {
    String exp = "4 1 x 17 + + 3 4 * / +";
    StringTokenizer in = new StringTokenizer(exp);
    Stack<String> pile = new Stack<String>();
    while (in.hasMoreTokens()) { // Tant qu'il y a quelque chose à lire
      pile.push(in.nextToken());
    }
    // System.out.println(pile); // debug!!
    String resultat = convertPostfixToInfix(pile);
    System.out.println(exp+" =====> "+resultat);

    String exp2 = resultat; // "( ( a + b ) ) * c - d"; // test
    String resultat2 = convertInfixToPrefix(exp2);
    System.out.println(exp2+" =====> "+resultat2);
  }
}