基于有限状态机的多项式输入实现

相信大家在没有老师提示使用正则表达式进行多项式匹配的时候，首先想到的方法是逐个字符去处理输入的字符串，从而把多项式和每个多项式中的项给分离出来。我在C语言的程序中也是这样实现的。在实现的过程中，我发现，依次读入每个字符进行判断的过程是不断重复，格式固定的。所以，想到了在计算机组成原理课程中学到的有限状态机思想。

 

我们观察下面的式子：

这个式子基本能代表了第一次作业要求中最一般的情况。

我们首先观察这个式子，其实可以对式子分割成更普适的形式。在式子最前面添加一个“+”号后，整个式子被分割成了两个形式相同的多项式的和。这两个式子分别是：

最前面的符号代表整个多项式的符号，然后 { } 包住了多项式中所有的项，( ) 包住的了系数和指数。在这里我发现带符号去处理的话太过繁琐，所以我们先忽略符号去处理。整个读取过程可以被划分为四个阶段：

       waitBig：等待大括号阶段。是初始阶段，等待输入一个“ { ”，然后进入对多项式每个项的处理；

       waitSmall：等待小括号阶段。当输入一个“ { ”后进入，此时需要等待输入“ ( ”或“ } ”，前者进入对项内系数和指数的处理，后者退出对多项式每个项的处理，重新开始等待输入下一个多项式；

       readXiShu： 读入系数阶段。当输入一个“ ( ”后进入，此时开始输入系数，直到遇见“ , ”；

       readZhiShu：读入指数阶段。当系数读取完毕后，可以检测到“ , ”，此时开始输入指数，直到遇到一个“)”；

（请大家忽略我的渣渣英语水平只能无奈部分使用拼音命名状态/(ㄒoㄒ)/~~）

 

状态转移图如下：

下面是对符号的处理，我们重新来看刚刚的式子

可以发现控制多项式的符号所在的位置都在大括号 { } 的外面，可以由状态转移图发现，此时的状态都是waitBig阶段，所以可以设置一个标志变量，来存储当前读入中的多项式的正负。当检测到正负号的输入时，判断当前阶段，如果阶段是waitBig，则修改标志变量为读入的符号。同理可以实现对系数正负的控制。

 

最后是存储的实现。笔者使用数组来存储多项式的每一项，数组的下标代表的是指数，数组元素存储的是指数对应的系数。在处于readZhiShu阶段读入到一个“ ) ”时，代表一个多项式的项输入完毕，此时可以将该项存储。多项式定义为一个结构，结构中包含一个存储项的数组。定义两个多项式结构，分别为duoXiangShi_SUM和duoXiangShi_ADD，分别用来存储多项式的和以及正在读入的多项式。在处于waitXiao阶段读入到一个“ } ”时，代表一个多项式读入结束，可以判断符号后用duoXiangShi_SUM加上（或减去）duoXiangShi_ADD，然后重置duoXiangShi_ADD。

 

以上是我采用有限状态机实现对多项式的输入。希望能有些帮助。