Creating Finite State Machines in C++
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
You Do the Math
In my years of software development, I’ve seen many situations in which people write long, complex functions filled with if statements to solve seemingly complex problems. Typically these problems involve stepping through various situations over time. Too often, however, what the people creating the code totally overlook is that the problem can be solved easily using a forgotten structure called a finite state machine (FSM).
A finite state machine is simply a set of states and a set of rules and actions that go with those states. For example, suppose you’re writing code that solves simple math problems written in infix notation, which is the usual notation we use for our math problems, such as the following:
3+4*2-6
Those of us in the computer field (who usually excel at math) can probably recognize the most likely mistake somebody might make in processing this statement: the order of operations. If you first solve 3+4 to get 7, and then multiply by 2 to get 14, and then subtract 6 to get 9, you’ll get the wrong answer. The multiplication takes precedence over the addition and subtraction, meaning that you do the multiplication first. Thus, you add 3 to the product of 4 times 2 (3+8), to get 11, and then you subtract 6, to get a final answer of 5.
Now, with the order of operations out of the way, how would you set out to write code to solve this problem? It turns out that the algorithm isn’t terribly difficult, but it’s not trivial, either. In fact, the algorithm to solve an infix problem is actually well-known (and thus not something you need to—or should—invent from scratch). It involves first converting the infix string to a postfix string, and then solving it. Postfix means that you first put in the numbers and then the operator; for example, 3 7 + means 3+7, or 10.
The above infix expression, 3+4*2-6, looks like this rewritten as postfix:
342*+6-
So, given the algorithm to convert an infix expression to a postfix expression, how do you then parse the string and solve it? Just to up the ante, let’s assume that you can have numbers of these sorts:
123 1.23 1.23e-5
Thus, you want your program to evaluate an expression such as this:
6.02e23/153.25
Further, you want the program to generate an error if you give it something incorrect, like this:
1+2q
If you’re familiar with a lot of algorithms (or if you just search the Web), you can easily find samples that demonstrate how to solve such an expression. But I’d like to show you a shortcut, using the concept of a finite state machine that can do all of the following:
- Solve infix expressions of the four basic operators (+ - * /).
- Handle numbers that include a decimal point or scientific notation
- Signal an error if the expression isn’t right
I would argue that the most difficult part is parsing the string, extracting the numbers in various formats. This is where some people start writing giant loops filled with dozens of if statements—probably even if statements embedded within if statements. Not only is such code complex, it’s likely bug-ridden.
Whenever I’m given such a problem, I think of a finite state machine.