Linux C 编程技巧--利用有限状态机模型编程

常见的计算机就是使用有限状态机作为计算模型的：对于内存的不同状态，CPU通过读取内存值进行计算，更新内存中的状态。CPU还通过消息总线接受外部输入设备（如键盘、鼠标）的指令，计算后更改内存中的状态，计算结果输出到外部显示设备（如显示器），以及持久化存储在硬盘。

电脑游戏设计中也经常使用有限状态机模型。以水果忍者游戏为例，游戏中水果的状态是有限状态，其运行轨迹是由模拟物理运动规律的计算公式运算而成的，一个香蕉抛起来后会按照抛物线运行，其每一帧位置变化都是一个状态的改变，状态改变通过计算公式来决定。当然作为游戏不会仅仅这么简单，如果这么简单就是动画了，游戏还有复杂的人机交互事件，比如用手在屏幕上“切”了水果，水果感知到这个事件后，会按照程序逻辑进入爆炸状态。

 

简单知道其定义是没有用的，在C编程中我们改如何应用呢？

 

例题1：去除一个字符串中连续的空格，即 Ｈ＿＿ｅｌ＿＿＿ｌｏ　变成　Ｈ＿ｅｌ＿ｌｏ；

 

我们拿到这道题时，可能会想到用getchar()依次取字符，当遇到空格时，继续下一个字符是否为空格，如果是则删除，如果不是则继续；那么问题来了，如果空格后面还有空格呢？如果还有很多空格呢？如果还有其他要求呢？这样很容易造成思维混乱，所以这时我们可以用到有限状态机模型，好像这样说很模糊啊，该怎么使用呢？利用这种方式，最后的就是利用好flag,即标识符；这样吧，我们来画一下这个模型：

 

这样看好像有点抽象，我来解释一下：

状态0  (flag = 1)若当前字符是空格，输出并跳转到状态1(flag = 1),如果是非空格，则打印字符；

状态1  (flag = 1) 若当前字符为非空格，则输出并跳转到状态0，若是空格，则不打印；

下面几个例题我尽量写得清楚；

 

我们按照这种逻辑来写程序，看看是不是比较方便，代码如下：

 

#include <stdio.h>

int main(int argc, char *argv[])
{
	char flag = 0;
	int ch;
	while((ch = getchar()) != EOF)
	{
		switch(flag)
		{
		case 0:
			if(ch == ' ')
				flag = 1;
			putchar(ch);
			break;
		case 1:
			if(ch == ' ')
				continue;
			flag = 0;
			putchar(ch);
			break;
		default:
			break;
		}
	}
	return 0;
}

程序执行结果如下：

fs@ubuntu:~/qiang/char1$ gcc -o test test.c 
fs@ubuntu:~/qiang/char1$ ./test
H  el   lo
H el lo

效果很明显；

 

上面的例题还算简单吧，好像不用这个模型也可以是吧，那好，我们再来一题

 

例题2：除连续的空格但字符串中的连续空格不变，比如Ｈ_ _ｅｌ＿＿＂ｗｏｒ＿＿＿ｌｄ＂＿＿＿ｌｏ；

大家看看，如果直接写程序是不是很烦，一会就乱掉了，那我们还用这个模型来编写，还是先画图：

 

 

 

#include <stdio.h>

int main(int argc, char *argv[])
{
	char flag = 0;
	int ch;
	while((ch = getchar()) != EOF){
		switch(flag){
		case 0:
			if(ch == ' ')
				flag = 1;
			if(ch == '"')
				flag = 2;
			putchar(ch);
			break;
		case 1:
			if(ch != ' '){
				flag = 0;
				if(ch == '"')
					flag = 2;
				putchar(ch);
			}
			break;
		case 2:
			if(ch == '"')
				flag = 0;
			if(ch == '\"')
				ch = '"';
			putchar(ch);
			break;
		default:
			printf("error!\n");
			break;
		}
	}
	return 0;
}

执行结果如下：

fs@ubuntu:~/qiang/char1$ ./char3
H  el  "wor   ld"   lo
H el "wor   ld" lo

 

来个实际点的问题：

例题３：:除单行注释

示例程序：

 

/*****This is a program!*****/
#include <stdio.h>

int main()
{
	printf("Hello world!\n");//Hello world!
}

将这段程序中的单行注释去掉，继续画图：

 

编写程序如下：

#include <stdio.h>

int main(void)
{
	char flag = 0;
	char ch;
	while((ch = getchar()) != EOF)
	{
		switch(flag)
		{
		case 0:
			if(ch == '/')
				flag = 1;
			else
				putchar(ch);
			break;
		case 1:
			if(ch == '/'){
				flag = 2;
			}
			else{
				putchar('/');
				putchar(ch);
			}
			break;
		case 2:
			if(ch == '\n')
			{
				flag = 0;
				putchar(ch);
			}
			break;
		default:
			break;
		}

	}
}

执行命令：

fs@ubuntu:~/qiang/char1$ ./quzhushi1 < test.c >result.c

注意命令中用到的重定向，将test.c文件重定向到quzhushi1 中，输出结果重定向到 result.c中

 

可查看result.c中：

/*****This is a program!*****/
#include <stdio.h>

int main()
{
	printf("Hello world!\n");
}

单行注释被删除。

 

例题4：去除单行注释和多行注释

     还是这个测试程序：

/*****This is a program!*****/
#include <stdio.h>

int main()
{
	printf("Hello world!\n");//Hello world!
}

好吧，继续画图，图上比较抽象，大家可以自己思考一下

这次比较复杂，要有5个标识符

 

测试代码如下：

#include <stdio.h>

int main()
{
	char ch;
	int flag = 0;
	while((ch = getchar()) != EOF)
	{
		switch(flag)
		{
			case 0:
				if(ch == '/')
					flag = 1;
				else
					putchar(ch);
				break;
	
			case 1:
				if(ch == '/')
					flag = 2;
				else if(ch == '*')
					flag = 3;
				else
				{
					flag = 0;
					putchar('/');
					putchar(ch);
				}
				break;
		
			case 2:
				if(ch == '\n')
				{
					putchar(ch);
					flag = 0;
				}
				break;

			case 3:
				if(ch == '*')
					flag = 4;
				break;

			case 4:
				if(ch == '/')
					flag = 0;
				else
					flag = 3;
				break;
		}
	}
}

执行命令：

fs@ubuntu:~/qiang/char1$ ./quzhushi < test.c >result.c

执行结果：

result.c

#include <stdio.h>

int main()
{
	printf("Hello world!\n");
}

大家可以比较画的图与所写程序，这种方法可以使我们编写程序时有个很好的思路！