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




[python] ... [/python] pour insérer un code Python.
[latex] ... [/latex] pour insérer au format latex.

Exemple:

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

[latex]\sqrt{x}[/latex]


Poster un commentaire



Programmes proches

Notation polonaise inversé ou post-fixée
Permutation circulaire d'une pile
Permutation circulaire d'une file d'attente
Copier une pile
Copier une file d'attente
Expression bien parenthésée
Renverser une file d'attente
Les primitives d'une file d'attente : FIFO
Les primitives d'une pile: LIFO