title: Building an expression tree using a stack and a binary tree c
body: <p>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:</p>
  
  <ul>
  <li>Read a, push on operand stack</li>
  <li>Read /, push on operator stack</li>
  <li>Read b, push on operand stack</li>
  <li>Read +: has lower precedence than / , so:
  <ul>
  <li>pop 2 operands (a and b) from operand stack</li>
  <li>pop / from operator stack</li>
  <li>create subtree and push on operand stack</li>
  <li>operator stack is empty, so push + on it</li>
  </ul></li>
  <li>Read f, push on operand stack</li>
  <li>Read - : has same precedence as + , so:
  <ul>
  <li>pop 2 operands from operand stack</li>
  <li>pop operator + from operator stack</li>
  <li>create a tree with operator + as the root and the two operands as left and right children</li>
  <li>push the root of the created tree back on the operand stack</li>
  <li>operator stack is empty, so push - on it</li>
  </ul></li>
  </ul>
  
  <p>The problem that I have difficulty understanding is how can I distinguish the <strong>precedence of the operands</strong>!</p>
  
  <p>Here is an incomplete version of the code that I wrote:</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;ctype.h&gt;
  
  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, &amp;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-&gt;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-&gt;element=e; // Storing the elemnt read inside the the new node
          nn-&gt;next=q-&gt;top_stack; // Pointing the new node to the top of the stack
          q-&gt;top_stack=nn; // Changing the top of the stack
          return 1;
      }
  }
  </code></pre>
  
  <p>Thank you in advance!</p>