利用状态机解决问题
概念
状态机是软件编程中的一个重要概念。比这个概念更重要的是对它的灵活应用。在一个思路清晰而且高效的程序中,必然有状态机的身影浮现。
比如说一个按键命令解析程序,就可以被看做状态机:本来在A状态下,触发一个按键后切换到了B状态;再触发另一个键后切换到C状态,或者返回到A状态。这就是最简单的按键状态机例子。进一步看,击键动作本身也可以看做一个状态机。一个细小的击键动作包含了:释放、抖动、闭合、抖动和重新释放等状态。
程序其实就是状态机
。
要素
状态机可归纳为4个要素,即现态
、条件
、动作
、次态
。这样的归纳,主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因,“动作”和“次态”是果。详解如下:
- 现态:是指当前所处的状态。
- 条件:又称为“事件”。当一个条件被满足,将会触发一个动作,或者执行一次状态的迁移。
- 动作:条件满足后执行的动作。动作执行完毕后,可以迁移到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态。
4.次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”一旦被激活,就转变成新的“现态”了。
如果我们进一步归纳,把“现态”和“次态”统一起来,而把“动作”忽略(降格处理),则只剩下两个最关键的要素,即:状态
、迁移条件
。
表示
状态机的表示方法有许多种,我们可以用文字、图形或表格的形式来表示一个状态机。
纯粹用文字描述是很低效的,所以就不介绍了。接下来先介绍图形的方式。
状态迁移图(STD)
状态迁移图(STD),是一种描述系统的状态、以及相互转化关系的图形方式。状态迁移图的画法有许多种,不过一般都大同小异。我们结合一个例子来说明一下它的画法,如图1所示。
- 状态框:用方框表示状态,包括所谓的“现态”和“次态”。
- 条件及迁移箭头:用箭头表示状态迁移的方向,并在该箭头上标注触发条件。
- 节点圆圈:当多个箭头指向一个状态时,可以用节点符号(小圆圈)连接汇总。
- 动作框:用椭圆框表示。
- 附加条件判断框:用六角菱形框表示。
状态迁移图和我们常见的流程图相比有着本质的区别,具体体现为:在流程图中,箭头代表了程序PC指针的跳转;而在状态迁移图中,箭头代表的是状态的改变
。
实践
利用状态机实现去除C/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;
}