利用状态机解决问题
概念
状态机是软件编程中的一个重要概念。比这个概念更重要的是对它的灵活应用。在一个思路清晰而且高效的程序中，必然有状态机的身影浮现。
比如说一个按键命令解析程序，就可以被看做状态机：本来在A状态下，触发一个按键后切换到了B状态；再触发另一个键后切换到C状态，或者返回到A状态。这就是最简单的按键状态机例子。进一步看，击键动作本身也可以看做一个状态机。一个细小的击键动作包含了：释放、抖动、闭合、抖动和重新释放等状态。
程序其实就是状态机。
要素
状态机可归纳为4个要素，即现态、条件、动作、次态。这样的归纳，主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：
- 现态：是指当前所处的状态。
- 条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
- 动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。
4.次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。
如果我们进一步归纳，把“现态”和“次态”统一起来，而把“动作”忽略（降格处理），则只剩下两个最关键的要素，即：状态、迁移条件。
表示
状态机的表示方法有许多种，我们可以用文字、图形或表格的形式来表示一个状态机。
纯粹用文字描述是很低效的，所以就不介绍了。接下来先介绍图形的方式。
状态迁移图（STD）
状态迁移图（STD），是一种描述系统的状态、以及相互转化关系的图形方式。状态迁移图的画法有许多种，不过一般都大同小异。我们结合一个例子来说明一下它的画法，如图1所示。
- 状态框：用方框表示状态，包括所谓的“现态”和“次态”。
- 条件及迁移箭头：用箭头表示状态迁移的方向，并在该箭头上标注触发条件。
- 节点圆圈：当多个箭头指向一个状态时，可以用节点符号（小圆圈）连接汇总。
- 动作框：用椭圆框表示。
- 附加条件判断框：用六角菱形框表示。
状态迁移图和我们常见的流程图相比有着本质的区别，具体体现为：在流程图中，箭头代表了程序PC指针的跳转；而在状态迁移图中，箭头代表的是状态的改变。
实践
利用状态机实现去除Ｃ/C++代码中的注释
思路
首先想象一下处理过程，一个字符一个字符的读取输入文件，如果是一般字符，原样输出；如果是特殊字符 /, *, ", /, \n 特殊处理。比如遇到一个 / 字符，则需要看下一个字符是否是 /，如果是就找到了单行注释的开头，接下来找换行符 \n，该行不输出；如果下一个字符是*，则找到了多行注释的开头，接下来需要找匹配的 */；如果是遇到了双引号"，则再遇到下一个"之前，要忽略掉这之间的注释。。
状态机迁移图
各状态解析
- state 0: 正在分析，在这个状态下，读到什么，输出什么。
- state 1: 读到第一个/
- state 2: 读到第二个/。（//...）
- state 3: 读到第一个。（/）
- state 4: 读到第二个。（/...*）
- state 5: 读到第一个双引号"
- state 6: 读到转义字符（转义字符后面的双引号不用来配对的）
- state 7: 读到//后面的行连接符\。 （//......\）
- state 8: 读到//后面的行连接符\后，继续处理
- state 9: 和state0是等价状态，分出这个状态可以做一些操作，比如删除注释。
代码
#include <cstdio>
#include <cstring>
#include <string>
unsigned char fsm[10][256];
void Initfsm()
{
const int line_len = sizeof(char) * 256;
memset(fsm[0], 0, line_len);
memset(fsm[1], 0, line_len);
memset(fsm[2], 2, line_len);
memset(fsm[3], 3, line_len);
memset(fsm[4], 3, line_len);
memset(fsm[5], 5, line_len);
memset(fsm[6], 5, line_len);
memset(fsm[7], 2, line_len);
memset(fsm[8], 8, line_len);
memset(fsm[9], 0, line_len);
fsm[0]['/'] = 1;
fsm[0]['"'] = 5;
fsm[1]['/'] = 2;
fsm[1]['*'] = 3;
fsm[1]['"'] = 5;
fsm[2]['\n'] = 9;
fsm[2]['\\'] = 7;
fsm[3]['*'] = 4;
fsm[4]['/'] = 9;
fsm[4]['*'] = 4;
fsm[5]['"'] = 0;
fsm[5]['\\'] = 6;
fsm[7]['\\'] = 7;
fsm[7]['\n'] = 8;
fsm[8]['\n'] = 9;
fsm[8]['\\'] = 7;
fsm[9]['/'] = 1;
fsm[9]['"'] = 5;
}
int main(int argc, char* argv[])
{
int state = 0;
unsigned char c;
std::string outStr;
FILE *fin = fopen(argv[1],"r");
if (fin == NULL)
{
printf("Fail to open input file!");
return 0;
}
FILE *fout = fopen(argv[2],"w");
Initfsm();
while(fscanf(fin,"%c",&c)!=EOF)
{
state = fsm[state][c];
outStr += c;
switch(state)
{
case 0:
fprintf(fout, "%s", outStr.c_str());
outStr = "";
break;
case 9:
outStr = "";
if(c == '\n')
{
fputc(c, fout);
}
break;
}
}
fclose(fin);
fclose(fout);
return 0;
}