Рекурсивные математические операции с разбором строк - PullRequest
Новая
       38

Рекурсивные математические операции с разбором строк

0 голосов
/ 04 апреля 2019

Я хочу рекурсивно разобрать входную строку, чтобы решить математическую задачу.

Ввод задается в этой форме: 

(P1=[X=(0.6,3),Y=(0.4,-1)],P2=[X=(0.3,0),Y=(0.4,[Y1=(0.8,[X=(0.2,1),Y=(0.8,2)]),Y2=(0.2,3)]),Z=(0.3,2)],P3=[A=(1,1)])

Цель состоит в том, чтобы вычислить P1, P2 и P3 и найдите, кто имеет наибольшее значение.

Математическое решение этой проблемы будет примерно таким: 

P1 = 0.6 * 3 + 0.4 * (-1) = 1.4
P2 = 0.3 * 0 + 0.4 * ( 0.8 * (0.2 * 1 + 0.8 * 2) + 0.2 * 3) + 0.3 * 2 = 1.416
P3 = 1 * 1 = 1

Итак, P2 > P1 > P3

Выходные данные должны быть P2.

Это упрощенная проблема, поскольку внутри скобок может быть гораздо больше операций.

Я не знаю, как разделитьвходная строка с различными разделителями и как сделать это рекурсивно.

Я новичок в программировании и Python, но любая помощь будет признательна.

1 Ответ

0 голосов
/ 09 апреля 2019

Написание рекурсивного парсера довольно амбициозно для новичка в программировании.Лучшая практика при написании любого синтаксического анализатора - начинать с написания BNF (что означает «форма Бэкуса-Наура»), который служит планом того, какими будут биты синтаксического анализатора.ДЕЛАЙТЕ ЭТО ДО ПЕРЕД НАПИСАНИЕМ ЛЮБОГО КОДА.Написание кода и проектирование синтаксических анализаторов - это очень разные мыслительные действия - проектирование синтаксического анализатора включает в себя множество сопоставлений с образцом и, в случае рекурсивного синтаксического анализатора, идентификацию вложенности выражений.Ваш BNF не должен быть формальным или строгим, если вы продумываете, как части будут переходить от одного к другому.

Вот BNF для вашего синтаксиса: 

number ::= an int or float numeric literal
identifier ::= an alphabetic character, followed by zero or more digits

factor_part ::= number | terms
factors ::= '(' factor_part (',' factor_part)... ')'

ident_factor ::= identifier '=' factors
terms ::= '[' ident_factor (',' ident_factor)... ']'

ident_term ::= identifier '=' terms
parser ::= '(' ident_term (',' ident_term)... ')'

BNF обычно начинаются сверху и работают вниз, иногда я работаю задом наперед.

Вот пошаговое преобразование из преобразования BNF в Python: 

import pyparsing as pp

# we'll need a function analogous to the sum built-in for doing product
def product(values):
    ret = values[0]
    for v in values[1:]:
        ret *= v
    return ret

# symbols useful during parsing - suppress them from the output, since we
# just want the parsed and computed values
EQ, LPAR, RPAR, LBRACK, RBRACK = map(pp.Suppress, "=()[]")

# start converting the BNF to pyparsing expressions
# numeric literal from pyparsing's predefined exprs in pyparsing_common
# includes an attached parse action to convert parsed string to int or float,
# so we won't have to do that later
number = pp.pyparsing_common.number().setName("number")
ident = pp.Word(pp.alphas.upper(), pp.nums).setName("identifier")

# define placeholders for recursive elements
terms = pp.Forward().setName("terms")
factors = pp.Forward().setName("factors")

# insert grammar definitions for each - use '<<=' instead of '=' so we
# don't replace the Forward expressions, but insert the definitions into them
factor_part = number | terms
factors <<= LPAR + pp.delimitedList(factor_part) + RPAR

# when we evaluate factors, the identifiers are not used, we can suppress them
ident_factor = pp.Suppress(ident + EQ) + factors
terms <<= LBRACK + pp.delimitedList(ident_factor) + RBRACK

# add parse actions to do calculations - terms get added, factors get multiplied
terms.addParseAction(sum)
factors.addParseAction(product)

# finally define an overall expression for the sequence (P1=[...], P2=[...],
# etc.) and return as a dict
ident_term = ident + EQ + terms
parser = LPAR + pp.Dict(pp.delimitedList(pp.Group(ident_term))) + RPAR


# try parsing the given input string:
a = """(P1=[X=(0.6,3),Y=(0.4,-1)],
        P2=[X=(0.3,0),
            Y=(0.4,
               [Y1=(0.8,
                    [X=(0.2,1),Y=(0.8,2)]
                    ),
                Y2=(0.2,3)
               ]
               ),
            Z=(0.3,2)
            ],
        P3=[A=(1,1)])"""

try:
    print(parser.parseString(a).asDict())
except Exception as e:
    print(pp.ParseException.explain(e))

Дает: 

{'P3': 1, 'P1': 1.4, 'P2': 1.416}
...