# Creating Finite State Machines in C++

## 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.