Erstellen eines Ausdrucksbaums unter Verwendung eines Stapels und eines Binärbaums c

binary-tree c expression-trees stack

Frage

Mir wird eine arithmetische Formel gegeben, die Operatoren +, -, *, / und Klammern enthält (die den natürlichen Vorrang von Operatoren ändern oder nicht ändern können). Ein Beispiel wäre das folgende: a / b + f - (c + d) * e - a * c. und ich werde gebeten, einen Stapel (implementiert als eine verkettete Liste) zu verwenden, um die Operanden und die Operatoren zu verfolgen: Ein Beispiel, wie mein Programm funktionieren sollte, ist das Folgende:

  • Lesen Sie einen, schieben Sie den Operandenstapel hoch
  • Lesen /, auf Operator Stack drücken
  • Lesen Sie b, drücken Sie den Operandenstapel
  • Read +: hat eine niedrigere Priorität als /, also:
    • pop 2 Operanden (a und b) vom Operandenstapel
    • pop / vom Operatorstapel
    • Unterbaum erstellen und Operandenstapel anschieben
    • Operator Stack ist leer, also drücken Sie +
  • Lesen Sie f, drücken Sie den Operandenstapel
  • Read -: hat den gleichen Vorrang wie +, also:
    • pop 2 Operanden vom Operandenstapel
    • Popoperator + vom Operatorstapel
    • Erstellen Sie einen Baum mit dem Operator + als Wurzel und den beiden Operanden als linke und rechte Kinder
    • Schieben Sie den Stamm des erstellten Baums auf den Operandenstapel zurück
    • Der Operator - Stapel ist leer, also drücken Sie ihn an

Das Problem, das ich nur schwer verstehen kann, ist, wie ich den Vorrang der Operanden unterscheiden kann !

Hier ist eine unvollständige Version des Codes, den ich geschrieben habe:

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

Vielen Dank im Voraus!

Akzeptierte Antwort

Für den Algorithmus, den Sie verwenden, hat der Operand keinen Vorrang. Aber im Bottom-Up-Shift-Reduce-Parser hat er Vorrang, wie @WhozCraig im Kommentar zu diesem Post unten sagte.

Die Operanden werden immer in den Operandenstack geschoben und werden mit einem Operator 2 herausgenommen und mit einem Operator berechnet, der dann erneut als ein einzelner Operand in den Operandenstapel geschoben wird.

Für Ihre Formel: a / b + f - (c + d) * e - a * c

  • ein
  • push to-Operand-Stack
  • Operand : a
  • Betreiber :

  • /

  • push to-Operator-Stapel
  • Operand : a
  • Betreiber : /

  • b

  • push to-Operand-Stack
  • Operand : ab
  • Betreiber : /

  • +

  • + <= / -> pop /, a & b -> a / b -> zum Operandenstapel schieben
  • Drücken Sie + zum Operatorstapel
  • Operand : (a / b)
  • Betreiber : +

  • f

  • Push-to-Operand-Stack
  • Operand : (a / b) f
  • Betreiber : +

  • -

  • - <= + -> pop +, (a / b) & f -> (a / b) + f -> zum Operandenstapel schieben
  • Operand : ((a / b) + f)
  • Betreiber : -

  • (

  • Push-to-Operator-Stapel
  • Operand : ((a / b) + f)
  • Betreiber : - (

  • c

  • Push-to-Operand-Stack
  • Operand : ((a / b) + f) c
  • Betreiber : - (

  • +

  • Push-to-Operator-Stapel
  • Operand : ((a / b) + f) c
  • Betreiber : - (+

  • d

  • Push-to-Operand-Stack
  • Operand : ((a / b) + f) CD
  • Betreiber : - (+

  • )

  • bis '(' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' ']
  • -> pop +, c & d -> c + d -> zum Operandenstapel schieben
  • Operand : ((a / b) + f) (c + d)
  • Betreiber : - (
  • -> pop (, stoppender Operatorstack
  • Operand : ((a / b) + f) (c + d)
  • Betreiber : -

  • *

  • * > - zum Operatorstapel schieben
  • Operand : ((a / b) + f) (c + d)
  • Betreiber : - *

  • e

  • * > - zum Operandenstapel schieben
  • Operand : ((a / b) + f) (c + d) e
  • Betreiber : - *

  • -

  • - <= * pop *, (c + d) & e -> (c + d) * e -> zum Operandenstapel schieben
  • Operand : ((a / b) + f) ((c + d) * e)
  • Betreiber : -
  • - <= - pop -, ((a / b) + f) & ((c + d) * e) -> ((a / b) + f) - ((c + d) * e) -> drücken zum Operandenstapel
  • Push-to-Operator-Stapel
  • Operand : (((a / b) + f) - ((c + d) * e))
  • Betreiber : -

  • ein

  • Push-to-Operand-Stack
  • Operand : (((a / b) + f) - ((c + d) * e)) a
  • Betreiber : -

  • *

  • * > - zum Operatorstapel schieben
  • Operand : (((a / b) + f) - ((c + d) * e)) a
  • Betreiber : - *

  • c

  • Push-to-Operand-Stack
  • Operand : (((a / b) + f) - ((c + d) * e)) ac
  • Betreiber : - *

  • Ende der Linie

  • pop alle Bediener im Stapel eins nach dem anderen
  • pop *, a & c -> (a * c) -> zum Operandenstapel schieben
  • Operand : (((a / b) + f) - ((c + d) * e)) (a * c)
  • Betreiber : -
  • pop -, (((a / b) + f) - ((c + d) * e)) & (a * c) -> (((a / b) + f) - ((c + d) *) e)) - (a * c) -> Push-to-Operand-Stack
  • Operand : ((((a / b) + f) - ((c + d) * e)) - (a * c))
  • Betreiber :

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



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum