/*
 * Recursive descent expression parsing.  Expression being parsed is
 * passed in the command line or entered by the user.  This supports
 * the operators "+ -" | "* /" | "^"
 *
 * Note that the command-line entry must be enclosed in quotation
 * marks (or else the symbol ^ disappears).
 *
 * Author:  Timothy Rolfe
 */
public class InfixPostfix
{  static String input;
   static int    current = 0;

   public static void main ( String[] args )
   {  String postfix;

      if ( args.length == 0 )
      {  java.util.Scanner console = new java.util.Scanner (System.in);
         System.out.print ("Enter the expression:  ");
         input = console.nextLine();
      }
      else
      {  input = args[0];
         System.out.println("Expression:  " + input + '\n');
      }

      postfix = expr();
      System.out.println("Equivalent postfix expression:  " + postfix);
   }

   // expr == term | expr+term | expr-term
   static String expr()
   {  char nxt;
      String result = term();       // first part of the postfix expression

      if ( current >= input.length() )
         return result;
   // Note:  while loop gives left associativity
      nxt  = input.charAt(current);
   // If next token in + -, treat result as expr, not term
      while ( nxt == '+' | nxt == '-' )
      {  current++;               // Advance to next token in input
         result += term() + nxt;  // Concat. right operand and operator
         if ( current >= input.length() )
            break;
         nxt  = input.charAt(current);
      }
      return result;
   }

   // term == factor | term*factor | term/factor
   static String term()
   {  char nxt;
      String result = factor();

      if ( current >= input.length() )
         return result;
   // Note:  while loop gives left associativity
      nxt  = input.charAt(current);
   // If next token in "*/", treat current as term, not factor
      while ( nxt == '*' | nxt == '/' )
      {  current++;          // Advance to next token in input
         result += factor() + nxt;
         if ( current >= input.length() )
            break;
         nxt  = input.charAt(current);
      }
      return result;
   }

   // factor == primary | primary^factor
   static String factor()
   {  char nxt;
      String result = primary();    // first part of the postfix expression

      if ( current >= input.length() )
         return result;
      nxt  = input.charAt(current);
      if ( nxt == '^' )
      {  current++;               // Advance to next token in input
         result += factor() + nxt;// Concat. right operand and operator
      }
      return result;
   }

   // primary == variable | (expr)  [variable processed as a letter]
   static String primary()
   {  char nxt;
      String result;

      if ( current >= input.length() )
         throw new RuntimeException("End of expr:  " + input);
      nxt = input.charAt(current++);     // ALWAYS consume a character
      if ( nxt == '(' )
      {  result = expr();
         if ( current >= input.length() )
            throw new RuntimeException("No close paren in " + input);
         nxt = input.charAt(current++);
         if ( nxt != ')' )
            throw new RuntimeException("No close paren in " + input);
      }
      else if ( Character.isLetter(nxt) )
         result = Character.toString(nxt);
      else
         throw new RuntimeException (nxt + " is illegal in " + input);
      return result;
   }
}