根据Python lis的逻辑连接优先级对操作数进行分组

Question

我的意见是：

['A', '&', 'B', '|', 'C', '|', '!', 'D', '^', 'E', '&', 'F']

它的操作数（A-F）和连接词的优先级取决于：

1. 哦！你知道吗
2. &
3. ^你知道吗
4. |你知道吗

我需要对项目进行分组，以便本例中的输出为：

[[['A', '&', 'B'], '|', 'C'], '|', [[['!', 'D'], '^', ['E', '&', 'F']]]]

所以第一个一元否定（！）已分组。然后是二元连词（&；），然后是异或（^），最后是分离词（|）。你知道吗

有没有一种简洁的方法可以用Python实现这一点？你知道吗

示例代码，应该可以完成工作，但不太整洁：

def grp(lst, operator='|'):
    i, l, r = 0, len(lst), []
    while i < l:
        item = lst[i]
        if item == operator:
            if item == '!':
                r.append([item, lst[i+1]])
            else:
                r[-1] = [r[-1], item, lst[i+1]]
            i+=1
        else:
            r.append(item)
        i+=1
    return r

lst = ['A', '&', 'B', '|', 'C', '|', '!', 'D', '^', 'E', '&', 'F']
print(grp(grp(grp(grp(lst, '!'), '&'), '^'), '|'))
# -> [[[['A', '&', 'B'], '|', 'C'], '|', [['!', 'D'], '^', ['E', '&', 'F']]]]

Answer 1

此解决方案概括了grp函数的思想，并且由于其递归结构，它只需要一次调用：

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']]]

请注意，parse函数本身并不知道关于二进制运算符的任何信息（除了为方便起见在此处添加的默认参数）。二元运算符及其优先级可以由第二个参数任意指定。在二进制运算符最后一次出现时拆分已解析的标记使分组左关联。（在第一次出现时拆分已解析的标记将使分组权限具有关联性，这不是通常的默认值，并且对于非交换运算符会产生意外的结果。）

Answer 2

我认为这是半整洁的。它又短又简单。 （虽然效率不高）

tokens = ['A', '&', 'B', '|', 'C', '|', '!', 'D', '^', 'E', '&', 'F']

# operators and number of operands they bind (one to the right, rest to the left):
ops = [ ('!',1), ('&',2), ('^',2), ('|',2) ]

def rindex(lst, x):
    return len(lst) - 1 - lst[::-1].index(x)

for op, n in ops:
    while True:
        try:
            i = rindex(tokens, op)
        except ValueError:
            break
        # "wrap" it:
        tokens[i-n+1 : i+2] = [ tokens[i-n+1 : i+2] ]

tokens
=> [[[['A', '&', 'B'], '|', 'C'], '|', [['!', 'D'], '^', ['E', '&', 'F']]]]

编辑：使用rindex，由@coproc提供。你知道吗