Finite State Machines and the State Design Pattern

EXAMPLE 1: Prefix, postfix, and infix notation

• 10 buttons labeled 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, respectively, to enter digit characters
• one button labeled . to enter the decimal point
• one button labeled +, to perform addition
• one button labeled *, to perform multiplication
• one button labeled =, to compute the result of the input so far
• one button labeled C, to clear all entries in the calculator and reset the calculator to its pristine initial state.
• and a display text field for me to view the input and the result of my desired computation.

• First click C to reset the calculator. The display should show '0'.
• Now, click '3', then '3' again, then '3' again.
• What do you see? The first time you click '3', the calculator replaces '0' with '3'. Then for each subsequent click on '3', the calculator simply appends '3' to the current display text field and update it with the resulting string. You should see "333" at this point.
• Next, click '+': "333" is still being display. But now click '3'. What happens? '3' is no longer appended to the existing display string, isn't it? You are sending the same message to the calculator by clicking the same '3', but the calculator responds differently this time, doesn't it? It has dynamically changed its behavior after you clicked on '+'! Again what we see here is another example of "state change". Clicking the '+' causes the calculator to transition to another state.

• click a digit button,
• click an operation button,
• click the equal button,
• click the clear button,
• click the point button.

NOTE: 

Start State

When you first turn on the calculator, imagine that it is in some initial condition called a start state. Suppose, from the start state, you...

• click a digit button: what do you want to happen? It depends...
  • digit = '0': display '0' and not concatenating '0' on subsequent clicks on '0'. This implies the calculator can stay in the same start state when '0' is clicked.
  • digit != '0': display the digit and begin concatenating any digit (including '0') on subsequent digit clicks. This implies the existence of another state for the calculator to switch to after a non-zero digit is clicked for the first time. Let's call this new state the accumulate state. We shall analyze the behavior of this state later.
• click an operation button, for instance, "+", which we will refer to as "op" for generalities sake. Among the many things we want to happens here, one thing for sure we want is for the calculator to remember op as a pending operation so that we can enter another number, click the equal button and get the correct result. A subtle problem arises here. Is there any current pending operation to be perform before updating op as the new pending operation? You may say, well, if we just turn on the calculator and the first thing you do is click an op button, then there is no pending operation to perform. The response to that is the calculator may transition form one state to another during its usage and may come back to the start state with some pending operation yet to be carried out. In any case, the calculator must have a way to remember a pending op, it is best to have the calculator remember a well-defined pending op at all times, even if there is no pending op at all. This is where the concept of a no-op operation becomes useful. Define the no-op operation to be an operation that "does nothing" and use no-op as a pending operation when there is no operation to perform. In the design pattern language, this is called the "Null Object" pattern. The next question to ask is whether or not the calculator should change to a state different from both the start state and the accumulate state.
  • Can the calculator stay in the same start state? Say, in the beginning you start with the number 0 in the display, and you click '+' . This is tantamount to entering the expression 0 +. If you click the equal button next, then you are in essence asking the calculator to compute 0 +, which is an invalid infix expression. What do you want the calculator to do and display here? Examine a few real calculators of different brands and see how they behave. Also, examine a few different "software" calculators, if you have any. They do not all behave the same way, do they? The behavior here can be arbitrarily defined because the expression entered ( 0 + ) is not a valid infix expression. So we arbitrarily specify that our calculator display an error message, stop accepting any additional inputs and stop performing any additional operations. This implies the existence of a new state called the error state. With this new behavior specification, the calculator cannot stay in the same state as the start state because, as we shall see in the discussion of the click equal event that follows, the start state cannot display an error.
  • Can the new state be the same as the accumulate state? If we transition to the accumulate state after we click an op, then we should be accumulating '0' as we continually click on '0', shouldn't we? But is that want we want the calculator to behave like? Of course not. After we click an op button, we should be in a state where we can accept new digit inputs. If we click '0', we do not want to accumulate '0' at all. Since this new state does not have the same behavior as the accumulate state discovered in 1, it is a different state. Let's call this state the compute state. We get to a compute state after we click on an op button.
• click the equal button: we want the calculator to compute the pending operation, which may be a no-op, update the pending operation to a no-op (since there is no more operation to perform), display the result and be ready to accept a brand new input. There is no need to transition to any state.
• click the clear button: we want the calculator to be reset to the initial pristine condition as if it has just been turned on. Obviously, the calculator should stay in this same start state.
• click the point button: we want to display "0." to signify that we have just entered a decimal point in order to input a number less than one. Do we stay in the same start state? We can't, because if we click '0' next, we want to see "0.". Should we stay in the start state, we would be displaying "0" instead. The new state is obviously not the error state either. Let's call this new state the point state.
  • Can the point state be the compute state? Consider the following sequence of 4 clicks: '0', '.' , '0', '0'. After the first click, '0', the calculator stays in the same start state. If after the second click ('.'), we do not change state, then after the third click ('0'), and fourth click ('0'), the calculator would display "0" and not "0.00", as it should. Therefore the point state cannot be the compute state.
  • Can the point state be the accumulate state? It depends on what we want the calculator to behave like once we are in the point state and keep clicking '.'. The first '.' click will cause the calculator to display "0.". What do we want the computer to display if click '.' again? One reasonable behavior is to ignore the '.' click and do nothing. That is, once we are in the point state, we ignore all the point clicks. What should the accumulate state behave like when we click '.'? Can we ignore the point click once we are in the accumulate state? From the start state, we click '3' and change to the accumulate state as discussed in the above. Now, click '.'. If calculator ignores the point click and does nothing, then we cannot enter the decimal point at all. We can never enter something like "3.5". The accumulate state cannot ignore the first point click while the point state ignores all point clicks. Thus the point state and the accumulate state are not the same.

Beginning with one state, the start state, by analyzing and specifying the behavior of the calculator in response to the five distinct click events, we have inferred the existence of four distinct other states: accumulate state, compute state, point state and error state. We can repeat the same analysis on each of these states for each of the click events. We will not discussed them in details here. Instead, we summarize the state behaviors and the state transition in the form of a diagram shown below.

Figure 1: State Transitions

State Diagram

Let's get started! Remember to do the following parts in order:

• Create stub class files for InfixCalc, ACalcState, IBinOp, AddOp and MulOp as shown in the UML class diagram; be sure to put it in the infixModel subdirectory (package).
• Make AddOp and MulOp singletons and write the code for their compute() methods. This should be trivial.
• Look at the javadoc/UML documentation of the ErrorState field in ACalcState. It is set to a "do-nothing" state. This is called the "Null Object Pattern". Copy the code for ErrorState to your ACalcState file.
• Add appropriate System.out.println statements to the public methods of InfixCalc, AddOp and MulOp.
• Compile and run; click all the buttons to prove that your listeners are really listening.

• Create concrete classes StartState, AccumState, PointState and CompState as shown in the javadoc/UML diagram.
• Be sure to make them singletons.
• Add appropriate System.out.println statements to their public methods.
• Now, go back to InfixCalc and apply the state pattern by delegating all state-dependent behaviors to the state. Is clear() a state-dependent behavior?
• Compile and run to see that the delegations are made.
• Use the above state diagram to write the code for all the methods of each of the concrete state classes, one class at a time.
• Compile and manually test each of the classes by testing each of the click events.

• Modify InFixGUI to add a '1' button and a '2' button. Add appropriate event listeners for these two buttons.
• Add a subtraction binary operation and a division binary operation.
• Modify InFixGUI to add a subtraction button and a division button. Add appropriate event listeners for these two buttons.
• Compile and run and test at each of the above steps.
• You now should have a fully functional "cheap" calculator.