PN Example
|
Key Concepts:
|
|
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 |
// 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