Analyser une expression booléenne

1106. Analyser une expression booléenne

Difficulté : Difficile

Sujets : Chaîne, Pile, Récursion

Une expression booléenne est une expression qui est évaluée comme vraie ou fausse. Il peut prendre l'une des formes suivantes :

• 't' qui est évalué à vrai.
• 'f' qui est évalué à faux.
• '!(subExpr)' qui s'évalue à le NON logique de l'expression interne subExpr.
• '&(subExpr₁, subExpr₂, ..., subExpr_n)' qui s'évalue à le ET logique de l'intérieur expressions subExpr₁, subExpr₂, ..., subExpr_n où n >= 1.
• '|(subExpr₁, subExpr₂, ..., subExpr_n)' qui s'évalue à le OU logique de l'intérieur expressions subExpr₁, subExpr₂, ..., subExpr_n où n >= 1.

Étant donné une expression de chaîne qui représente une expression booléenne, renvoie l'évaluation de cette expression.

Il est garanti que l'expression donnée est valide et suit les règles données.

Exemple 1 :

• Entrée : expression = "&(|(f))"
• Sortie : faux
• Explication :
  • Tout d'abord, évaluez |(f) ---> f. L'expression est maintenant "&(f)".
  • Ensuite, évaluez &(f) ---> f. L'expression est désormais "f".
  • Enfin, retournez false.

Exemple 2 :

• Entrée : expression = "|(f,f,f,t)"
• Sortie : vrai
• Explication : L'évaluation de (faux OU faux OU faux OU vrai) est vraie.

Exemple 3 :

• Entrée : expression = "!(&(f,t))"
• Sortie : vrai
• Explication :
  • Tout d'abord, évaluez &(f,t) ---> (faux ET vrai) ---> faux ---> f. L'expression est maintenant "!(f)".
  • Ensuite, évaluez !(f) ---> PAS faux ---> vrai. Nous revenons vrai.

Contraintes :

• 1 <= expression.length <= 2 * 10⁴
• expression[i] est l'un des caractères suivants : '(', ')', '&', '|', '!', 't', 'f' et ','.

Indice :

1. Écrivez une fonction "parse" qui appelle les fonctions d'assistance "parse_or", "parse_and", "parse_not".

Solution :

Nous allons décomposer la solution en fonctions plus petites qui gèrent l'analyse et l'évaluation de différents types d'expressions : parse_or, parse_and, parse_not et une fonction d'analyse principale qui gère l'analyse récursive de l'expression. Nous utiliserons une pile pour suivre les expressions imbriquées et les évaluer étape par étape.

Approche:

1. Analyse et récursivité :

   • Utilisez une pile pour garder une trace des expressions lorsque vous rencontrez des parenthèses imbriquées.
   • Traitez les caractères de manière séquentielle et gérez la pile pour les évaluations imbriquées.
   • Lorsque vous rencontrez une parenthèse fermante), extrayez le dernier ensemble d'expressions et appliquez l'opération logique (&, | ou !).

2. Fonctions d'aide :

   • parse_or : évalue |(expr1, expr2, ..., exprN) en renvoyant true si au moins une sous-expression est vraie.
   • parse_and : évalue &(expr1, expr2, ..., exprN) en renvoyant true uniquement si toutes les sous-expressions sont vraies.
   • parse_not : évalue !(expr) en renvoyant l'opposé de la sous-expression.

3. Gestion des expressions :

   • Les caractères simples comme t et f se traduisent directement par vrai et faux.
   • Lorsqu'une opération est rencontrée (&, |, !), les expressions internes sont évaluées en fonction de leurs règles respectives.

Implémentons cette solution en PHP : 1106. Analyser une expression booléenne

  
  
  Explication:




Fonction principale (parseBooleanExpression) :


Parcourt l'expression et pousse les caractères vers une pile.
Lorsqu'il rencontre un ), il collecte tous les éléments entre parenthèses et les évalue en fonction de l'opération (&, |, !).
Convertit les résultats en « t » (vrai) ou « f » (faux) et les repousse dans la pile.







Fonctions d'aide :



parse_and : renvoie vrai si toutes les sous-expressions sont « t » (vrai).

parse_or : renvoie vrai si une sous-expression est « t ».

parse_not : inverse la valeur booléenne d'une seule sous-expression.








  
  
  Exemple de procédure pas à pas :




Entrée : "&(|(f))"


Traitement de la pile :



&, (, |, (, f, ), ) → L'expression interne |(f) est évaluée à f.
Résultant de &(f), qui est évalué à f.


Sortie : faux.



Entrée : "|(f,f,f,t)"


Évalue le | opération:


Trouver un « t », et l'évaluer est donc vrai.


Sortie : vrai.



Entrée : "!(&(f,t))"

Traitement de la pile :



!, (, &, (, f, ,, t, ), ) → &(f,t) est évalué à f.

!(f) est alors évalué à vrai.


Sortie : vrai.





  
  
  Complexité:




Complexité temporelle : O(N), où N est la longueur de l'expression. Chaque caractère est traité un nombre limité de fois.

Complexité spatiale : O(N), en raison de la pile utilisée pour garder la trace des expressions imbriquées.


Cette solution est bien adaptée aux contraintes et devrait gérer efficacement la taille d'entrée.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!