/* Paren.java:
 * grammar:
 *   P ---> E '$'
 *   E ---> T {('+'|'-') T}
 *   T ---> S {('*'|'/') S}
 *   S ---> F '^' S | F
 *   F ---> char | '(' E ')'
 */
public class ParenLisp {
   private GetNext getChar = new GetNext();
   private char next;

   public String P() {
      String res;
      scan();
      res = E();
      if (next != '$') return "ERROR";
      else return res;
   }

   private String E() {
      String res;
      char save;
      res = T();
      while (next == '+' || next == '-') {
         save = next;
         scan();
         res = "(" + save + " " + res + " " + T() + ")";
      }
      return res;
   }

   private String T() {
      String res;
      char save;
      res = S();
      while (next == '*' || next == '/') {
         save = next;
         scan();
         res = "(" + save + " " + res + " " + S() + ")";
      }
      return res;
   }

   private String S() {
      String res;
      res = F();
      if (next == '^') {
         scan();
         res = "(" + "^ " + res + " " + S() + ")";
      }
      return res;
   }

   private String F() {
      String res = "";
      if (Character.isLetterOrDigit(next)) {
         res = next + "";
         scan();
      }
      else if (next == '(') {
         scan();
         res = E();
         if (next == ')') {
            scan();
         }
         else {
            error(2);
            res = "ERROR";
         }
      }
      else {
         error(3);
         res = "ERROR";
      }
      return res;
   }

   private void scan() {
      while (Character.isWhitespace(next = 
             getChar.getNextChar()))
         ;
   }

   private void error(int n) {
      System.out.println("*** ERROR: " + n);
      System.exit(1);
   }

   public static void main(String[] args) {
      ParenLisp.java paren = new ParenLisp.java();
      String res = paren.P();
      System.out.println(res);
   }
}
% javac GetNext.java
% javac ParenLisp.java
% java Paren
1 + 2 * 3 $
(+ 1 (* 2 3))
% java Paren
(1 + (2 * 3) )$
(+ 1 (* 2 3))
% java Paren
1*(2+3)$
(* 1 (+ 2 3))
% java Paren
1+2+3+4$
(+ (+ (+ 1 2) 3) 4)
% java Paren
3^2^2^2$
(^ 3 (^ 2 (^ 2 2)))
% java Paren
7$
7
% java Paren
( ( ( ( 7 + ((4)) ) ) ) ) $
(+ 7 4)
% java Paren
(3*(2+4)/(5+1))-2$
(- (/ (* 3 (+ 2 4)) (+ 5 1)) 2)
% java Paren
(5+3)^(2+1)^2$
(^ (+ 5 3) (^ (+ 2 1) 2))
% java Paren
2+3*4^5*6+7$
(+ (+ 2 (* (* 3 (^ 4 5)) 6)) 7)
% java Paren
((3^2-4*1*2)^(1/2)-3)/(2*1)$
(/ (- (^ (- (^ 3 2) (* (* 4 1) 2)) (/ 1 2)) 3) (* 2 1))