python - 尝试实现 DFA 但代码生成错误

Question

代码:-

#Shortest DFA implementation in Python
S,D,F=input()
s=1
for c in S:s=D[s,c]
print(["Not a chance!","Accepted!"][F&s>0])

输入:-输入是字符串 S、增量函数 D 和最终状态掩码 F 的三元组。我用 2 的幂对每个状态进行编号，因此 F 只是每个接受状态的或。 D 是来自 (state,input char) -> state 的映射。

示例输入(接受所有以 b 结尾的字符串):

'abab',{(1,'a'):1,(1,'b'):2,(2,'a'):1,(2,'b'):2},2

输出:-

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-32-506f09a31940> in <module>()
      1 #Shortest DFA implementation in Python
----> 2 S,D,F=input()
      3 s=1
      4 for c in S:s=D[s,c]
      5 print(["Not a chance!","Accepted!"][F&s>0])

ValueError: too many values to unpack (expected 3)

同样，下面的代码是实现一个NFA。但它会抛出另一种错误，即使在添加 eval() 之后也是如此。代码如下:-

#Shortest NFA implementation
S,D,F=eval(input())
s=1
for c in S:
 t,s=s,0
 for a,b in D[c]:s|=t/a%2*b
print(["Not a chance!","Accepted!"][F&s>0])

输入:-我们像以前一样将状态编号为 2 的幂。 D 是从输入字符到由该字符标记的转换列表的映射。

示例输入(接受所有以 b 结尾的字符串):

'abab',{'a':[(1,1)],'b':[(1,1),(1,2)]},2

得到的输出是:-

'abab',{'a':[(1,1)],'b':[(1,1),(1,2)]},2
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-34-7e5418d2d6fc> in <module>()
      4 for c in S:
      5  t,s=s,0
----> 6  for a,b in D[c]:s|=t/a%2*b
      7 print(["Not a chance!","Accepted!"][F&s>0])

TypeError: unsupported operand type(s) for |=: 'int' and 'float'

请告诉我上述代码中所需的必要但最少的修改，以便它成功执行并产生所需的输出。

Answer 1

此代码在 Python 2 中有效，但在 Python 3 中无效。我怀疑当您使用 Python 3 时，该代码实际上是为 Python 2 设计的。input在 Python 2 中，不仅从输入中读取字符串，而且还执行 eval语句，这意味着它将获取字符串并将其转换为 Python 语法。 input在 Python 3 中返回您输入的字符串。eval 不再像您在 Python 2 中看到的那样执行。要模仿您在 Python 2 中看到的内容，您需要运行 eval 在 input 之上:

In [1]: S,D,F = eval(input())
'abab',{(1,'a'):1,(1,'b'):2,(2,'a'):1,(2,'b'):2},2

In [2]: S
Out[2]: 'abab'

In [3]: D
Out[3]: {(1, 'a'): 1, (1, 'b'): 2, (2, 'a'): 1, (2, 'b'): 2}

In [4]: F
Out[4]: 2

编辑

对于您正在运行的新代码，罪魁祸首是循环中的除法运算:t/a。这默认返回一个 float ，而在 Python 2 中，如果 t 和 a 都是整数，它将返回一个整数。在 Python 3 环境中运行 Python 2 代码时必须小心。只需将 t/a 包装在 int 调用中:int(t/a)。

In [7]: S,D,F=eval(input())
   ...: s=1
   ...: for c in S:
   ...:  t,s=s,0
   ...:  for a,b in D[c]:s|=int(t/a)%2*b
   ...: print(["Not a chance!","Accepted!"][F&s>0])
   ...:
'abab',{'a':[(1,1)],'b':[(1,1),(1,2)]},2
Accepted!

我最后要提醒您的是，在 Python 3 环境中运行 Python 2 代码时要格外小心。如果可能，请在为其设计的环境中运行代码。如果没有，这个有用的 Python 2 到 Python 3 习语比较指南应该有所帮助:http://python-future.org/compatible_idioms.html .特别是:

• 输入:http://python-future.org/compatible_idioms.html#input
• ... 最后是除法运算符:http://python-future.org/compatible_idioms.html#division