Cleaning up Reverse Polish Notation evaluator

Question

I was wondering if anyone had some general clean up advice on my code. I believe that more helper functions would be my case but I could be wrong. 30 lines maximum per method is my rule. I can't seem to figure out how to clean this up more, though.

Sample Input:

(1/3) (1/5) - (40/1) * #

(2/3) B * #

Sample Output

Expression 1 is: (1/3)(1/5)-(40/1)*

The value is: (16/3)

Intermediate results: (2/15)(16/3)

Expression 2 is: (2/3)B

Invalid Expression

Intermediate results:

import java.util.Scanner;

public class RpnEvaluator
{
   private final int MAX_TOKEN = 100; 
   private Scanner stdin = new Scanner(System.in);
   private Queue myQueue = new Queue(MAX_TOKEN);
   private Stack myStack = new Stack(MAX_TOKEN);

   public void run() throws java.io.IOException
   {
      int count = 1;
      Fraction myInterMid;
      while(stdin.hasNext())
      {
         runOnce(count++);
         System.out.print("Intermediate results: ");
         while(!myQueue.isEmpty())
         {
            myInterMid = (Fraction)myQueue.remove();
            System.out.print(myInterMid.toString());
         }
         System.out.println();
         clear(myStack, myQueue);
      }
      System.out.println("Normal Termination of Program 3.");
   }

   private boolean isOperator(String input)
   {
      String[] oprtr = {"+", "-", "*"};
      for(String choice: oprtr)
         if(choice.equals(input))
            return true;
      return false;
   }

   private boolean isOperand(String input)
   {
      if(input.charAt(0) == '(')
         return true;
      return false;
   }

   private Fraction runOperation(String choice, Fraction op2, Fraction op1)
   {
      Fraction newFract = new Fraction();
      switch (choice)
      {
         case "*":
            newFract = new Fraction(op1.times(op2));
            break;
         case "+":
            newFract = new Fraction(op1.plus(op2));
            break;
         case "-":
            newFract = new Fraction(op1.minus(op2));
            break;
      }
      return newFract;
   }

   private void runOnce(int count)
   {
      Fraction op1 = null;
      Fraction op2 = null;
      clear(myStack, myQueue);

      System.out.print("Expression " + count++ + " is: ");
      doTypeCheck(op1, op2); 
   }

   private void clear(Stack myStack, Queue myQueue)
   {
     myStack.clear();
     myQueue.clear();
   }

   private void runTheOperator(Fraction op2, Fraction op1,
         String readIn)
   {
      op1 = (Fraction)myStack.pop();
      Fraction interMed = runOperation(readIn, op2, op1);
      myStack.push(interMed);
      myQueue.add(interMed);
   }

   private void doTypeCheck(Fraction op1, Fraction op2)
   {
      Fraction answer = null;
      String readIn = "";
      boolean valid = true;
      readIn = stdin.next();

      while(!readIn.equals("#") && valid == true)
      {
         if(!isOperator(readIn) && isOperand(readIn))
         {
            processOperand(readIn);
            readIn = stdin.next();
         }
         else if(isOperator(readIn))
         {
            System.out.print(readIn);
            if(myStack.isEmpty())
               valid = false;
            else
               op2 = (Fraction)myStack.pop();

            if(myStack.isEmpty())
            {
               valid = false;
               throwLine(readIn);
            }
            else
            {
               runTheOperator(op2, op1, readIn);
               readIn = stdin.next();
            }
         }
         else
         {  
            System.out.print(readIn);
            valid = false;
            throwLine(readIn);
         }
      }
      System.out.println();
      if(myStack.isEmpty())
         valid = false;
      else
         answer = (Fraction)myStack.pop(); 
      if(!myStack.isEmpty())
         valid = false;
      checkMessageValid(valid, answer);
   }

   private void checkMessageValid(boolean valid, Fraction answer)
   {
      if(valid == false)
         System.out.println("Invalid Expression");
      else
         System.out.println("The value is: " + answer.toString());
   }

   private void throwLine(String line)
   {
      while(!line.equals("#"))
      {
         line = stdin.next();
      }
   }

   private void processOperand(String readIn)
   {
      Fraction stringFract = null;
      Fraction myFract = null;
      stringFract = new Fraction(readIn);
      System.out.print(stringFract.toString());
      myFract = new Fraction(readIn);
      myStack.push(myFract);
   }

}

Answer 1

Reverse Polish Notation does not need parentheses, so that should actually be invalid input and should not be checked.

To determine if something is an operand you should be able to use stdin.hasNextInt(). If that is false, then you should be able to use stdin.next() to get whatever the operator is. This could greatly simplify your type checking.

Instead of terminating input with # you should just check for newlines.

I'm not sure what the purpose of having myQueue is. You should only need a stack for processing RPN.

I would recommend reading up on RPN to understand it more (the Wikipedia page has an algorithm for interpreting RPN) and see if that gives you ideas on how you might rethink your approach.

---

Edit: Assuming that the input format and output values are requirements, there are several things you can do to improve the code.

• MAX_TOKEN should be private static final.
• You should rename your methods to better describe what they do. runOnce() is called in a loop, so it is not called once, and it doesn't explain what it does. I would recommend something like processNextCalculation(). doTypeCheck(), throwLine() and checkMessageValid() should also be renamed.
• You should move the output in checkMessageValid() to be in the same place as where you output the intermediate results. You will need to change some return values to propagate the results upward.
• isOperand() can be reduced to return input.charAt(0) == '(';
• In run() you don't use myInterMid elsewhere so you can remove references to it and simply System.out.println(myQueue.remove());
• You should try to be consistent about using my as a prefix. Typically, it implies that the variable is an instance member variable, but you also use it for variables within methods. That is definitely confusing.
• I don't know what is in your Fraction class, but I imagine that the times(), plus(), and minus() methods are returning Fractions, so you don't need to new one up from the result.
• You don't need to declare op1 and op2 in runOnce(), since you can just pass two nulls to doTypeCheck(). For that matter, you don't need to even have parameters for doTypeCheck(). Once you've done that, you should bring the rest of the method up to run() so you can keep your text output in the same place.
• Since you can't have both isOperator() and isOperand() be true, you don't need to check both in your first if condition in doTypeCheck().
• You don't need to check myStack.isEmpty() twice, you should be able to check if myStack.size() is less than two. If your implementation of Stack doesn't have a size() method, well...I feel bad for you.
• Whenever myStack.isEmpty() is true, you can break out of the loop and your failure case will still show correctly.
• You only need one Fraction in processOperand() and you can initialize it on the same line as you declare it.

Answer 2

Don't add more helper methods. The problem isn't that you need to split up your existing methods. Rather, it's that your existing helper methods aren't meaningful or elegant. For example, what does runOperation() do? How about runTheOperator()? Why do both methods exist, and why do they accept arguments in different orders? What does doTypeCheck() do, and why do you pass it two null arguments?

Taking a big picture view… the beauty of Reverse Polish calculators is that they should be very simple to implement. Your code does not feel simple. Some of the complications are:

1. You're implementing an RPN calculator that operates on rationals rather than integers. I can accept that, but you should recognize that the syntax/grammar is no longer pure and easy to parse.
2. An RPN calculator normally needs just one data structure: a stack. You've introduced a queue to log the intermediate results, which complicates the code.
3. You shouldn't feed the operands to an RPN operator; an RPN operator can work directly on the stack. A typical operator would pop two items and push one result, but other kinds of operators could exist as well. For example,
   • A negate operator would flip the sign of the top element
   • A clear operator would remove everything from the stack
   • A swap operator would pop the top two elements from the stack and push them back in reverse order

My suggested remedies are:

1. Implement an RPN calculator for integers first. Then, if you want to add support for fractions, do so by hacking the Scanner, not the core of your calculator. You should have to change little in the calculator itself other than a few data types and names of method calls.
2. I recommend dropping the intermediate display feature. A typical RPN calculator would display either the top of the stack or the entire stack at every prompt. If the user wanted to see intermediate results, he/she could simply split up the input over several lines.

3. Define a class for operators. A reasonable framework might be

   public abstract class RpnOperator {
       private static final HashMap<String, RpnOperator> ALL = new HashMap<String, RpnOperator>();
   
       public final String symbol;
   
       public RpnOperator(String symbol) {
           this.symbol = symbol;
           ALL.put(symbol, this);
       }
   
       public static RpnOperator forSymbol(String symbol) {
           return ALL.get(symbol);
       }
   
       public abstract void operate(Stack<Fraction> calcStack) throws RpnException;
   }
   

   Then, in the calculator, you could define

   private static RpnOperator ADD = new RpnOperator("+") {
       public void operate(Stack<Fraction> calcStack) {
           Fraction a = calcStack.pop();
           Fraction b = calcStack.pop();
           calcStack.push(a.plus(b));
       }
   };
   

You didn't post your Fraction class, but I suspect that there are problems there too. For example, you call new Fraction(op1.plus(op2)) — why is op1.plus(op2) insufficient, such that you need to copy-construct that result into another Fraction object?