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

binary-tree c expression-trees stack

Question

I am given an arithmetic formula containing operators +, -, *, / and parentheses (which might or might not change the natural precedence of operators). An example would be the following one: a / b + f – (c + d) * e – a * c. and I am asked to use a stack (implemented as a linked list) in order to keep track of the operands and the operators: an example of how my program should work is the following:

  • Read a, push on operand stack
  • Read /, push on operator stack
  • Read b, push on operand stack
  • Read +: has lower precedence than / , so:
    • pop 2 operands (a and b) from operand stack
    • pop / from operator stack
    • create subtree and push on operand stack
    • operator stack is empty, so push + on it
  • Read f, push on operand stack
  • Read - : has same precedence as + , so:
    • pop 2 operands from operand stack
    • pop operator + from operator stack
    • create a tree with operator + as the root and the two operands as left and right children
    • push the root of the created tree back on the operand stack
    • operator stack is empty, so push - on it

The problem that I have difficulty understanding is how can I distinguish the precedence of the operands!

Here is an incomplete version of the code that I wrote:

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

Thank you in advance!

Accepted Answer

for algorithm you are using, operands has no precedence. But in bottom-up shift-reduce parser, it does have precedence as @WhozCraig said at comment of this post below.

The operands always be pushed into operand stack and will be popped out 2 and calculated with an operator then pushed again to operand stack as a single operand.

For your formula: a / b + f – (c + d) * e – a * c

  • a
  • push to operand stack
  • operand: a
  • operator:

  • /

  • push to operator stack
  • operand: a
  • operator: /

  • b

  • push to operand stack
  • operand: a b
  • operator: /

  • +

  • + <= / -> pop /, a & b -> a / b -> push to operand stack
  • push + to operator stack
  • operand: (a / b)
  • operator: +

  • f

  • push to operand stack
  • operand: (a/b) f
  • operator: +

  • -

  • - <= + -> pop +, (a/b) & f -> (a/b) + f -> push to operand stack
  • operand: ((a/b)+f)
  • operator: -

  • (

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

  • c

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

  • +

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

  • d

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

  • )

  • until '(' popped, pop all operator in stack one by one and calculate with 2 operands
  • -> pop +, c & d -> c + d -> push to operand stack
  • operand: ((a/b)+f) (c+d)
  • operator: - (
  • -> pop (, stop popping operator stack
  • operand: ((a/b)+f) (c+d)
  • operator: -

  • *

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

  • e

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

  • -

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

  • a

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

  • *

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

  • c

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

  • end of line

  • pop all operators in stack one by one
  • pop *, a & c -> (a*c) -> push to operand stack
  • operand: (((a/b)+f)-((c+d)*e)) (a*c)
  • operator: -
  • 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))
  • operator:

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



Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why