1. 完成课程讲义中状态机的实现：
(1) 累加器 Accumulator
例子：列表[-1, 2, 3, -2, 5, 6]中的数字相加，我们得到和是 13。
output = Accumulator().transduce([-1,2,3,-2,5,6]) #output=[-1, 1, 4, 2, 7, 13]
(2) 二进制相加 Binary_Addition
例子：011 和 001 相加我们得到 100。
output = Binary_Addition().transduce([(1,1),(1,0),(0,0)]) #output=[0, 0, 1]
(3) 反向器 Reverser
实现一个反向器，逆向输出一个序列。输入的形式如下：
sequence1 + [‘end’] + sequence2
其中 sequence1 是字符串列表，‘end’表示 sequence1 的终结，sequence2 为任意序列。反向器的作用如下：当 sequence1 里的每个元素输入时，反向器输出 None。当[‘end’]和 sequence2 的每个元素输入时，反向器依次反向输出 sequence1 中的元素；当没有元素输出时，则输出 None。
例子：
output = Reverser().transduce([‘foo’,’ ', ‘bar’] + [‘end’] + list(range(5))) #output = [None, None, None, ‘bar’, ’ ', ‘foo’, None, None, None]
解释：输出中前三个 None 为输入 sequence1 时输出。从输入‘end’开始，sequence1 中的元素开始反向输出。sequence1 输出完毕后，继续输出 None。（即输入 list(range(5))中的 2，3，4 时）。
更多测试例子：
①output=Reverser().transduce([‘foo’, ’ ', ‘bar’] + [‘end’] + [‘end’]*3+list(range(2))) #output = [None, None, None, ‘bar’, ’ ', ‘foo’, None, None, None] ②output = Reverser().transduce(list(‘the’) + [‘end’] + list(range(3))) #output = [None, None, None, ‘e’, ‘h’, ‘t’, None] ③output=Reverser().transduce([] + [‘end’] + list(range(5))) #output = [None, None, None, None, None, None] ④output=output=Reverser().transduce(list(‘nehznehS evol I’) + [‘end’]+ list(range(15))) #output = [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, ‘I’, ’ ', ‘l’, ‘o’, ‘v’, ‘e’, ’ ', ‘S’, ‘h’, ‘e’, ‘n’, ‘z’, ‘h’, ‘e’, ‘n’, None]
实现要求：
（1） 不同的状态机子类继承父类 SM；
（2） 补充父类的 transduce 函数，子类不能重写 transduce 函数；
（3） 补充每个子类的 transition_fn 和 output_fn 函数，其中累加器的实现代码如下：
class Accumulator(SM): start_state = 0 def transition_fn(self, s, x): return s + x def output_fn(self, s): return s
建议：利用累加器的代码实现父类的 transduce 函数，再实现二进制相加和反向器的 transition_fn 和 output_fn 函数。
【解题思路】
①定义状态机：
首先定义一个状态机，设置初始状态用于传递运行状态。然后定义初始状态转移函数与输出函数。只在父类中定义基本的方法即可，并只需实现状态转移的transduce方法即可，其他方法在子类中实现即可。
②定义累加器类：
累加器类是继承于状态机类的子类。对于累加器类，可以根据下一状态都等于上一状态加上传入的参数的特性编写状态转移函数。对于输出函数，只需直接返回累加完的当前状态表示结果即可。
③定义二进制加法类：
二进制加法类是继承于状态机类的子类。对于二进制加法类，采取一个元组表示当前状态值，元组的第一个元素表示进位值，即记录低一位是否产生进位。元组的第二个元素表示已经计算的当前结果，由于二进制是逆序存储的，故对于每次加法，只需将计算出来的结果append到列表的结尾即可。
对于每次加法，一共有4种可能情况，穷举4种情况，依次进行判断即可。
最后的输出函数，需要再对最终是否产生进位进行一次判断，如果不产生进位，则直接返回元组的第二个参数即可；如果产生进位，则先执行append(1)后，再返回元组的第二个元素即可。
④定义反相器：
反相器类是继承于状态机类的子类。对于反相器类，采取的方法是记录‘end’的位置，最后统一进行计算的方法。状态值是一个四元元组分别表示是否结束，len的位置，seq1的长度和已经输入的列表。在输出中直接处理即可。
【编程实现】
# 定义状态机 class StateMachine: def __init__(self): self.start_state = None # default start state def transition_fn(self, s, x): pass def output_fn(self, s): pass def transduce(self, input_seq): for i in range(len(input_seq)): self.start_state = self.transition_fn(self, self.start_state, input_seq[i]) print(self.output_fn(self, self.start_state)) # 定义累加器 class Accumulator(StateMachine): start_state = 0 def transition_fn(self, s, x): return s + x def output_fn(self, s): return s # 定义二进制相加器 class Binary_Addition(StateMachine): start_state = (0, []) # (carry,digit) def transition_fn(self, s, x): temp = s[1] # 分情况判断进位 if s[0] + x[0] + x[1] == 3: temp.append(1) s = (1, temp) elif s[0] + x[0] + x[1] == 2: temp.append(0) s = (1, temp) elif s[0] + x[0] + x[1] == 1: temp.append(1) s = (0, temp) else: temp.append(0) s = (0, temp) return s def output_fn(self, s): # 判断最高位进位 if s[0] == 1: s[1].append(1) return s[1] # 定义反相器 class Reverser(StateMachine): start_state = (0, 0, 0, []) # isEnd,len(seq1),total lenth def transition_fn(self, s, x): # 不断刷新state中的值 temp = s[3] temp.append(x) if s[0] == 1: return 1, s[1], s[2] + 1, temp if x == 'end': return 1, s[1], s[2] + 1, temp else: return 0, s[1] + 1, s[2] + 1, temp def output_fn(self, s): # 循环获取输出 res = [] for i in range(s[2]): if i < s[1]: res.append(None) elif s[1] <= i <= 2 * s[1] - 1: res.append(s[3][2 * s[1] - 1 - i]) else: res.append(None) return res
首先定义状态机父类，定义构造函数，输出函数，状态转换函数，以及transduce函数。通过仔细观察几个输入样例，不难发现，输入的list中的项数跟需要操作的次数相同，因此可以直接使用循环循环插传入list的长度，然后调用输出函数即可。
累加器类是继承于状态机类的子类。对于累加器类，可以根据下一状态都等于上一状态加上传入的参数的特性编写状态转移函数。对于输出函数，只需直接返回累加完的当前状态表示结果即可。
二进制加法类是继承于状态机类的子类。对于二进制加法类，采取一个元组表示当前状态值，元组的第一个元素表示进位值，即记录低一位是否产生进位。元组的第二个元素表示已经计算的当前结果，由于二进制是逆序存储的，故对于每次加法，只需将计算出来的结果append到列表的结尾即可。对于每次加法，一共有4种可能情况，即产生进位与否，当前位是0还是1。依次进行判断即可。最后的输出函数，需要再对最终是否产生进位进行一次判断，如果不产生进位，则直接返回元组的第二个参数即可；如果产生进位，则先执行append(1)后，再返回元组的第二个元素即可。
反相器类是继承于状态机类的子类。对于反相器类，采取的方法是记录‘end’的位置，最后统一进行计算的方法。状态值是一个四元元组分别表示是否结束，len的位置，seq1的长度和已经输入的列表。在输出中直接处理即可。最后输出时，只需首先输出seq1的长度个None，然后依次进行反向输出，最后再补齐None即可。
【测试结果】
（1）累加器：
输入：
输出：
（2）二进制加法器：
输入：
输出：
（3）反相器：
①
输入：
输出：
②
输入：
输出：
③
输入：
输出：
④
输入：
输出：
[None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, ‘I’, ’ ', ‘l’, ‘o’, ‘v’, ‘e’, ’ ', ‘S’, ‘h’, ‘e’, ‘n’, ‘z’, ‘h’, ‘e’, ‘n’, None]
