Building an expression tree using a stack and a binary tree c

binary-tree c expression-trees stack

Question

A mathematical formula including the operations +, -, *, /, and parentheses is presented to me (which might or might not change the natural precedence of operators). The following is an illustration: a * c; a / b + f; (c + d) * e. and I'm expected to manage the operands and operators using a stack (implemented as a linked list): The following is an illustration of how my software should operate:

  • Push the operand stack when reading a.
  • Push the operator stack when reading /.
  • Push the operand stack after reading b.
  • The precedence of + is lower than that of /, so:
    • 2 operands (a and b) are popped off the operand stack.
    • from operator stack, pop
    • build a subtree and put it into the operand stack
    • Push + on the operator stack because it is empty.
  • Push the operand stack after reading f.
  • - has the same precedence as + when read, so:
    • from the operand stack, pop two operands
    • from operator stack, pop operator +
    • make a tree with the two operands as its left and right offspring, with the root being the operator +.
    • Put the constructed tree's root back on the operand stack.
    • Push - on the operator stack because it is empty.

How can I separate the ordinal order of the operands is the issue that I find difficult to comprehend.

An partial copy of the code I created is provided below:

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

I appreciate it in advance.

1
0
12/8/2012 1:17:39 PM

Accepted Answer

Operands have no priority for the algorithm you are applying. But as @WhozCraig noted in a comment on this piece below, it does take priority in bottom-up shift-reduce parsers.

The operands are always inserted into the operand stack, popped out two at a time, and then calculated using an operator before being pushed back into the operand stack as a single operand.

For your equation: (c + d) * e â€" a * c / b + f

  • a
  • push operation stack
  • a operand
  • operator:

  • /

  • push operating stack
  • a operand
  • / operator

  • b

  • push operation stack
  • 82-82-82: a b
  • / operator

  • +

  • + <= / push to operand stack, pop /, a / b, and a & b
  • push + operating stack
  • 127-127: (a / b)
  • 135 to zzz: +

  • f

  • Operand stack push
  • (a/b) f: operand
  • 161 to zzz: +

  • -

  • - <= + pop +, (a/b) & f, (a/b) + f, and so on. Operand stack push
  • ((a/b)+f): operand
  • operator: -

  • (

  • to operator stack, push
  • ((a/b)+f): operand
  • - (Zzz-225-Zzz)

  • c

  • Operand stack push
  • ((a/b)+f) c operand
  • Zzz251-Zzz: (

  • +

  • to operator stack, push
  • ((a/b)+f) c operand
  • - (+) operator

  • d

  • Operand stack push
  • the following: ((a/b)+f) c d
  • - (+) operator

  • )

  • Pop each operator in the stack one at a time until '(' is popped, then compute with two operands.
  • -> put to operand stack, c + d, c & d
  • ((A/B)+F) (C+D): operand
  • 340-zzz-zzz: (
  • -> stop popping operator stack; pop
  • (((a/b)+f) (c+d)) Zzz-351-Zzz
  • 359 to zzz:

  • *

  • * > - to operator stack, push
  • ((a/b) + f) (c + d) operand
  • 387-zzz: - *

  • e

  • * > - Operand stack push
  • ((a/b) + f) ((c + d) e) operand
  • 417-zzz: - *

  • -

  • - <= * & e -> pop *, (c + d) (c + d) * e -> Operand stack push
  • ((a/b)+f) ((c+d)*e) operand
  • operator: -
  • - <= - ((A/B)+F) pop - Push to operand stack: & ((c+d)*e) -> ((a/b)+f) - ((c+d)*e)
  • to operator stack, push
  • (((a/b)+f)-(((c+d)*e)): operand
  • A: operator

  • a

  • Operand stack push
  • (((a/b)+f)-(((c+d)*e))) operand
  • 511-zzz: -

  • *

  • * > - to operator stack, push
  • (((a/b)+f)-(((c+d)*e))) operand
  • 539-zzz: - *

  • c

  • Operand stack push
  • (((a/b)+f)) operand -((c+d)*e)) a c
  • 563-zzz: - *

  • the last line

  • one by one, pluck each operator from the stack
  • push to operand stack from pop *, a & c to (a*c)
  • (((a/b)+f)-((c+d)*e)) (a*c): operand
  • A: operator:
  • (((a/b)+f) pop - (((a/b)+f)-((c+d)*e)) & (a*c) -> (((c+d)*e)) Push to operand stack: - (a*c)
  • ((((a/b)+f)-(((c+d)*e))-((a*c)): operand
  • operator:

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

5
12/9/2012 12:48:15 AM


Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow