Problem
I recently posted some sample code that I was providing students with and got great feedback so figured I post another one of the examples I will be providing students with. (See Simple Example of an Iterable and an Iterator in Java)
This one is a simple postfix calculator. The main learning objectives are basic inheritance, trees, post-order and in-order traversals and stack based parsing of postfix expressions.
First, the CLI code:
import java.util.Scanner;
public class PostfixCLI {
public static void main(String[] args) {
System.out.println("Enter postfix expression to evaluate, 'exit' to exit.");
Scanner in = new Scanner(System.in);
while (true) {
try {
System.out.print(">>> ");
String input = in.nextLine();
if (input.equals("exit")) {
break;
}
Expression expression = Expression.parsePostOrder(input);
System.out.format("%s = %.4fn",
expression.toString(),
expression.evaluate());
} catch (InvalidExpressionException e) {
System.out.println("Invalid expression: " + e.getMessage());
continue;
} catch (RuntimeException e) {
System.out.println("Runtime error: " + e.getMessage());
continue;
} catch (Exception e) {
System.out.println("Unknown error: " + e.getMessage());
continue;
}
}
}
}
And the Expression.java file that does most of the work.
import java.util.Stack;
import java.util.Scanner;
public abstract class Expression {
public abstract double evaluate();
public String toPostOrder() {
return this.toString();
}
public String toInOrder() {
return this.toString();
}
/*
* Parse an expresssion tree given a string and return the resulting tree.
* InvalidExpressionException is raised in cases of invalid input.
*/
public static Expression parsePostOrder(String expression)
throws InvalidExpressionException {
Scanner tokenizer = new Scanner(expression);
Stack<Expression> stack = new Stack<Expression>();
while (tokenizer.hasNext()) {
String token = tokenizer.next();
try {
double number = Double.parseDouble(token);
stack.push(new Number(number));
} catch (NumberFormatException e) {
// If control reaches here it's because the token is not a
// number, so it must be an operator.
if (stack.size() < 2) {
throw new InvalidExpressionException(
"Not enough parameters for " + token);
}
Expression right = stack.pop();
Expression left = stack.pop();
stack.push(BinaryOperator.fromSymbol(token, left, right));
}
}
if (stack.size() != 1) {
throw new InvalidExpressionException("Not enough operators.");
}
// The single item left on the stack is the root of the tree.
return stack.pop();
}
}
class Number extends Expression {
double number;
public Number(double num) {
super();
this.number = num;
}
@Override
public double evaluate() {
return this.number;
}
@Override
public String toString() {
return Double.toString(this.number);
}
}
abstract class BinaryOperator extends Expression {
Expression left;
Expression right;
protected abstract String getOperatorSymbol();
public BinaryOperator(Expression left, Expression right) {
super();
this.left = left;
this.right = right;
}
@Override
public String toString() {
return this.toInOrder();
}
@Override
public String toInOrder() {
return "(" + this.left.toInOrder() + " " + this.getOperatorSymbol()
+ " " + this.right.toInOrder() + ")";
}
@Override
public String toPostOrder() {
return this.left.toPostOrder() + " " + this.right.toPostOrder() + " "
+ this.getOperatorSymbol();
}
public static BinaryOperator fromSymbol(String symbol, Expression left,
Expression right) throws InvalidExpressionException {
if (symbol.equals("+")) {
return new AddOperator(left, right);
} else if (symbol.equals("-")) {
return new SubtractOperator(left, right);
} else if (symbol.equals("*")) {
return new MultiplyOperator(left, right);
} else if (symbol.equals("/")) {
return new DivideOperator(left, right);
} else {
throw new InvalidExpressionException("Invalid operator: " + symbol);
}
}
}
final class AddOperator extends BinaryOperator {
protected AddOperator(Expression left, Expression right) {
super(left, right);
}
@Override
protected String getOperatorSymbol() {
return "+";
}
@Override
public double evaluate() {
return this.left.evaluate() + this.right.evaluate();
}
}
final class SubtractOperator extends BinaryOperator {
protected SubtractOperator(Expression left, Expression right) {
super(left, right);
}
@Override
protected String getOperatorSymbol() {
return "-";
}
@Override
public double evaluate() {
return this.left.evaluate() - this.right.evaluate();
}
}
final class MultiplyOperator extends BinaryOperator {
protected MultiplyOperator(Expression left, Expression right) {
super(left, right);
}
@Override
protected String getOperatorSymbol() {
return "*";
}
@Override
public double evaluate() throws RuntimeException {
return this.left.evaluate() * this.right.evaluate();
}
}
final class DivideOperator extends BinaryOperator {
protected DivideOperator(Expression left, Expression right) {
super(left, right);
}
@Override
protected String getOperatorSymbol() {
return "/";
}
@Override
public double evaluate() {
double left = this.left.evaluate();
double right = this.right.evaluate();
if (right == 0) {
throw new RuntimeException("Division by zero in " + this.toString());
}
return left / right;
}
}
Solution
General
-
Use full JavaDoc for method comments. Instead of “Throw X in case Y” go for “@throws X if Y”
-
You never need to call the default (zero-argument) superclass constructor. If the first statement of a constructor isn’t a call to some superclass constructor, a call to the default constructor is inserted if there is one. If not, the class won’t compile. (Thanks @cHao!)
-
You can drop
this.when accessing other members unless there’s ambiguity. If you find yourself needing to use it outside constructors and setters–which contain lines likethis.field = field–take it as a subtle hint that you may need to refactor the method or rename a local variable. -
The protected access level on a constructor for a final class is equivalent to package-private; drop
protectedto be explicit. That being said, if this is a beginning class you may want to stick with public classes until you can cover the reasons for using package-private.
Update: I expand a bit on some of the original items and address some more higher-level design issues below.
PostfixCLI
This class is very simple, but there are a couple small changes you can make to start teaching good habits to your students right away.
-
Keep
mainto a few lines, enough to instantiate the REPL class and run it. This makes reusing it and writing unit tests easier and limitsmainto bridging the gap between the JVM launching your application with arguments and the application itself. -
As @Vogel612 states, you should rarely catch the top-level exceptions (
RuntimeException,Exception,Throwable, et al). Especially when learning it’s better to let them propagate to the JVM and kill the process.Since you’ve created your own exception hierarchy, the only exceptions getting through should be utterly unanticipated:
OutOfMemoryError,StackOverflowExceptionand the like. There’s nothing you can do about these here, and they will indicate a serious problem in the code that requires attention.Granted, in a customer-facing application you’d end up catching these in a generic fashion, logging them for a debug session, and exiting the application as gracefully as possible. Rarely will you be able to do anything more than let the exception bubble up, and students won’t be at the level of experience to do anything better for a long while.
I’m pushing hard on this one because every project on which I’ve worked has required going through pages of code to remove
catch (Exception e) { e.printStackTrace(); }as it makes tracking down errors very difficult.
Expression (minus the parser)
-
Expression.toInOrdercallstoStringwhileBinaryExpression.toStringcallstoInOrder. This works, but it’s very confusing. Is there a better way? (Maybe not) -
Shouldevaluatereturn aNumberinstead of a rawdouble?
Number
- To go with
evaluateand differentiate it fromNumber, consider renaming thenumberfield tovalue. The constructor argument can also bevaluesince there’s no reason to shorten it tovalornum.
BinaryOperator
-
Add a field to store the operator in
BinaryOperatorand pass it from each subclass constructor, removing the need forgetOperatorSymbol(). -
Instead of throwing a generic
RuntimeExceptionwhen dividing by zero, create a customDivideByZeroExceptionor better still, handleNaNinsideNumberand the other operators. -
It would be great to separate the operator itself from its use in an expression with left and right values. However, I understand you must keep it simple enough for your students, so I’ll leave it at that. 🙂
Parser
-
If the user enters “2.42.74”, it will be erroneously reported as not having enough operands. Instead, parse the token to an operator, and only when that passes do you know the real problem.
-
Once you change the above, you can handle unary operators like “1/x”. The operator should know how many operands it needs, and it should be given the stack itself rather than pulling off two values in the loop.
The parser is doing way too much to cram it into a single method, and that it knows every operator requires two operands paints yourself into a corner. The first step is to move this code into a separate class that can maintain the stack and do the work to manipulate it across methods.
The parsing method needs to be refactored into methods to scan the input, parse each token, apply it to the stack, and finally return the result. Here’s a rough cut:
public class Parser {
private final Stack<Expression> stack = new Stack<>();
public Expression parse(String input) {
Scanner tokens = new Scanner(expression);
while (tokens.hasNext()) {
parse(tokens.next());
}
if (stack.size() != 1) {
throw new InvalidExpressionException("Not enough operators");
}
return stack.pop();
}
private void parse(String token) {
... parse Number or Operator and place result on stack ...
}
}
This answer will focus on the main method
Separation of concerns:
You have the full story in your main method. You do: Exception-Handling, printing, prompting and a little bit of parsing:
You might want to move that to different methods. The abstraction level in main method should be so high, it reads more like plain english instead of code:
public static void main(String[] args){
while(true){
try{
String input = promptUserForInput();
if(isExitCode(input)){
break;
}
parseExpressionAndPrintResults(input);
}
catch(Exception e){
System.out.println("Unknown error: " + e.getMessage());
continue;
}
}
}
Error Handling:
Your catch of RuntimeException is redundant. Runtime Exceptions will also be caught when catching Exception. That is one of the reasons, why it is considered bad practice to catch Exception.
Accordingly you can remove:
catch(RuntimeException e){
System.out.println("Runtime Error: " + e);
continue;
}
Prompting the user for input:
I had an answer on a different post, which mostly concerned itself with that, you might want to have a look at it for more on parsing numbers.
Other than that:
System.out.println("Enter postfix expression to evaluate, 'exit' to exit.");
It is generally considered easier to use named constants instead of long strings, how does this look to you:
System.out.println(PROMPT);
And while we’re at it, the prompt you issue will be “shoved” out of the screen. I prefer prompting the user before every input. That’s why I would write the aforementioned promtUserForInput() as follows:
private String promptUserForInput(){
final String PROMPT = "Enter postfix expression to evaluate, 'exit' to exit.n >>> ";
System.out.println(PROMPT);
Scanner in = new Scanner(System.in); // you can move that to class-level if you
//want to minimize the overhead from creating it.
return in.nextLine();
}
Parsing the input:
Well the rest is simple, I’d just move the code that you didn’t see yet into the parseExpressionAndPrintResults method.
try {
double number = Double.parseDouble(token);
stack.push(new Number(number));
} catch (NumberFormatException e) {
// If control reaches here it's because the token is not a
// number, so it must be an operator.
}
This sounds like a job for if (tokenizer.hasNextDouble())..., as that improves readability.
Will all operator symbols be a single-character String?
If so, I suggest using chars instead. If you are keeping to single-character Strings and developing using Java 7 or later, then I will also suggest using a switch in the static method BinaryOperator.fromSymbol() instead of the if-else ladder you have currently used. Alternatively, consider enums too…
One thing in particular stands out to me here in your program, and it is that you are making it very difficult to extend this to allow for other types of operators.
If I were to add only a single new binary operator, modulus division (%), I would have to also add a new case to the switch statement. A slightly better option would be to have an array of operator factory objects, which would have a method to themselves check if the symbol matches their operator.
If I wanted to add a unary operator, such as negation, square root, factorial, or something like that, I would not only have to add a case, I would need to define a brand new base class for Unary Operators, and a factory methods for producing them, and a number of other things. Instead, make the operator base class less specific to binary operators, and just have one version that takes a varargs parameters
And then there are the Generalized Stack Manipulation Operators: duplicate (copy top element), exchange (swap top elements), pop (delete top element), clear (delete all elements), store (place top element in separate storage), load (retrieve element from external storage), and dozens of others. These commands all either produce multiple results, take different numbers of arguments depending on the values of other arguments, or are stateful, their exact meaning changing depending on earlier parts of the program.
No amount of magic will be able to make these operators fit into the paradigim of expression-producing-binary-operators that pervades your code. If you intend to support these more general operators, then you will need to remap some responsibilities of the classes:
I would recommend separating Operators completely from Expressions. Operators are not by themselves expressions – operators are used to combine different expressions into one expression.
Then, make the Operators responsible for handling adjustment of the stack. When you determine that a particular operator is to be employed , say Add, just call Add.operate(stack). Add is then responsible for taking the top two Expressions from the stack, and placing an AdditionExpression formed from them onto the stack.
Once you have support for these generalized operators, you can build an interactive console on top of it, where users issue commands that are then added to the stack, which is then persisted between prompts, allowing for extended computations. and experimentation with the stack structure.