state machine

We discussed importing objects with high level IO in our "storing object" page. Another very useful programming style is the state machine programming. Let's use it to do the complex example.

To start with, we need to analyze all the possible input patterns and design "states" to manage its transition. Our possible complex patterns are i, a, bi, a+i, and a+bi where a, b could be positive or negative number. How many states do we need? I don't know. But, I will start with one state and build the transition diagram.

State Diagram

A careful analysis of the problem domain is critical to cover all cases. The machine above has 3 states, and it uses one flag neg to indicate plus or minus numbers. Can I eliminate the "flag"? Yes, you can. You will need to have more states though. It is a tradeoff of simplicity and clarity. For me, I usually prefer using states and dislike flag. But, a "sign flag" is quite compelling in this case.

Code

// use state machine approach to parse complex number

void complex_parse(string Ln) {

int s = 0;

bool neg = false;

int real=0, img=0;

int c;

char ichar='\0';

stringstream in;

in.str(Ln); // IMO, it is easier to deal with stream (versus string). So, I convert Ln to in

cout << "input:<" << Ln <<">\n";

while (s<9) {

// cout << "state " << s << endl; // my debugging style with state machine: I break to see the state transitions

switch (s) {

case 0: // i, -i

c = in.peek();

if (isdigit(c)) s=2;

if (c=='+') in.ignore();

if (c=='-') { in.ignore(); neg = true;}

if (c=='i') {

if (neg) cout << "<-i>(0, -1)\n"; else cout << "<i>(0, 1)\n" ;

return; }

break;

case 2: // a, bi

in >> real;

c = in.peek();

if (c==EOF) // this won't work in windows, in.eof() works

{ if (neg) real = - real;

cout << "<a>" << "("<< real << ", "<< 0 << ")\n";

return;}

if (c=='i') {

if (neg) real = - real;

cout << "<bi>" << "(" << 0 << ", " << real << ")\n";

return;}

if (c=='+') { in.ignore(); neg=false; s=4; }

if (c=='-') { in.ignore(); neg=true; s=4; }

break;

case 4: // a+bi, a-bi

if (in.peek()=='i') img = 1;

else in >> img >> ichar;

if (neg) img = - img;

cout << "<a+bi>" << "(" << real << ", " << img << ")\n";

return;

}

}

}

The above image was captured after changing real, imag to double.

Things to learn:

• State machine clarifies our thinking. It also serves as a great documentation.

• Compared with IF-THEN-ELSE, state machine is relatively easy to debug. Did you notice printing out each state transition above? It is a convenience place for breakpoint too.

• Many communication protocols (e.g. TCP) I know are documented and implemented with state machines.

  • Try to solve the same problem with regular control versus state machine and see the tradeoff. A lot of times, it is just personal preference.

Discussions:

• • Another popular method of "parsing" input is the regular expression approach. Compiler course usually covers that one well.

  • The code in this page has a few areas to be improved.

  • Instead of using 0, 2, 4 as the state, try more descriptive state names and use #define.

    • The while loop can be a bit more tight to avoid infinite loop.

    • There is no error checking (A BIG HOLE in real life coding).