Construire un arbre d'expression en utilisant une pile et un arbre binaire c

binary-tree c expression-trees stack

Question

On me donne une formule arithmétique contenant les opérateurs +, -, *, / et les parenthèses (qui peuvent ou non changer la priorité naturelle des opérateurs). Un exemple serait le suivant: a / b + f - (c + d) * e - a * c. et on me demande d'utiliser une pile (implémentée sous forme de liste chaînée) afin de garder une trace des opérandes et des opérateurs: voici un exemple de la façon dont mon programme devrait fonctionner:

  • Lire une pile d'opérandes
  • Lire /, appuyer sur la pile d'opérateurs
  • Lire b, appuyer sur la pile d'opérandes
  • Read +: a une priorité inférieure à /, donc:
    • extraire 2 opérandes (a et b) de la pile d'opérandes
    • pop / de la pile d'opérateur
    • créer un sous-arbre et pousser sur la pile d'opérandes
    • la pile d'opérateurs est vide, donc appuyez dessus +
  • Lire f, appuyer sur la pile d'opérandes
  • Lire -: a la même priorité que +, donc:
    • pop 2 opérandes de la pile d'opérandes
    • opérateur pop + depuis la pile d'opérateurs
    • créer un arbre avec opérateur + comme racine et les deux opérandes comme enfants gauche et droit
    • repoussez la racine de l'arbre créé sur la pile d'opérandes
    • la pile d'opérateurs est vide, alors poussez dessus

Le problème que j’ai du mal à comprendre, c’est comment puis-je distinguer la préséance des opérandes !

Voici une version incomplète du code que j'ai écrit:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

typedef struct btnode Btree;
typedef struct node s_Node;

struct btnode {
    char info; 
    Btree *left; 
    Btree *right;
};


struct node {
    char element;
    s_Node*next;
}; 

typedef struct{
    s_Node *top_stack;
} stack_t; 

int IsOperator(char c);

main () {
    FILE* fp;
    stack_t operands;
    stack_t operators;
    char c;
    operands=NewStack();
    operators=NewStack();
    fp= fopen ("Myfile.txt", "r");
    if (fp== NULL)
        printf ("   FILE COULD NOT BE OPENED");
    else
    {
        c=getc(fp);
        while (!feof (fp))
        {
            if ( c== ' ');
            else 
            {
                printf ("Here is your character: %c\n", c);
                if (IsOperator (c))
                    Push (c, &operands);
                else if ( isalpha (c))


            }
        c=getc(fp);
        }
    }
}

int IsOperator(char c)
{   
    switch(c)
    {
        case '+':
        case '-':
        case '/':
        case '*':
        return 1;
        default:
        return 0;
    }
} 

stack_t NewStack()
{
    stack_t *n_stack;
    n_stack=(stack_t*)malloc(sizeof(stack_t));
    n_stack->top_stack=NULL;
    return (*n_stack);  
}

int Push(char e, stack_t *q)
{       
    s_Node *nn;
    nn= (s_Node*)malloc(sizeof(s_Node));

    if(Full(*q))
    {
        printf("\n\t Stack is Full !! \n\n");
        return 0;   // return 0 if enstack NOT successful
    }
    else 
    { 
        nn->element=e; // Storing the elemnt read inside the the new node
        nn->next=q->top_stack; // Pointing the new node to the top of the stack
        q->top_stack=nn; // Changing the top of the stack
        return 1;
    }
}

Merci d'avance!

Réponse acceptée

pour l'algorithme que vous utilisez, les opérandes n'ont pas de priorité. Mais dans l’analyseur de réduction de décalage de bas en haut, il a la priorité, comme le dit @WhozCraig au commentaire de cet article ci-dessous.

Les opérandes sont toujours insérés dans la pile d'opérandes et seront extraits 2 et calculés avec un opérateur, puis poussés à nouveau dans la pile d'opérandes en tant qu'opérande unique.

Pour votre formule: a / b + f - (c + d) * e - a * c

  • une
  • push à la pile d'opérande
  • opérande : a
  • opérateur :

  • /

  • push à la pile d'opérateur
  • opérande : a
  • opérateur : /

  • b

  • push à la pile d'opérande
  • opérande : ab
  • opérateur : /

  • +

  • + <= / -> pop /, a & b -> a / b -> pousser dans la pile d'opérande
  • push + to stack stack
  • opérande : (a / b)
  • opérateur : +

  • F

  • pousser à la pile d'opérande
  • opérande : (a / b) f
  • opérateur : +

  • -

  • - <= + -> pop +, (a / b) et f -> (a / b) + f -> pousser dans la pile d'opérande
  • opérande : ((a / b) + f)
  • opérateur : -

  • (

  • pousser à la pile d'opérateur
  • opérande : ((a / b) + f)
  • opérateur : - (

  • c

  • pousser à la pile d'opérande
  • opérande : ((a / b) + f) c
  • opérateur : - (

  • +

  • pousser à la pile d'opérateur
  • opérande : ((a / b) + f) c
  • opérateur : - (+

  • pousser à la pile d'opérande
  • opérande : ((a / b) + f) cd
  • opérateur : - (+

  • )

  • jusqu’à '(' sauté, saute tous les opérateurs en pile un par un et calcule avec 2 opérandes
  • -> pop +, c & d -> c + d -> pile dans la pile d'opérandes
  • opérande : ((a / b) + f) (c + d)
  • opérateur : - (
  • -> pop (, arrête la pile d'opérateur
  • opérande : ((a / b) + f) (c + d)
  • opérateur : -

  • *

  • * > - push to stack stack
  • opérande : ((a / b) + f) (c + d)
  • opérateur : - *

  • e

  • * > - pousser à la pile d'opérande
  • opérande : ((a / b) + f) (c + d) e
  • opérateur : - *

  • -

  • - <= * pop *, (c + d) et e -> (c + d) * e -> pile dans la pile d'opérandes
  • opérande : ((a / b) + f) ((c + d) * e)
  • opérateur : -
  • - <= - pop -, ((a / b) + f) et ((c + d) * e) -> ((a / b) + f) - ((c + d) * e) -> appuyer à la pile d'opérande
  • pile pour opérateur
  • opérande : (((a / b) + f) - ((c + d) * e))
  • opérateur : -

  • une

  • pousser à la pile d'opérande
  • opérande : (((a / b) + f) - ((c + d) * e)) a
  • opérateur : -

  • *

  • * > - push to stack stack
  • opérande : (((a / b) + f) - ((c + d) * e)) a
  • opérateur : - *

  • c

  • pousser à la pile d'opérande
  • opérande : (((a / b) + f) - ((c + d) * e)) ac
  • opérateur : - *

  • fin de ligne

  • pop tous les opérateurs en pile un par un
  • pop *, a & c -> (a * c) -> pile dans la pile d'opérandes
  • opérande : (((a / b) + f) - ((c + d) * e)) (a * c)
  • opérateur : -
  • pop -, (((a / b) + f) - ((c + d) * e)) & (a * c) -> (((a / b) + f) - ((c + d) * e)) - (a * c) -> pousser vers la pile d'opérande
  • opérande : ((((a / b) + f) - ((c + d) * e)) - (a * c))
  • opérateur :

résultat: ((((a / b) + f) - ((c + d) * e)) - (a * c))



Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow