Python:应用操作的数学顺序，按照括号中的层次结构重新排序字符串

Question

如何使用Python重新排序字符串，应用带括号的数学操作顺序？

让我举一个例子：

"son(father(granpa)mother))" ===> "granpa father mother son"

其思想是使用标准数学顺序操作重新排序原始字符串。在数学顺序操作中，括号具有最高优先级。让我用一个数学例子：

4 + (5 + (3 + 3)) = ((3 + 3) + 5 ) + 4 = 3 + 3 + 5 + 4 = 14

编辑：这个示例使用的仅仅是+，因为python总是在+之前做*，在相同的括号级别上，这不是重点，重点是字符串中的顺序，因为它只会将结果重新排序。

目标是重新排序包含变量的字符串，以研究操作的可定位优化。我想重新排序的字符串示例：

def xor_with_nands(a,b):
  return f"~(~(~({a} & {b}) & {a}) & ~(~({a} & {b}) & {b}))"

>> xor_with_nands(0,1)
>> ~(~(~(0 & 1) & 0) & ~(~(0 & 1) & 1))
>> eval(xor_with_nands(0,1))
>> 1

如果有一种方法可以根据括号的数学顺序(只是括号，而不是其他数学操作顺序)重新排序字符串，则可以分析某些过程中的优化。

我们的目标是获得一个可视化嵌套逻辑操作的工具，按照执行顺序来直观地理解它们，并希望能够简化它们。

结论：分流场算法是惊人的。非常感谢!

Answer 1

您正在寻找一个分流场算法。

这将将您的数学表示法(也称为infix表示法)转换为计算机可以轻松处理的格式(称为后缀符号)。参见这里：算法获得更好的描述。

本质上，该算法将把表达式转换为已正确排序的队列。

以下是取自Brilliant.org的一些伪码

1.  While there are tokens to be read:
2.        Read a token
3.        If it's a number add it to queue
4.        If it's an operator
5.               While there's an operator on the top of the stack with greater precedence:
6.                       Pop operators from the stack onto the output queue
7.               Push the current operator onto the stack
8.        If it's a left bracket push it onto the stack
9.        If it's a right bracket 
10.            While there's not a left bracket at the top of the stack:
11.                     Pop operators from the stack onto the output queue.
12.             Pop the left bracket from the stack and discard it
13. While there are operators on the stack, pop them to the queue

这将允许您定义自定义运算符和定义它们的优先级。

Answer 2

在这里，我使用了一种递归的方法来处理字符串逐个字符。它不是很有效率，但它能完成任务。

def tokenize_parentheticals(s, idx=None):
    # first, use a single-element list as essentially a 'mutable integer'
    # that we can pass up and down the chain of recursive calls to never
    # move backwards in the string
    if idx is None:
        idx = [0]
    # the start of each token is the character at the beginning of the string.
    start = idx[0]
    # We will store all tokens in each 'layer' and yield them all at the
    # end of the layer
    tokens = []
    # count through the string character by character, and look for either
    # an open-paren or a close-paren
    while idx[0] < len(s):
        c = s[idx[0]]
        idx[0] += 1
        # if we encounter an open-paren, then 
        #   (1) terminate the current token and add it to our list
        #   (2) recurse inside the next set of parentheses
        # once we return from the recursion, update the start of the next 
        # token to the character after the most recent close-paren
        if c == '(':
            tokens.append(s[start:idx[0] - 1])
            yield from tokenize_parentheticals(s, idx)
            start = idx[0]
        # If we encounter a close-paren, then
        #   (1) terminate the current token and add it to our list
        #   (2) un-recurse, go up a level
        elif c == ')':
            tokens.append(s[start:idx[0] - 1]
            break
    # before exiting, yield all non-empty tokens
    yield from (t for t in tokens if t)


inp = "son(father(granpa)mother))"
' '.join(tokenize_parentheticals(inp))
# 'granpa father mother son'

list(tokenize_parentheticals('4 + (5 + (3 + 3))'))
# ['3 + 3', '5 + ', '4 + ']

list(tokenize_parentheticals(xor_with_nands(0, 1)))
# ['0 & 1', '~', ' & 0', '0 & 1', '~', ' & 1', '~', ' & ~', '~']

免责声明:我写了这个答案，没有阅读你的问题的编辑和你对此的实际用途。这可能不是一个足够强大的解决方案来满足您的需要。根据需要定制。

Answer 3

这可能会有帮助：

from collections import defaultdict
import re

def sort_terms(s, ops = ''):
    d = defaultdict(list)
    depth = 0
    pattern = r'[()]|[^( )' + ops + ']+'
    for item in re.findall(pattern,s):
        if item == '(':
            depth += 1
        elif item == ')':
            depth -= 1
        else:
            d[depth].append(item)
    terms = []
    for depth in sorted(d.keys(),reverse = True):
        terms.extend(d[depth])
    return terms

示例：

>>> sort_terms("son(father(granpa)mother))")
['granpa', 'father', 'mother', 'son']
>>> sort_terms('4 + (5 + (3 + 3))','+')
['3', '3', '5', '4']
>>> '+'.join(sort_terms('4 + (5 + (3 + 3))','+'))
'3+3+5+4'
>>> sort_terms('~(~(~(0 & 1) & 0) & ~(~(0 & 1) & 1))','~&')
['0', '1', '0', '1', '0', '1']

运算符本身被去掉，但在问题本身中，您表示只想注意括号。