CS 3723
 Programming Languages 
   Fully Parenthesize  
   Arithmetic Expressions  

The Programs: Below are two programs:
  1. Copy.java: Copies the input exactly, removing all whitespace.

  2. Parens.java: Inputs an arithmetic expression and writes an equivalent arithmetic expression which is fully parenthesized and has no redundant parentheses.

The Copy program is transformed to the Parens with very simple changes to five lines, two of them deleting stuff, and three of them with small additions.

The programs below also use a GetChar class that can be found at the end of the page R-D Parser for Arith Expr.

Copy.java Parens.java
class Copy {
   private GetNext getChar = new GetNext();
   private char next;

   private 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 = res + save + T();
      }
      return res;
   }

   private String T() {
      String res;
      char save;
      res = S();
      while (next == '*' || next == '/') {
         save = next;
         scan();
         res = res + save + 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.isLetter(next)) {
         res = next + "";
         scan();
      }
      else if (next == '(') {
         scan();
         res = "(" + E();
         if (next == ')') {
            res = res + ")";
            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) {
      Copy copy = new Copy();
      String res = copy.P();
      System.out.println(res);
   }
}

class Parens {
   private GetNext getChar = new GetNext();
   private char next;

   private 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 = "(" + res + save + T() + ")";
      }
      return res;
   }

   private String T() {
      String res;
      char save;
      res = S();
      while (next == '*' || next == '/') {
         save = next;
         scan();
         res = "(" + res + save + 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.isLetter(next)) {
         res = next + "";
         scan();
      }
      else if (next == '(') {
         scan();
         res = E(); // "(" + missing
         if (next == ')') {
            // res = res + ")"; missing
            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) {
      Parens parens = new Parens();
      String res = parens.P();
      System.out.println(res);
   }
}

Input Output of Parens.java
a + b * c ^ d $
 
(a+(b*(c^d)))$
( ( ( a + b ) * c ) ^ d ) $
 
(((a+b)*c)^d)$ 
((( a )) + (((b * ( c ^ d))) ))$
 
(a+(b*(c^d)))$ 
(a + b*c)^(d/e - f)*g$
 
(((a+(b*c))^((d/e)-f))*g)$ 
((c^b - d*a*b)^(a/b) - c)/(b*a)$
 
(((((c^b)-((d*a)*b))^(a/b))-c)/(b*a))$

The C program above is complete as it is, but the Java program requires a separate GetChar class that can be found at "Bare" Parser.

Revision date: 2013-02-06. (Please use ISO 8601, the International Standard.)