Как лучше всего превратить эти вложенные строки в префиксной записи в кортежи?

Question

Мне бы хотелось общее решение для преобразования строк с префиксной нотацией в кортежи. Вот три примера ниже, которые иллюстрируют то, чего я надеюсь достичь. Каждая строка является элементом в списке (только во втором примере имеется более одного элемента).

['neg(or(p,q))']
['imp(p,q)', 'imp(neg(r),neg(q))']
['and(and(p,q),r)']

Становится

[('neg',('or','p','q'))]
[('imp','p','q'), ('imp',('neg','r'),('neg','q'))]
[('and',('and','p','q'),'r')]

В более общем смысле, желаемый формат: ('соединительный',' параметр ',' параметр '), где соединительными могут быть' и ',' или ',' iff ',' imp ',' neg '. Затем за каждым из них следуют два параметра, за исключением «neg», которое принимает только один. Параметры могут быть другими кортежами, как показано выше в примерах, которые демонстрируют вложенные формулы.

Другой способ взглянуть на это с помощью формул, которые мотивировали проблему в первую очередь.

Пример. 1 ((p ∧ q) ∨ (¬p ∧ ¬q)) в конечном итоге становится

[('or',('and','p','q'),('and',('neg','p'),('neg','q')))]

Пр. 2 (p → q), (¬r → ¬q) в конечном итоге становится

[('imp','p','q'), ('imp',('neg','r'),('neg','q'))]

То, что я пробовал:

import re

def tuplify(raw_sequent):

    first_split = re.split('\(', raw_sequent, 1)
    connective = first_split[0]
    second_split = re.split('\,', first_split[1])
    right_arg = second_split[-1]
    second_split = second_split[:-1]
    left_arg = ','.join(second_split)
    tup = (connective, left_arg, right_arg[:-1])

    return tup

Однако это вообще не обобщает, толькоработая для ввода

'and(and(p,q),or(r))'

Я полагаю, что решение может потребовать комбинации регулярных выражений и рекурсии.

Answer 1

Это решение с использованием Regex и String. Надеемся, что в комментариях объясняется, что происходит:

import re


def convert_to_tuple(text):
    """ Take an expression and convert it to tuple
      'neg(or(p,q))'  -->  ('neg', ('or', 'p', 'q'))
    """
    # used to extract not nested expression
    pattern = re.compile('(\w+)\(([^\(]*?)\)')
    # extract the index of the expression
    index_pattern = re.compile('#(\d+)#')
    # contains all expression extracted from the text
    expressions = []
    # you only need to extract most global expression only
    global_expressions = []


    def fix_expression(expression):
        """  a recursive solution to rebuild nested expression. """
        if isinstance(expression, str):
            # if the expression is like #index# return the correct expression else return this str expression
            m = index_pattern.search(expression)
            if m:
                return tuple(fix_expression(expressions[int(m.group(1))]))
            return expression
        # if the expression is a tuple extract all fixed nested expression in a tuple
        return tuple(fix_expression(subexp) for subexp in expression)


    def extract_expression(code):
        """ keep extracting nested expressions list,  """

        def add_exp(match):
            """ handle the match return by sub to save the expression and return its index."""
            expressions.append(None)
            index = len(expressions) - 1
            name, args = match.groups()

            if ',' in args:
                # if what is between parentheses contains ',' split is
                args = tuple(args.split(','))
            else:
                # args should always be a tuple to support unpacking operation
                args = (args,)

            # expression transformed to a tuple
            expressions[index] = (name, *args)
            return '#{}#'.format(index)

        while pattern.search(code):
            code = re.sub(pattern, add_exp, code)

        # for debuging string after removing all expression
        # print(code)


    # this extract all nested expression in the  text
    extract_expression(text)

    # Global expression there index is not used in any other expression
    # the last expression is for sure a global one because.
    global_expressions.append(expressions[-1])
    for i, exp in enumerate(expressions[:-1]):
        for other_exp in expressions[i + 1:]:
            if any('#{}#'.format(i) in sub_exp for sub_exp in other_exp):
                break
        else:
            # this expression is not used in any expression it's a global one
            global_expressions.append(exp)

    # for debugging
    # print(expressions)
    # print(global_expressions)

    return fix_expression(global_expressions[0])


print([convert_to_tuple(x) for x in ['neg(or(p,q))']])  # [('neg', ('or', 'p', 'q'))]
print([convert_to_tuple(x) for x in ['imp(p,q)', 'imp(neg(r),neg(q))']])  # [('imp', 'p', 'q'), ('imp', ('neg', 'r'), ('neg', 'q'))]
print([convert_to_tuple(x) for x in ['and(and(p,q),r)']])  # [('and', ('and', 'p', 'q'), 'r')]

Хитрость во вложенном выражении при использовании Regex заключается в том, что я использую re.sub, чтобы извлечь невложенное выражение сначала в список и замените его индексом. продолжайте делать это, пока нет выражения для извлечения. затем обработайте список извлеченных выражений, чтобы выполнить требуемое задание.

проверьте мой ответ на подобный вопрос, чтобы иметь четкую идею об этой технике:

Ответ для извлечения всех переменных изстрока кода Python (регулярное выражение или AST)

Answer 2

Короче рекурсивное решение с генератором:

import re
def to_tuple(d, stop=None):
   a = next(d, None)
   if a and a != stop:
      b = next(d, None)
      if b is None or b == stop:
        yield a
      else:
         if b == '(':
            yield (a, *to_tuple(d, stop=')'))
         else:
            yield from filter(None, [a, b])
         yield from to_tuple(d, stop=stop)

---

def format_input(_d):
   return iter(re.findall('\(|\)|\w+', _d))

n = [['neg(or(p,q))'], ['imp(p,q)', 'imp(neg(r),neg(q))'], ['and(and(p,q),r)']]
r = [[tuple(to_tuple(format_input(i)))[0] for i in k] for k in n]

Выход:

[[('neg', ('or', 'p', 'q'))], 
[('imp', 'p', 'q'), ('imp', ('neg', 'r'), ('neg', 'q'))], 
[('and', ('and', 'p', 'q'), 'r')]]

Answer 3

Следующий код

import re

OPERATORS_DIC = {'and': 2, 'or': 2, 'iff': 2, 'imp': 2, 'neg': 1}
EXPRESSIONS = [ 'neg(or(p,q))'
                , 'imp(p,q)'
                , 'imp(neg(r),neg(q))'
                , 'and(and(p,q),r)' ]

def digest(expression):
    """expression is an expression that should be recursively digested
    """
    for op in OPERATORS_DIC:
        match = re.search( op + '\((.*)\)', expression )
        if not match:
            continue
        inside = match.groups()[0]
        # examples: inside is 'p,q' or 'p,neg(q)', or 'p,neg(and(q,r))'
        if OPERATORS_DIC[op] == 1:
            return (op, digest(inside))
        # else we try to get the two arguments by counting parentheses
        for k in range(len(inside)):
            if inside[k] != ',':
                continue
            before, after = inside[:k], inside[k+1:]
            if ( before.count('(') == before.count(')') and
                 after .count('(') == after .count(')') ):
                return (op, digest(before), digest(after))
    return expression


for expr in EXPRESSIONS:
    print('{} -> {}'.format(expr, digest(expr)))

дает:

neg(or(p,q)) -> ('neg', ('or', 'p', 'q'))
imp(p,q) -> ('imp', 'p', 'q')
imp(neg(r),neg(q)) -> ('imp', ('neg', 'r'), ('neg', 'q'))
and(and(p,q),r) -> ('and', ('and', 'p', 'q'), 'r')

Таким образом, необходимый выход для ввода EXPRESSIONS равен

[ digest(expr) for expr in EXPRESSIONS ]

Answer 4

Ваша проблема подходит для рекурсивного решения:

def tuplify(raw_sequent):
    numOpen = 0
    numClose = 0

    startBracket = 0
    stopBracket = 0
    for i in raw_sequent:
        if i == "(":
            numOpen += 1

        if i == ")":
            numClose += 1

        if numOpen == 0:
            startBracket += 1
            stopBracket += 1
        elif numOpen > numClose:
            stopBracket += 1

    begin = raw_sequent[:startBracket]
    middle = raw_sequent[startBracket+1:stopBracket]
    end = raw_sequent[stopBracket+1:]

    result = []
    if len(begin) > 0:
        result += [i for i in begin.split(",") if len(i) > 0]

    if len(middle) >0:
        result.append(tuplify(middle))

    if len(end) > 0:
        result.append(tuplify(end))

    return tuple(result)