#include <stdlib.h>
#include <string.h>

void parenPermutations (char *expression)
{
   int marker, num_ints, num_tokens, num_elements;
   int i, j;
   int numbers[10000]; char tokens[10000];
   char newstr[10000]; int len; char working_str[10000];
   int num_results, results[10000];
   char *element[10000], to_add[10000];
   char possibles[1000][10000]

   strcpy (newstr, expression);
   marker = 0; num_ints = 0; num_tokens = 0; num_elements = 0;
   for (i = 0; i < 10000; i++)
      {
         element[i] = NULL;
         tokens[i] = 0;
      }

   element [num_elements] = strtok (&(newstr[marker]), " ");
   marker += strlen (element[num_elements]) + 1;
   while (element[num_elements] != NULL)
      {
         element [++num_elements] = strtok (&(newstr[marker]), " ");
         marker += strlen (element[num_elements]) + 1;
      }

   printf ("\n*** num_elements = %d\n", num_elements);

   marker = 0;
   numbers[num_ints++] = atoi(element[marker++]);
   while (marker < num_elements)
      {
         tokens[num_tokens++] = *(element[marker++]);
         numbers[num_ints++] = atoi(element[marker++]);
      }

   printf ("\nnum_ints = %d, num_tokens = %d, num_elements = %d\n",
      num_ints, num_tokens, num_elements);
   // Get no-parens result as base case

   for (i = 0; i < num_elements; i++)
      printf ("%s", element[i]);
   printf ("\n");

   i = 0;
   sprintf (newstr, "%d\0", numbers[0]);
   printf ("Main Newstr = {%s}\n",newstr);
   for (i = 0; i < num_tokens; i++)
      {
         strcat (newstr, " ");
         len = strlen(newstr);
         newstr[len] = tokens[i];
         newstr[len+1] = '\0';
         sprintf (to_add, " %d\0", numbers[i+1]);
         strcat (newstr, to_add);
         printf ("Main Newstr = {%s}\n",newstr);
      }

   // Now add parens recursively
   strcpy (working_str, "");

   i = 0;
   for (j = num_ints - 1; j > 2; j--)
      {
          k = j;  // num of ints inside outer parens
          while (k > 1)
             {
                 
             } 

      }


   printf ("Main Newstr = {%s}\n",newstr);

   results[num_results++] = parseExpression (newstr);
   printf ("RESULT = %d\n", results[0]);
}


int parseExpression (char *expression)
{
   int numbers[10000];
   char tokens[10000];
   int num_ints = 0, num_tokens = 0;
   int marker = 0;
   int num_elements = 0;
   char working_str[10000];
   char working_str2[10000];
   char newstr[10000];
   int next_results[10000];
   int next_num_results = 0;
   int this_loop_results;
   int i, j;
   int open_paren_marker = -1, close_paren_marker;
   int intermediate_result;
   int copy_from, copy_to;
   int final_result;
   int multi_pos;
   char *element[10000];
   char itoa_result [1000];
   int len;

   for (i = 0; i < 10000; i++)
      element[num_elements] = NULL;

   strcpy (working_str, expression);

   do
   {
   strcpy (newstr, working_str);
   len = strlen (newstr);
   newstr [len+1] = '\0';

   open_paren_marker = -1; close_paren_marker = -1;
   num_elements = 0;

   marker = 0;
   element [num_elements] = strtok (&(working_str[marker]), " ");
   marker += strlen (element[num_elements]) + 1;
   while (element[num_elements] != NULL)
      {
         element [++num_elements] = strtok (&(working_str[marker]), " ");
         marker += strlen (element[num_elements]) + 1;
      }

   printf ("num_elements = %d\n", num_elements);
   marker = 0;
   while (marker < num_elements)
      {
         printf ("Element %d, is %s\n",marker, element[marker]);
         if (strcmp(element[marker], "(") == 0)
            open_paren_marker = marker;
         if (*(element[marker])==')')
            {
               close_paren_marker = marker;
               break;
            }
         marker++;
      }

   printf ("open par = %d, close par = %d 
\n",open_paren_marker,close_paren_marker);

   if (close_paren_marker > 0)
      {
         strcpy (newstr, element[open_paren_marker + 1]);
         for (i = open_paren_marker+2; i < close_paren_marker; i++)
            {
               strcat (newstr, " ");
               strcat (newstr, element[i]);
            }
               
         printf ("Newstr: %s\n", newstr);
         intermediate_result = parseExpression (newstr);

         // Replace inner-most parenthetical with intermediate result
         strcpy (working_str2, "");
         j = 0;
         for (i = 0; i < open_paren_marker; i++)
            {
               strcat (working_str2, element[i]);
               strcat (working_str2, " ");
            }
         sprintf (itoa_result, "%d\0", intermediate_result);
         strcat (working_str2, itoa_result);
         for (i = close_paren_marker + 1; i < num_elements; i++)
            {
               strcat (working_str2, " ");
               strcat (working_str2, element[i]);
            }
         strcpy (working_str, working_str2);
         len = strlen(working_str);
         for (i = len; i < 10000; i++)
            working_str[i] = '\0';
         printf ("New working str: %s\n",working_str);
   }

   } while (close_paren_marker > 0);

   // No more parens left; parse left to right

parse_again:
   marker = 0; num_ints = 0; num_tokens = 0; num_elements = 0;
   for (i = 0; i < 10000; i++)
      {
         element[num_elements] = NULL;
         tokens[i] = 0;
      }

   printf ("Newstr = {%s}\n",newstr);
   element [num_elements] = strtok (&(newstr[marker]), " ");
   marker += strlen (element[num_elements]) + 1;
   while (element[num_elements] != NULL)
      {
         element [++num_elements] = strtok (&(newstr[marker]), " ");
         marker += strlen (element[num_elements]) + 1;
      }

   printf ("\n*** num_elements = %d\n", num_elements);

   marker = 0;
   numbers[num_ints++] = atoi(element[marker++]);
   while (marker < num_elements)
      {
         tokens[num_tokens++] = *(element[marker++]);
         numbers[num_ints++] = atoi(element[marker++]);
      }

   printf ("\nnum_ints = %d, num_tokens = %d, num_elements = %d\n", 
num_ints, num_tokens, num_elements);

   if (num_ints == 1)
      {
         return numbers[0];
      }

         // Have to do multiplication first
         marker = 0; multi_pos = -1;
         for (i=0; i < num_tokens; i++)
            {
               printf ("Token %d = %c\n", i, tokens[i]);
               if (tokens[i] == '*')
                  {
                     printf ("multi_pos = %d\n", i);
                     multi_pos = i;
                     strcpy (newstr, "");
                     for (j=0; j < i; j++)
                        {
                           sprintf (itoa_result, "%d\0", numbers[j]);
                           strcat (newstr, itoa_result);
                           strcat (newstr, " ");
                           len = strlen(newstr);
                           newstr[len] = tokens[j];
                           newstr[len+1] = '\0';
                           strcat (newstr, " ");
                        }
                     printf ("Numbers %d * %d\n",numbers[i],numbers[i+1]);
                     sprintf (itoa_result, "%d\0", numbers[i] * numbers[i+1]);
                     printf ("itoa_result = %s\n", itoa_result);
                     strcat (newstr, itoa_result);
                     for (j=i+1; j < num_tokens; j++)
                        {
                           strcat (newstr, " ");
                           len = strlen(newstr);
                           newstr[len] = tokens[j];
                           newstr[len+1] = '\0';
                           strcat (newstr, " ");
                           sprintf (itoa_result, "%d\0", numbers[j+1]);
                           strcat (newstr, itoa_result);
                        }
                     len = strlen(newstr);
                     newstr[len+1] = '\0';
                     printf ("Newstr = %s\n", newstr);
                     goto parse_again; 
                  }
            }

   // Now do + and -
   marker = 0; num_ints = 0; num_tokens = 0;

   numbers[num_ints++] = atoi(element[marker++]);
   while (marker < num_elements)
      {
         tokens[num_tokens++] = *(element[marker++]);
         numbers[num_ints++] = atoi(element[marker++]);
      }

   printf ("num_ints = %d, num_tokens = %d, num_elements = %d\n", 
       num_ints, num_tokens, num_elements);

   if (num_ints == 1)
      {
         return numbers[0];
      }

   final_result = 0;  
   i = 0;
   final_result += numbers[0];
   num_ints--;

   while (num_ints > 0)
      {
         switch (tokens[i])
            {
            case '+':
               final_result += numbers[i+1];
               break;
            case '-':
               final_result -= numbers[i+1];
               break;
            default:
               printf ("Don't recognize token %d %c (%x)\n", i, 
tokens[i], 
tokens[i]);
               exit (1);
            }
         num_ints--; i++;
       }

   printf ("Returning %d\n", final_result);
   return final_result;
}

int main()
{
   int result;
   char expr[500];
   // strcpy (expr, "5 * 2 + 3 * 5 - 10 + 6 * 9 * 2");   

   strcpy (expr, "1 * 2 * 3 * 4 * 5 * 6");

   // strcpy (expr, "( 1 + 2 ) * ( 3 - 9 ) + ( 2 + 5 * 10 )");
   parenPermutations (expr);
   return 0;
}