Comment insérer une parenthèse dans une expression d'infixe en utilisant une pile

Question

J'ai besoin d'un algorithme pour insérer une parenthèse dans une expression infixe en utilisant pile. par exemple:

entrée: 12/c + c * p^(8 + 9)

sortie: ((12/c) + (c * (p^(8 + 9))))

J'ai juste besoin de l'algorithme pour cela et il est ok si nous arrivons à la sortie par préfixe ou postfix. mais la sortie doit être exacte comme l'exemple. une expression infixe avec une parenthèse complète.

Je vais apprécier si quelqu'un peut donner un pseudo-code ou un exemple étape par étape.

Merci

Answer 1

J'ai réalisé auparavant par la notation polonaise inverse (RPN). Vous devez d'abord construire une version postfix de l'expression. Vous pouvez utiliser the shunting-yard algorithm. Deuxièmement, vous devez "évaluer" (symboliquement) l'expression de postfix que vous venez de créer. The RPN evaluation algorithm fait cela.

Answer 2

1 - convertir à postfix

2 - lire l'expression postfix

3 - une boucle sur l'expression postfix ... si le caractère est poussée opérandes dans la pile d'autre si l'opérateur ... pop top deux dans la pile et insérez cette deux avec l'opérateur qui est le caractère actuel dans les parenthèses et repoussez-le dans la pile