#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "BST.h"
#define EMPTY 0
void push_exp(int item);
int pop_exp();
int is_stk_exp_empty();
void push_tree();
BST_t *pop_tree();
int is_stk_tree_empty();
BST_t * infixtree(char* infix);
struct stack_exp
{
        int data[MAX];
        int top;
};
struct stack_exp ex;
struct stack_tree
{
        BST_t *nodes[100];
  int top;
};
struct stack_tree tree;
int emptystacks()
{
        ex.top =-1;
        tree.top =-1;
}
void push_exp(int item)
{
                ++ex.top;
                ex.data[ex.top]=item;
}
int pop_exp()
{
        int ret =0;
        if(ex.top != -1)
        {
                ret= ex.data[ex.top];
                --ex.top;
        }
        return ret;
}
int is_stk_exp_empty()
{
 if(ex.top == -1)
                return 1;
        else
                return 0;
}
int isoperator(char e)
{
        if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%'|| e == '^')
                return 1;
        else
                return 0;
}
BST_t *create_node(int n1)
{
        BST_t *newnode;
        newnode = (BST_t *)malloc(sizeof(newnode));
        newnode->data=n1;
        newnode->left=NULL;
        newnode->right=NULL;
        return newnode;
}
int isoper(char ch)
{
  char op;
        switch(ch)
        {
        case '+':
        case '-':
        case '/':
        case '*':
        case '^':
                op =1;
                break;
        default:
                op=0;
                break;
        }
return op;
}
 
BST_t * infixtree(char* infix)
{
        char *i,*p;
        char n1;
        BST_t *temp,*r,*l,*root,*t;
        i = &infix[0];
        while(*i)
        {
 
                while(isblank(*i) && *i != '\0')
   {
                        i++;
                }
 
                if( isdigit(*i) || isalpha(*i))
                {
                        while( isdigit(*i) || isalpha(*i))
                        {
                                push_exp(*i);
                                i++;
                        }
                }
                if(isoper(*i))
                {
                        push_exp(*i);
                }
                if( *i == '(' )
                {
                        push_exp(*i);
                }
                if( *i == ')')
                {
                while( (n1 = pop_exp()) != '(')
                {
                  if(isoperator(n1))
                   {
                     temp = create_node(n1);
      t = pop_tree();
                     if(t)
                       temp->right = t;
                   }
                  else
                  {
                    r=create_node(n1);
                    push_tree(r);
                  }
                }
                l=pop_tree();
                if(l){
                        temp->left=l;
                        root=temp;
                        push_tree(root);
                }
}
i++;
}
return root;
}
void push_tree(BST_t *t)
{
        tree.top++;
        tree.nodes[tree.top]=(BST_t *)malloc(sizeof(BST_t));
        tree.nodes[tree.top]=t;
}
 
BST_t *pop_tree()
{
        if(tree.top > -1 )
         return tree.nodes[tree.top--];
        else
         return NULL;
}
int is_stk_tree_empty()
{
        if(tree.top == -1)
                return 1;
        else
                return 0;
}
void inorder(BST_t * root)
{
        if(root != NULL )
        {
            inorder(root->left);
            printf("%c", root->data);
     inorder(root->right);
        }
}
 
int main()
{
      char in1[70],in2[70],post[50],ch;
      BST_t * root1, *root2;root1=root2=NULL;
      int i=0;
      printf(" Exp: \"( a + ( ( ( ( b * c ) ^ d ) / ( e + f ) ) * g) )\"\n");
      strcpy(in1," ( a + ( ( ( ( b * c ) ^ d ) / ( e + f ) ) * g))"); '
      emptystacks();
      root1 = infixtree(in1);
      inorder(root1);
      printf("\n");
      printf("Exp : \"a + b * c ^ d / ( e + f ) * g\" \n");
      strcpy(in2,"a + b * c ^ d / ( e + f ) * g"); 
      emptystacks();
      root2 = infixtree(in2);
      inorder(root2);
return 0;
}

# calc3 - infix calculator

NF > 0 {
    f = 1
    e = expr()
    if (f <= NF) printf("error at %s\n", $f)
    else printf("\t%.8g\n", e)
}

function expr(  e) {        # term | term [+-] term
    e = term()
    while ($f == "+" || $f == "-")
        e = $(f++) == "+" ? e + term() : e - term()
    return e
}

function term(  e) {        # factor | factor [*/] factor
    e = factor()
    while ($f == "*" || $f == "/")
        e = $(f++) == "*" ? e * factor() : e / factor()
    return e
}

function factor(  e) {      # number | (expr)
    if ($f ~ /^[+-]?([0-9]+[.]?[0-9]*|[.][0-9]+)$/) {
        return $(f++)
    } else if ($f == "(") {
        f++
        e = expr()
        if ($(f++) != ")")
            printf("error: missing ) at %s\n", $f)
        return e
    } else {
        printf("error: expected number or ( at %s\n", $f)
        return 0
    }
}