- You Do the Math
- What Exactly Is a Finite State Machine?
- Coding the State Machine
- Coding the States
- Coding the Driver
- Conclusion
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
What Exactly Is a Finite State Machine?
Rather than just giving an abstract definition of a finite state machine, I’ll supply an example that should demonstrate exactly what one is.
Think of a string such as this:
10+5-3*2=
Here are some states in which a processor going through this string might live:
- Reading a number
- Handling an operator
- Solving the expression, the "equals" state
Additionally, I need two more states:
- Start
- Error
These last two are just "bookkeeping" states.
Here’s how everything works. You start out in the Start state, and you begin reading the string. If you encounter a digit or a decimal point, you know that you’re now reading a number. That’s the "Reading a number" state. You continue doing so as long as you encounter a digit or a decimal point or the letter e. If you encounter one of the four operator characters (+ - * /), then you switch to the "Handling an operator" state. If you encounter an equal sign (=), you switch to the "Solving the expression" state. Otherwise, you switch to the Error state, because you found an invalid character.
Now what about the operator state? You stay in that state for only one character. Then you check the next character, and if it’s a digit or a decimal point, you go back to the "Reading a number" state. Otherwise you go to the Error state. But here’s a question for you: Do you have to do additional error checking and make sure that your operator is one of + - * /? No. The reason is that the other states took care of that verification for you. If you got to the "Handling an operator" state successfully, you know that you have an operator.
What does the equals state do? It solves the problem, and then immediately goes back to reading a number.
This almost seems too easy. But that’s what’s great about finite state machines: They automate a process that you build, and they take a lot of burden away from you, the programmer, especially in the areas of complexity and error handling.
Now I’d like to tabulate what I came up with. But I need to explain a couple of quick concepts:
- I’m going to write up each state along with a possible event that can take place. (In our simple problem, an event is just a character coming in.)
- Then I’m going to describe the action to take place when that event occurs, as well as the next state to head to, which might be the same state that the machine is currently in, which means that the machine won’t need to change states.
- Finally, I’d like to describe what each state does when the machine switches to the particular state.
Here’s the complete table for this problem.
|
State |
OnEnter |
Event |
Action |
Next State |
|
Start |
ClearAll |
0123456789. |
|
NumberEntry |
|
NumberEntry |
AppendDigit |
0123456789.Ee |
AppendDigit |
NumberEntry |
|
NumberEntry |
(same) |
+-*/^ |
Parse Number, Push on stack |
Operator |
|
NumberEntry |
(same) |
= |
Parse Number, Push on stack |
Equals |
|
NumberEntry |
(same) |
Other |
|
Error |
|
Operator |
Push operator on stack |
0123456789. |
Operate |
NumberEntry |
|
Operator |
(same) |
Other |
|
Error |
|
Equals |
Calculate |
0123456789. |
|
NumberEntry |
|
Equals |
(same) |
Other |
|
Error |
|
Error |
PrintErrorMessage |
|
|
Stop |
Although this table looks pretty complex, if you look at each state individually you can see that it’s actually very detailed yet simple. Look at the first row of the NumberEntry state, but ignore the OnEnter column. This row describes what to do when the NumberEntry encounters a digit. Think about that: If you’re reading a digit, and thus constructing a number, and you receive another digit, what do you do? You concatenate the next digit onto the number you’re constructing. Thus, in a detailed perspective, when you receive a digit, a decimal point, or a capital E or lowercase e for scientific notation (the event), then you append the received digit to the string of numbers you’re building (the action), and you stay inside the current state to receive another character for processing.
That’s the whole idea behind a state machine. You think in terms of states and what events can take place; then, in response to an event, determine what to do to process the event, and what state to go to next.
But one thing is missing. Although I haven’t yet discussed how to get into the NumberEntry state, you can assume that some other state received a character that triggered the machine to leave that state and switch to the NumberEntry state. The character received would be either a digit or a decimal point. (But not an E, because scientific numbers can’t start with an E.) What do you do with that digit? You don’t want to throw it away, and thus I’m also defining an OnEntry method for each state. For the NumberEntry state, the OnEntry method will take the character and use it to start the number being read. And that’s where the OnEntry column comes from in the table.
Let’s recap:
- For each state, I’m including an OnEntry method that runs when the state begins. Then I’m listing a set of events that can happen, and for each event an action followed by a next state. In the case of NumberEntry, I’ve detailed one event—a number. What other events can come in? That is, what characters can the machine receive? The ones I could think of were an operator (+ - * /) or an equal sign (=). For each of these, I list the action and the next state, as shown in the table.
- For the operator characters event, I parse the number and push it onto the stack, before moving on to the Operator state.
- For the equal sign, I also parse the number and push it onto the stack, but this time move on to the Equals state.
- Finally, I’m including one other event that can occur while reading a number: an error. What if you’re in the middle of reading in a string and you encounter some character that doesn’t belong? For that situation, I’m including one more row in the table. In such a case, the event would be any character I don’t want. The action is to do nothing; the next state is the Error state.
At this point, I need to mention a couple of things. First, I’m combining two processes into one: I’m running a state machine, and I’m simultaneously running an algorithm to convert an infix string to a postfix structure. I haven’t said much yet about the algorithm to convert to postfix; after all, this is an article about state machines. But you’re probably curious, so I’ll just briefly mention some points about it as I go along.
When converting infix to postfix numbers, the algorithm I’m using requires that you just push numbers onto a stack. (The meat of the algorithm is with the operators.) Thus, after receiving an entire number, I want to parse the number, and then save the number on a stack. Easy enough.