Costruire un albero di espressioni usando una pila e un albero binario c

binary-tree c expression-trees stack

Domanda

Mi viene data una formula aritmetica contenente operatori +, -, *, / e parentesi (che potrebbero o non potrebbero cambiare la naturale precedenza degli operatori). Un esempio potrebbe essere il seguente: a / b + f â € "(c + d) * e â €" a * c. e mi viene chiesto di utilizzare uno stack (implementato come elenco collegato) per tenere traccia degli operandi e degli operatori: un esempio di come dovrebbe funzionare il mio programma è il seguente:

  • Leggere a, premere stack di operandi
  • Leggi /, premi sullo stack dell'operatore
  • Leggi b, premi lo stack degli operandi
  • Leggi +: ha precedenza più bassa di /, quindi:
    • pop 2 operandi (a e b) dalla pila di operandi
    • pop / da stack operatore
    • creare sottostruttura e premere stack di operandi
    • lo stack dell'operatore è vuoto, quindi premi + su di esso
  • Leggi f, premi stack degli operandi
  • Leggi -: ha la stessa precedenza di +, quindi:
    • pop 2 operandi dalla pila di operandi
    • pop operator + dallo stack dell'operatore
    • crea un albero con operatore + come radice e i due operandi come figli sinistro e destro
    • spingere indietro la radice dell'albero creato nella pila degli operandi
    • lo stack dell'operatore è vuoto, quindi spingilo sopra

Il problema che ho difficoltà a capire è come posso distinguere la precedenza degli operandi !

Ecco una versione incompleta del codice che ho scritto:

#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;
    }
}

Grazie in anticipo!

Risposta accettata

per l'algoritmo che stai utilizzando, gli operandi non hanno precedenza. Ma in bottom-up shift-ridurre parser, ha la precedenza come @WhozCraig ha detto al commento di questo post qui sotto.

Gli operandi devono essere sempre inseriti nello stack degli operandi e verranno estratti 2 e calcolati con un operatore, quindi trasferiti nuovamente agli operandi come un unico operando.

Per la tua formula: a / b + f â € "(c + d) * e â €" a * c

  • un
  • push alla pila di operandi
  • operando : a
  • operatore :

  • /

  • push allo stack dell'operatore
  • operando : a
  • operatore : /

  • B

  • push alla pila di operandi
  • operando : ab
  • operatore : /

  • +

  • + <= / -> pop /, a & b -> a / b -> invia allo stack operand
  • spingere + per impilare l'operatore
  • operando : (a / b)
  • operatore : +

  • f

  • spingere alla pila di operandi
  • operando : (a / b) f
  • operatore : +

  • -

  • - <= + -> pop +, (a / b) & f -> (a / b) + f -> push a pila degli operandi
  • operando : ((a / b) + f)
  • operatore : -

  • (

  • spingere allo stack dell'operatore
  • operando : ((a / b) + f)
  • operatore : - (

  • c

  • spingere alla pila di operandi
  • operando : ((a / b) + f) c
  • operatore : - (

  • +

  • spingere allo stack dell'operatore
  • operando : ((a / b) + f) c
  • operatore : - (+

  • d

  • spingere alla pila di operandi
  • operando : ((a / b) + f) cd
  • operatore : - (+

  • )

  • fino a quando '(' popping, pop all in stack uno alla volta e calcola con 2 operandi
  • -> pop +, c & d -> c + d -> push allo stack degli operandi
  • operando : ((a / b) + f) (c + d)
  • operatore : - (
  • -> pop (, interrompe lo stack di popping dell'operatore
  • operando : ((a / b) + f) (c + d)
  • operatore : -

  • *

  • * > - premi allo stack dell'operatore
  • operando : ((a / b) + f) (c + d)
  • operatore : - *

  • e

  • * > - push allo stack degli operandi
  • operando : ((a / b) + f) (c + d) e
  • operatore : - *

  • -

  • - <= * pop *, (c + d) & e -> (c + d) * e -> push allo stack operand
  • operando : ((a / b) + f) ((c + d) * e)
  • operatore : -
  • - <= - pop -, ((a / b) + f) & ((c + d) * e) -> ((a / b) + f) - ((c + d) * e) -> push allo stack di operandi
  • push - per stack operatore
  • operando : (((a / b) + f) - ((c + d) * e))
  • operatore : -

  • un

  • spingere alla pila di operandi
  • operando : (((a / b) + f) - ((c + d) * e)) a
  • operatore : -

  • *

  • * > - premi allo stack dell'operatore
  • operando : (((a / b) + f) - ((c + d) * e)) a
  • operatore : - *

  • c

  • spingere alla pila di operandi
  • operando : (((a / b) + f) - ((c + d) * e)) ac
  • operatore : - *

  • fine della linea

  • pop tutti gli operatori nello stack uno per uno
  • pop *, a & c -> (a * c) -> push allo stack degli operandi
  • operando : (((a / b) + f) - ((c + d) * e)) (a * c)
  • operatore : -
  • pop -, (((a / b) + f) - ((c + d) * e)) & (a * c) -> ((a / b) + f) - ((c + d) * e)) - (a * c) -> push to operand stack
  • operando : ((((a / b) + f) - ((c + d) * e)) - (a * c))
  • operatore :

risultato: ((((a / b) + f) - ((c + d) * e)) - (a * c))



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché