Comment estimer l'espace de pile nécessaire pour transformer une expression infixe en une expression postfixe

Il existe le fameux shunting-yard algorithm qui peut être utilisé pour transformer une expression infixe (telle que 1 + 2 * 3) en une expression postfixe (telle que 1 2 2 * +). L'algorithme de shunt-yard a besoin d'une pile pour stocker les éléments sur le point d'être déplacés.Comment estimer l'espace de pile nécessaire pour transformer une expression infixe en une expression postfixe

Est-il possible de pré-estimer la longueur de la pile nécessaire pour effectuer une traduction d'une entrée spécifique dans sa forme postfixée en temps linéaire et en mémoire constante?

Source

2013-03-12 fuz

exécuterait l'algorithme de triage de triage sur l'entrée, mais compter au lieu de pousser et de sauter les opérateurs se qualifier comme une réponse? –

@groovy IIRC vous devez connaître le contenu de la pile pour exécuter probablement la cour de triage, par exemple, si vous avez des parens. – fuz

bon point .. :) –

Bien sûr. Le shunting-yard algorithm ne fait que pousser les opérateurs (y compris les parenthèses) sur la pile, donc une approximation de premier ordre est le nombre d'opérateurs dans l'expression. Avec un peu plus d'intelligence, vous pouvez scanner l'expression et rechercher l'associativité et le groupement. Mais au moment où vous avez terminé, vous auriez probablement écrit un algorithme basé sur une pile pour déterminer la meilleure estimation de la taille de la pile requise pour l'expression, et aurait doublé votre coût d'exécution.

Source

2013-03-12 21:41:14

Merci pour la réponse. Je voudrais faire cette estimation parce que je veux éviter un algorithme récursif. Je dois déjà passer par l'expression infixe avant d'estimer quelque chose d'autre, donc je pense que c'est une simple optimisation pour enregistrer les appels à malloc en précalculant la taille de la pile dont j'ai besoin. – fuz

L'algorithme de dérivation est non récursif. Un algorithme n'est pas récursif simplement parce qu'il utilise une pile comme structure de données. Et l'utilisation d'une pile comme structure de données nécessite beaucoup moins de mémoire que l'utilisation d'appels récursifs. –

Ouais, je le sais. C'est pourquoi j'utilise Shunting yard au lieu de déployer un analyseur récursif. Je voudrais juste pré-estimer la quantité de pile nécessaire pour éviter les appels répétés à malloc. – fuz

Sur l'ancienne calculatrice HP-45, nous avons toujours analysé les parenthèses les plus imbriquées et commencé l'évaluation. Cela devrait être un algorithme O (N) rapide pour N jetons dans l'entrée.

En pratique, il était difficile de créer une expression qui a soufflé la pile 4-haute du HP-45.

Source

2013-03-12 21:52:42

Merci pour la réponse même si je ne peux pas vraiment voir comment cela est lié à l'algorithme de triage. – fuz

Comment estimer l'espace de pile nécessaire pour transformer une expression infixe en une expression postfixe

Répondre

Questions connexes