typedef unsigned char    Uint8;
typedef unsigned short    Uint16;
typedef unsigned long    Uint32;
typedef signed char      Sint8;
typedef signed short    Sint16;
typedef signed long      Sint32;

struct Math
{
   bool IsNum;
   int var;
   Math *next;
   Math *last;
};

void Del(Math *ptr)
{
   if(ptr->last != NULL)
   {ptr->last->next= ptr->next;}
         
   if(ptr->next != NULL)
   {ptr->next->last= ptr->last;}

   delete ptr;
}

char Operator[5]={'*', '/', '+', '-'};
Math* Calculate(Math *list)
{
   Math* var1= NULL;//var1 is used for doing math operations and for deleteing ')' nodes
   Math* var2= NULL;//used only for math
   Math *parse=list;//used for cycling through the linklist
   Uint16 i;//used for looping through the order of operations

   while( parse != NULL)//cycle through the linklist
   {
      if(!parse->IsNum)//if its an operator
      {
         if(parse->var == '(')//if the operator is an open parenthesis
         {
            var1= Calculate(parse->next);//solve everything within the parenthesis, function should return a pointer to the close parenthesis ')'

            if(parse == list)//dont lose the pointer that marks our place
            {list= parse->next;}
            
            Del(parse);//delete the '('

            if(var1 != NULL)//delete the ')'
            {Del(var1);}

            break;//get outta the loop
         }
      }
      parse = parse->next;
   }

   for(i=0; i < 4; i+=2)//cycle through the Operators, 2 at a time
   {
      parse= list;
      while( parse != NULL)//go through the linklist
      {
         if(!parse->IsNum)//if its an operator
         {
            if(parse->var == Operator[i] || parse->var == Operator[i+1])//if its one of the ones wanted
            {
               var1= parse->last;//get the 2 numbers between the operator
               var2= parse->next;

               if(var1 != NULL && var2 != NULL && var1->IsNum && var2->IsNum)//make sure everything is ok
               {
                  parse->IsNum=true;//this operator is going to turn into a number
                  switch(parse->var)
                  {
                  case '/':
                     parse->var= var1->var / var2->var;
                     break;
                  case '*':
                     parse->var= var1->var * var2->var;
                     break;
                  case '+':
                     parse->var= var1->var + var2->var;
                     break;
                  case '-':
                     parse->var= var1->var - var2->var;
                     break;
                  }

                  if(var1 == list)//make sure we dont lose our place in the array
                  {list= parse;}

                  Del(var1);//delete the 2 variables
                  Del(var2);
               }
            }
            else if(parse->var == ')')//if a ')' closed-parenthesis is found, get out of the loop
            {
               break;
            }
         }
         parse= parse->next;
      }
   }

   if(parse != NULL)//if parse != NULL then that means that a ')' closed-parenthesis was found so return a pointer to it
   {list= parse;}

   return list;
}

int main ()
{
   #define LEN 256 //length of the formula buffer, it will be loaded from INI file sooner or later
   char formula[LEN]="(500 + 600) * 8 + 6 - (2 + (7 - 3))+2";//the problem we want to solve
   int i,j;//used for loops
   Uint16 Multiplier;//used to convert strings into integers
   Math *list=NULL;//the linklist
   Math *parse=NULL;//used to make and parse through the linklist

   j=0;
   for(i=0; (i < LEN) && (formula[i] != NULL) ; i++)
   {//make sure that only characters we want are in the string (this will probably be done once after the formula is loaded from the INI file)
      if(formula[i] >= '(' && formula[i] <= '9' && formula[i] != ',' && formula[i] != '.')//Numbers: 0-9 Operators: ( ) * + - /
      {
         formula[j++]=formula[i];
      }
   }
   formula[j]=0;


   for(i=j-1;i >=0;i--)//start from the end of the string and move forward
   {
      parse= new Math;//make a new Math and make it the head of the linklist
      if(list != NULL)
      {list->last= parse;}//list's last is equal to new head
      parse->next= list;//next is equal to the old head
      list= parse;//list is equal to the head of the linklist

      if(formula[i] >= '0' && formula[i] <= '9')//if its a number
      {
         Multiplier=1;

         parse->var= 0;
         parse->IsNum=true;

         while(i>=0 && formula[i] >= '0' && formula[i] <= '9')
         {
            parse->var += (formula[i] ^ 0x30) * Multiplier;
            Multiplier *= 10;
            i--;
         }
         i++;
      }
      else //its not a number, so its an operator
      {
         parse->var= formula[i];
         parse->IsNum=false;
      }
   }
   list->last= NULL;//the head's ->last pointer points to NULL

   list = Calculate(list);//calculate the number down to 1 node
   if(list != NULL)//if everything went well
   {
      //printf("%i",list->var);
      delete list;//delete the last node
      list=NULL;
   }
   return 0;
}