PN Example

Nicholas Duchon: Mar 31, 2017

Key Concepts:

  • Recusion
  • Static intializers
  • ArrayList <String> for test cases
  • Scanner as a parameter to recursive method
  • Exceptions
  • Continue after exceptions

Code with line numbers and comments:

1
// File: PNEvaluation.java
2
// Date: Mar 30, 2016
3
// Purpose:
4
//   recursion on a pre-fix string
5

6
import java.util.Scanner;
7
import java.util.ArrayList;
8

9
class MyEx extends RuntimeException {
10
  public MyEx (String s) {super (s);}
11
} // end unchecked exception
12

13
public class PNEvaluation {
14
  static ArrayList <String> asPN = new ArrayList <> ();
15
  static String m1 = "not enough values in string";
16
  static String m2 = "bad element where there should be an operator: ";
17

18
  static {
19
    asPN.add ("+ / + 50 6 + 3 4 10");
20
    asPN.add ("+ 5 6");
21
    asPN.add ("- 5 6");
22
    asPN.add ("* 5 6");
23     asPN.add ("/ 5 6");
24     asPN.add ("/ + - 10 3 * 6 - * 4 7 3 + 2 * 3 5");
25     asPN.add ("+ + / 5 6 8");
26     asPN.add ("+ + / 5 6 8 9");
27     asPN.add ("+ + ^ 5 6 8 9");
28     asPN.add ("/ 1 - 3 3");
29     asPN.add ("/ -1 - 3 3");
30     asPN.add ("* a 6");
31   } // end static initializer
32    
33   public static double eval (Scanner sc) throws MyEx {
34     if (!sc.hasNext()) throw (new MyEx (m1));
35     if (sc.hasNextDouble()) return sc.nextDouble ();
36     String st = sc.next ();
37     switch (st) {
38       case "+": return eval (sc) + eval (sc);
39       case "-": return eval (sc) - eval (sc);
40       case "*": return eval (sc) * eval (sc);
41       case "/": return eval (sc) / eval (sc);
42       default : throw (new MyEx (m2 + st));
43     } // end processing an operator
44   } // end recursive method eval
45    
46   public static void main (String args []) {
47     for (String spn: asPN)
48       try {
49         System.out.println (spn + " = " + eval (new Scanner (spn)));
50       } catch (MyEx e) {
51         System.out.println ("   --- Problem with string: " + spn);
52         System.out.println ("   --- " + e);
53       } // end catch
54     System.out.println ("-- Bye --");
55   } // end main
56 } // end class PNEvaluation
It has been pointed out to me that I really should explain my code, and not just "dump and run".

So I thought this code might be interesting for a number of reasons beyond simply a recursive solution to the prefix processing problem. I like to think that this code presents an elegant solution to the processing a prefix string using the Java Scanner class, includes some error handling, and presents one way to add test cases into a project development cycle.

The test cases are implemented using a static initializer (lines 18-31), adding String's to an ArrayList <String>. I find this approach attractive because one can easily add elements to this list, or remove them, or even just comment out the list entries.

Because this code is using an ArrayList, the processing of the String's can be done using an advanced for-each loop, lines 47-53).

A nice feature of the for-each loop (47-53) is the use of a try/catch block within the loop. The result of this approach is that if a line in the ArrayList of String's has a problem (throwing an exception), the loop will still continue to the following lines of the list.

This code will detect two problems with a String: not enough values for the number of operators, and anything that is in the string where an operator should be that is not one of the recognized operators (+, -, *, /).

As for the recursive method, I rather think this is elegant code, short and easy to understand.

I have put reference line numbers in parentheses below:

(33) throwing an exception lets the caller of this code go on to the next line with a helpful error message

(34) there should be more in this String to match the operators encountered so far

(35) a double means that a value has been encountered, so just return this value to the caller step of the recursion

(36) get the next token as a String, used on lines 37 and 42, the latter in case this token is not an operator

(37) try switching on the token

(38-41) JDK 8 supports the use of cases with String's. Each case makes recursive calls and does the appropriate operation. Passing a Scanner instance around, and doing immediate returns is one elegant way to handle the recursion in this situation.

(42) the String has an unrecognized entry, and the code throws an exception, letting the caller go on to the next line of ArrayList <String> in this program.

You may wish to confirm your understanding of this code by considering the output of this program:
+ / + 50 6 + 3 4 10 = 18.0
+ 5 6 = 11.0
- 5 6 = -1.0
* 5 6 = 30.0
/ 5 6 = 0.8333333333333334
/ + - 10 3 * 6 - * 4 7 3 + 2 * 3 5 = 9.235294117647058
   --- Problem with string: + + / 5 6 8
   --- MyEx: not enough values in string
+ + / 5 6 8 9 = 17.833333333333336
   --- Problem with string: + + ^ 5 6 8 9
   --- MyEx: bad element where there should be an operator: ^
/ 1 - 3 3 = Infinity
/ -1 - 3 3 = -Infinity
   --- Problem with string: * a 6
   --- MyEx: bad element where there should be an operator: a
-- Bye --

Raw code:

// File: PNEvaluation.java
// Date: Mar 30, 2016
// Author: Nicholas Duchon
// Purpose:
//   recursion on a pre-fix string

import java.util.Scanner;
import java.util.ArrayList;

class MyEx extends RuntimeException {
  public MyEx (String s) {super (s);}
} // end unchecked exception

public class PNEvaluation {
  static ArrayList <String> asPN = new ArrayList <> ();
  static String m1 = "not enough values in string";
  static String m2 = "bad element where there should be an operator: ";
 
  static {
    asPN.add ("+ / + 50 6 + 3 4 10");
    asPN.add ("+ 5 6");
    asPN.add ("- 5 6");
    asPN.add ("* 5 6");
    asPN.add ("/ 5 6");
    asPN.add ("/ + - 10 3 * 6 - * 4 7 3 + 2 * 3 5");
    asPN.add ("+ + / 5 6 8");
    asPN.add ("+ + / 5 6 8 9");
    asPN.add ("+ + ^ 5 6 8 9");
    asPN.add ("/ 1 - 3 3");
    asPN.add ("/ -1 - 3 3");
    asPN.add ("* a 6");
 
} // end static initializer
 
  public static double eval (Scanner sc) throws MyEx {
    if (!sc.hasNext()) throw (new MyEx (m1));
    if (sc.hasNextDouble()) return sc.nextDouble ();
    String st = sc.next ();
    switch (st) {
      case "+": return eval (sc) + eval (sc);
      case "-": return eval (sc) - eval (sc);
      case "*": return eval (sc) * eval (sc);
      case "/": return eval (sc) / eval (sc);
      default : throw (new MyEx (m2 + st));
    } // end processing an operator
 
} // end recursive method eval
 
  public static void main (String args []) {
    for (String spn: asPN)
      try {
        System.out.println (spn + " = " + eval (new Scanner (spn)));
      } catch (MyEx e) {
        System.out.println ("   --- Problem with string: " + spn);
        System.out.println ("   --- " + e);
      } // end catch
    System.out.println ("-- Bye --");
  } // end main
} // end class PNEvaluation



End
Nicholas Duchon