擅长:python、mysql、java
<p>此解决方案概括了<code>grp</code>函数的思想,并且由于其递归结构,它只需要一次调用:</p>
<pre><code>def lastIndex(lst, x):
return len(lst) - 1 - lst[::-1].index(x)
def parse(l, binOps=('|', '^', '&')):
assert len(l) > 0, "malformed input"
if len(l) == 1:
assert l[0] != '!' and not l[0] in binOps, "malformed input"
return l[0]
if len(binOps) > 0:
binOp = binOps[0]
try:
opPos = lastIndex(l, binOp) # for left-associativity of binary operators
return [parse(l[:opPos], binOps), binOp, parse(l[opPos+1:], binOps[1:])]
except ValueError:
return parse(l, binOps[1:])
assert l[0] == '!', "malformed input"
return ['!', parse(l[1:], binOps)]
parse(['A', '&', 'B', '|', 'C', '|', '!', 'D', '^', 'E', '&', 'F'])
# -> [[['A', '&', 'B'], '|', 'C'], '|', [['!', 'D'], '^', ['E', '&', 'F']]]
</code></pre>
<p>请注意,parse函数本身并不知道关于二进制运算符的任何信息(除了为方便起见在此处添加的默认参数)。二元运算符及其优先级可以由第二个参数任意指定。在二进制运算符最后一次出现时拆分已解析的标记使分组左关联。(在第一次出现时拆分已解析的标记将使分组权限具有关联性,这不是通常的默认值,并且对于非交换运算符会产生意外的结果。)</p>