Évaluer la chaîne en correspondant les parenthèses

Question

Quel serait le meilleur moyen de traduire de manière programmatique une chaîne comme

"((abc&(def|ghi))|jkl)&mno"

pour être exécutée comme suit :

if ((func('abc') and (func('def') or func('ghi'))) or func('jkl')) and func('mno'):
    return True

J'ai l'impression qu'il doit y avoir un moyen simple d'y parvenir, mais je n'arrive pas à comprendre.

Answer 1

Eh bien, vous pouvez l'analyser avec des expressions régulières simples en remplaçant les correspondances au besoin, si votre chaîne n'est pas plus compliquée que ce que vous montrez (par exemple, est uniquement composée de ces symboles plus des lettres/chiffres). Ensuite, vous pouvez simplement utiliser eval() pour l'exécuter en tant que code python.

Par exemple:

import re

def func(x):
    # juste un exemple...
    return True

s = "((abc&(def|ghi))|jkl)&mno"

s = re.sub(r'(\w+)', r"func('\1')", s)
s = s.replace('&', ' and ')
s = s.replace('|', ' or ')

print(s)
print(eval(s))

Sortie:

((func('abc') and (func('def') or func('ghi'))) or func('jkl')) and func('mno')
True

Answer 2

Ceci est un problème intéressant, avec plusieurs couches pour une solution.

Tout d'abord, étant donné cet exemple, vous avez besoin d'un analyseur syntaxique d'infixes de base. En pyparsing, il y a une méthode d'aide intégrée infixNotation. Plusieurs exemples de pyparsing montrent comment analyser une expression booléenne en utilisant infixNotation. Voici un analyseur syntaxique qui analysera votre expression d'exemple :

import pyparsing as pp

terme = pp.Word(pp.alphas)
ET = pp.Literal("&")
OU = pp.Literal("|")
expr =  pp.infixNotation(terme,
                         [
                             (ET, 2, pp.opAssoc.LEFT,),
                             (OU, 2, pp.opAssoc.LEFT,),
                         ])

print(expr.parseString(sample).asList())

Pour votre exemple, cela affichera :

[[[['abc', '&', ['def', '|', 'ghi']], '|', 'jkl'], '&', 'mno']]

Vous pouvez voir que nous avons capturé non seulement l'expression, mais aussi le regroupement par parenthèses.

Nous pouvons commencer la conversion vers votre sortie souhaitée en ajoutant des actions d'analyse. Ce sont des rappels au moment de l'analyse que pyparsing appellera, pour remplacer les jetons analysés par une valeur différente (qui n'a pas besoin d'être une chaîne, pourrait être un nœud AST pour l'évaluation - mais dans ce cas, nous retournerons une chaîne modifiée).

ET.addParseAction(lambda: " et ")
OU.addParseAction(lambda: " ou ")
terme.addParseAction(lambda t: "fonc('{}')".format(t[0]))
expr.addParseAction(lambda t: "({})".format(''.join(t[0]))

Les actions d'analyse peuvent être des méthodes avec diverses signatures :

fonction()
fonction(jetons)
fonction(emplacement, jetons)
fonction(chaine_d'entrée, emplacement, jetons)

Pour ET et OU, nous devons simplement remplacer les opérateurs analysés par leurs mots-clés correspondants "et" et "ou". Pour les termes variables analysés, nous voulons changer "xxx" en "fonc(xxx)", nous écrivons donc une action d'analyse qui prend les jetons analysés, et retourne une chaîne modifiée.

L'action d'analyse pour expr est intéressante car elle prend simplement le contenu analysé, les rassemble en utilisant ''.join(), puis les enveloppe dans des (). Comme expr est en fait une expression récursive, nous verrons qu'il effectue l'enrobage approprié dans () à chaque niveau dans la liste imbriquée analysée.

Après avoir ajouté ces actions d'analyse, nous pouvons essayer d'appeler à nouveau parseString(), maintenant en donnant :

["(((fonc('abc') et (fonc('def') ou fonc('ghi'))) ou fonc('jkl')) et fonc('mno'))"]

En se rapprochant!

Pour mettre en forme dans votre déclaration if souhaitée, nous pouvons utiliser une autre action d'analyse. Mais nous ne pouvons pas attacher cette action d'analyse directement à expr, puisque nous avons vu que expr (et son action d'analyse associée) sera analysé à tous les niveaux d'imbrication. Nous pouvons donc créer une version "externe" de expr, qui est simplement une expression conteneur d'une expr:

expr_externe = pp.Group(expr)

L'action d'analyse est similaire à ce que nous avons vu pour expr, où nous retournons une nouvelle chaîne en utilisant les jetons d'entrée:

def format_expression(jetons):
    return "si {}:\n    retourner Vrai".format(''.join(jetons[0]))

expr_externe.addParseAction(format_expression)

Maintenant nous utilisons expr_externe pour analyser la chaîne d'entrée:

print(expr_externe.parseString(sample)[0])

Obtenir:

si (((fonc('abc') et (fonc('def') ou fonc('ghi'))) ou fonc('jkl')) et fonc('mno')):
     retourner Vrai

(Il pourrait y avoir un ensemble supplémentaire de () sur cette valeur, ils pourraient être supprimés dans l'action d'analyse pour expr_externe si désiré.)

Version finale de l'analyseur (décommentez les instructions d'impression intermédiaire pour voir la progression de la fonctionnalité de l'analyseur) :

sample = "((abc&(def|ghi))|jkl)&mno"

import pyparsing as pp

terme = pp.Word(pp.alphas)
ET = pp.Literal("&")
OU = pp.Literal("|")
expr =  pp.infixNotation(terme,
                         [
                             (ET, 2, pp.opAssoc.LEFT,),
                             (OU, 2, pp.opAssoc.LEFT,),
                         ])

# print(expr.parseString(sample).asList())

ET.addParseAction(lambda: " et ")
OU.addParseAction(lambda: " ou ")
terme.addParseAction(lambda t: "fonc('{}')".format(t[0]))
expr.addParseAction(lambda t: "({})".format(''.join(t[0])))

# print(expr.parseString(sample).asList())

def format_expression(jetons):
    return "si {}:\n    retourner Vrai".format(''.join(jetons[0]))

expr_externe = pp.Group(expr).addParseAction(format_expression)
print(expr_externe.parseString(sample)[0])