Expression bien parenthésée

Exercice:Expression bien parenthésée

Fonction Python parenthesage( expression ) qui retourne True si l’expression est bien parenthésée et False sinon en utilisant des piles, l’expression est sous forme une chaîne de caractère passée en argument est ou non bien parenthésée en utilisant les piles avec ses primitives.

Avec les parenthèses ( et ) une expression est bien parenthésée si :

  • Il ne contient aucune parenthèse ’(’ ou ’)’, ou
  • Il est de la forme ’(mot)’ avec expression est une expression bien parenthésée, ou
  • Il est la concaténation de 2 expressions bien parenthésées.

Par exemple :

  • Les expressions suivantes sont bien parenthésées : ( ) ; (( )( )) ; (( )( ))(( ))( )
  • Les expressions suivantes ne sont pas bien parenthésées : )( ; ((( )) ; ( )( )( ))

Pour le résoudre à l’aide d’une pile :

  1. On parcourt le mot de gauche à droite
  2. Dés que l’on rencontre un caractère ’(’ on l’empile sur la pile.
  3. Dés que l’on rencontre un caractère ’)’, deux cas se présentent :
    1. Soit la pile est vide, et dans ce cas l’expression n’est pas bien parenthésée.
    2. Soit la pile est non-vide, et dans ce cas on la dépile.
  4. A la fin si la pile est vide l’expression est bien parenthésée, sinon il ne l’est pas.

Exemple d’exécution

>>>parenthesage( ” (( )( ))(( ))( ) ” )
True
>>>parenthesage( ” ((( )) ” )
False

Partager avec...
Share on FacebookShare on Google+Tweet about this on Twitter
Tagués avec : , , , , , , , , , , , , , , , , , , , , ,

Poster un Commentaire

Soyez le premier à commenter !

Utiliser [python] ... [/python] pour insérer un code Python.

$latex format_latex $ pour insérer au format latex.

Exemple:

[python]
print('Hello word')
[/python]

$latex \sqrt{x} $

Laisser un commentaire


Programme similaire