расчет арифметического выражения через бинарное дерево

[darklexus1990]

Собственно есть частичный код программы.Необходимо все собрать в одно.

Задание:. Написать программу, размещающую запись арифметического выражения в двоичном дереве. Арифметическое выражение может содержать в себе переменные, знаки математических операций, круглые скобки. Результатом программы должно быть вычисленное значение произвольно заданного арифметического выражения.

Структура бинарного дерева для данного примера:

struct tree{
double value;
BOOL sym;
char op;
tree *left,*right;
};

Функция добавления числа (листа) к дереву:

tree *add(tree *r,char *num,int len_num){
   if(r==NULL){
      if(len_num>0){
         num[len_num]=0;
         r=new tree();
         r->value=atof(num);
         r->left=NULL;
         r->right=NULL;
         r->sym=false;
      }else{
         return NULL;
      }
   }else{
      r->right=add(r->right,num,len_num);
   }
   return r;
}

Для работы программы потребуется объявление глобальных переменных:

char *s;
int i,l;
tree *root=NULL;

Функция создания дерева, возвращает указатель на созданную структуру.
Вызывается таким образом:

if ((root=buildtree(NULL))==NULL||i<l-1) обработка ошибок

Строка s содержит введенное арифметическое выражение.

tree *buildtree(tree *r){
   int c=0;
   tree *temp,*b;
   char *num=new char[250];
   while(s[i]!=')'){
      if(i>=l){
         return NULL;
      }
      switch(s[i]){
         case '+':
         case '-':
            if(c==0&&s[i-1]!=')'){
               return NULL;
            }
            temp=r;
            r=new tree();
            r->sym=true;
            r->op=s[i];
            r->right=NULL;
            if(s[i-1]!=')'){
               if((temp=add(temp,num,c))!=NULL){
                  r->left=temp;
                  c=0;
               }else{
                  return NULL;
               }
            }else{
                  r->left=temp;
            }
            break;
         case '*':
         case '/':
            if(c==0&&s[i-1]!=')'){
               return NULL;
            }
            if(s[i-1]!=')'&& r!=NULL){
               temp=new tree();
               temp->sym=true;
               temp->op=s[i];
               temp->left=NULL;
               temp->right=NULL;
               if((temp->left=add(temp->left,num,c))!=NULL){
                  b=r;
                  while(b->right!=NULL){
                    b=b->right;
                  }
                  b->right=temp;
                  c=0;
               }
            }else{
               temp=r;
               r=new tree();
               r->sym=true;
               r->op=s[i];
               r->right=NULL;
               if(temp==NULL){
                  if((temp=add(temp,num,c))!=NULL){
                     r->left=temp;
                     c=0;
                  }else{
                     return NULL;
                  }
               }else{
                  r->left=temp;
               }
            }
            break;
         case '(':
            i++;
            if(r==NULL){
               if((r=buildtree(r))==NULL){
                  return NULL;
               }
            }else{
               if((r->right=buildtree(NULL))==NULL){
                  return NULL;
               }
            }
            break;
         case '0':
         case '1':
         case '2':
         case '3':
         case '4':
         case '5':
         case '6':
         case '7':
         case '8':
         case '9':
         case '.':
            num[c++]=s[i];
            break;
         case ' ':
            break;
         default:
            return NULL;
      }
      i++;
   }
   if(c>0){
      r=add(r,num,c);
      c=0;
   }

   return r;
}

[darklexus1990]

Функция проверки правильности составленного арифметического выражения (в т.ч. и правильность расстановки круглых скобок):

int check(){
  int state=0,cnt=0;
  for(i=0;i<l-1;i++){
    switch(state){
      case 0:
       switch(s[i]){
       case '(':
         cnt++;
       break;
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
      case '0':
         state=1;
       break;
       default:
         return false;
     }
      break;
      case 1:
       switch(s[i]){
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
      case '0':
       break;
     case '.':
       state=2;
       break;
      case '+':
     case '-':
     case '*':
     case '/':
       state=4;
       break;
     case ')':
       if(cnt>0){
         cnt--;
         state=5;
       }else{
         return false;
       }
       break;
     default:
       return false;
   }
   break;
      case 2:
   switch(s[i]){
     case '1':
     case '2':
     case '3':
     case '4':
     case '5':
     case '6':
     case '7':
     case '8':
     case '9':
     case '0':
       state=3;
       break;
     default:
       return false;
   }
   break;
      case 3:
   switch(s[i]){
     case '1':
     case '2':
     case '3':
     case '4':
     case '5':
     case '6':
     case '7':
     case '8':
     case '9':
     case '0':
       break;
      case '+':
     case '-':
     case '*':
     case '/':
       state=4;
       break;
     case ')':
       if(cnt>0){
         cnt--;
         state=5;
       }else{
         return false;
       }
       break;
     default:
       return false;
   }
   break;
      case 4:
   switch(s[i]){
     case '1':
     case '2':
     case '3':
     case '4':
     case '5':
     case '6':
     case '7':
     case '8':
     case '9':
     case '0':
       state=1;
       break;
     case '(':
       cnt++;
       state=0;
       break;
     default:
       return false;
   }
   break;
      case 5:
   switch(s[i]){
      case '+':
     case '-':
     case '*':
     case '/':
       state=4;
       break;
     case ')':
       if(cnt>0){
         cnt--;
       }else{
         return false;
       }
       break;
     default:
       return false;
   }
   break;

    }
  }
  if((cnt==0)&&((state==1)||(state==3)||(state==5))){
    return true;
  }
  return false;
}

Функция очистки дерева, вызывается так:

root=deltree(root);

tree *deltree(tree *root)
{
if(root!=NULL)
   {
    deltree(root->left);
    deltree(root->right);
    delete root;
    root=NULL;
   }
return NULL;
}

Функция подсчета результата арифметического выражения:

double calc(tree *r){
   if(r!=NULL){
      if(r->sym){
         switch(r->op){
            case '+':
               return calc(r->left)+calc(r->right);
            case '-':
               return calc(r->left)-calc(r->right);
            case '*':
               return calc(r->left)*calc(r->right);
            case '/':
               return calc(r->left)/calc(r->right);
         }

          }
          return r->value;
       }
       return 0;
    }

Функция ввода арифметического выражения, не допускающая буквенных символов:

void vvod(){
   char ch=0;
   i=0;
   while((ch=getch())!=13){
      switch(ch){
         case 8:
            printf("%c",8);
            printf(" %c",8);
            i--;
         break;
         case '1':
         case '2':
         case '3':
         case '4':
         case '5':
         case '6':
         case '7':
         case '8':
         case '9':
         case '0':
         case '(':
         case ')':
         case '+':
         case '-':
         case '*':
         case '/':
         case '.':
            printf("%c",ch);
            s[i++]=ch;
      }
   }
   s[i]=0;
   i=0;
   s=strcat(s,")");
   l=strlen(s);
   printf("\n");
}