help on finding a better algorithm

This is a discussion on help on finding a better algorithm within the C Programming forums, part of the General Programming Boards category; hello all , i want to know how it is possible to tokenize a string such as Y = 5X^2 ...

  1. #1
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492

    help on finding a better algorithm

    hello all , i want to know how it is possible to tokenize a string such as
    Y = 5X^2 + 6X^-5 + 12X^4-7X^6 so that the algorithm doesn't affect negative numbers i mean :
    if i use strtok(string"+-") this would simply wipe out any - or + sign it finds! so needless to say , i can not have the negative powers such as -2 in the above given string .
    how should i go about it ?
    thanks in advance
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Do you know it will always be polynomial-ish? If so, then (1) read coefficient (2) read "X^" (3) read power (4) lather (5) rinse (6) repeat. (Note that you have your choice: given ... -7X^6, you can say that the - is the operation, or + is the operation and -7 is the coefficient.)

  3. #3
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    Quote Originally Posted by tabstop View Post
    Do you know it will always be polynomial-ish? If so, then (1) read coefficient (2) read "X^" (3) read power (4) lather (5) rinse (6) repeat. (Note that you have your choice: given ... -7X^6, you can say that the - is the operation, or + is the operation and -7 is the coefficient.)
    Excuse me but what is polynomial? i have never heard that word!
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    147
    I would simply run through the source string one character at a time, looking for candidate operators vs numeric characters, creating objects representing the operands and operators as they are discovered, such that when your finished looping through the string, the objects can 'chain' together to perform the operations required.

  6. #6
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    thank you very much , by the way does C support reference parameters like C++?
    ( i mean in function sth like func(&x); do we have it in C?
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Not references, but you can pass a pointer to a function, and it will work almost like a reference, with the difference that you need to use *x to reference variable x.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by matsp View Post
    Not references, but you can pass a pointer to a function, and it will work almost like a reference, with the difference that you need to use *x to reference variable x.

    --
    Mats
    And with the possibility that the pointer is NULL, where as with references, that's not allowed to happen.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    thanks guys, i've come up with a function!, but there is a problem which i dont know what it is
    and i dont know where i messed it up!
    here , in this function , i try to separate each expression in the formula entered by user, and in each call, the next expression would be retrieved ( for example consider the formula : y = 4X^2 + 3X^-2 + 5X^7 . contains 3 expressions , 4X^2, 3X^-2 and finally 5X^7 ,)
    actually after that the expression is recognized ( for example 4X^2 ) , it would be used to give us the multipicant and the power of the expression , so the bottom line is :
    get the full formula , find the next expression , and retrieve the multipicant and power of that expression,

    here is the function , i would appreciate your help on this :
    Code:
    char * return_expo(char string[],int size,double *Multipicant,double *Power)
    {
            char * expoo =" ";
            char Multipicant_char[5];
            char Power_char[5];
            static int i = 0;
            int j = 0;
            int count = 0;
            int counter = 0;
    
            while ( string [i] !='\0') //y = 2X^3 + 3X^-3 + 4X^4
            {
                  if ( i == 0)
                  {
    
                            if ( string [i] = 'y' || string [i] == 'Y' )
                           {
                                   i++;
                                   continue;
                           }
                           if ( string [i] == ' ' )
                           {
                                   i++;
                                   continue;
                           }
                          
                           while ( string[i]!= 'x' || string[i] != 'X' )
                           {
    
                                  Multipicant_char[j]=string[i];
                                  i++;
                                  j++;
                           }
                   //Power
                           if ( string[i] =='^')
                           {
                                   i++;//baraye eshare kardan be elemente bad az ^
                                   do {
                                          Power_char[j] = string[i];
                                          i++;
                                          j++;
                                      } while ( string[i] !='-' || string[i] !='+' );
                           }
                           break;
                  }
    
                  //when its not the first expression to be scanned .
                  else
                  {
                          if ( string[i] == ' ')
                          {
                                  i++;//used to skip spaces
                                  continue;
                          }
    
                          while (string[i] != 'x' || string[i] != 'X')
                          {
                                  Multipicant_char[j]=string[i];
                                  i++;
                                  j++;
                          }
    
                    //Power
                           if ( string[i] =='^')
                           {
                                   i++;//in this loop , i'm trying to get the power with its sign (indicating being negative or not)
                                   do {
                                          Power_char[j] = string[i];
                                          i++;
                                          j++;
                                      } while ( string[i] !='-' || string [i] != '+');
                           }
                  }
                  break;
    
            }
    
    
    
            *Multipicant = atof(Multipicant_char);
            *Power = atof(Power_char);
    
    
            return expoo;//so far its not needed , just retrieve the multipicant and power
    }
    Last edited by Masterx; 05-29-2009 at 06:09 AM.
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Instead of using the "legal goto" of continue, why not write:
    Code:
    if (x)
    ...
    else if (y) 
    ... 
    else 
    ...
    Code:
                         while ( string[i]!= 'x' || string[i] != 'X' )
                           {
    
                                  Multipicant_char[j]=string[i];
                                  i++;
                                  j++;
                           }
    Repeated twice, so you may want to make it into a function?

    Code:
                                  do {
                                          Power_char[j] = string[i];
                                          i++;
                                          j++;
                                      } while ( string[i] !='-' || string[i] !='+' );
    This is repeated twice. Make it a function?

    What is the break at the end of each half of the big if/else parts for? Doesn't make sense to me.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    Quote Originally Posted by matsp View Post
    Instead of using the "legal goto" of continue, why not write:
    Code:
    if (x)
    ...
    else if (y) 
    ... 
    else 
    ...
    Code:
                         while ( string[i]!= 'x' || string[i] != 'X' )
                           {
    
                                  Multipicant_char[j]=string[i];
                                  i++;
                                  j++;
                           }
    Repeated twice, so you may want to make it into a function?

    Code:
                                  do {
                                          Power_char[j] = string[i];
                                          i++;
                                          j++;
                                      } while ( string[i] !='-' || string[i] !='+' );
    This is repeated twice. Make it a function?

    What is the break at the end of each half of the big if/else parts for? Doesn't make sense to me.

    --
    Mats
    tanx, i used those breaks to avoid the next iteration to happen! i mean if the expression is found! and multipicant_char and power_char are initialized with proper data, then get out of the loop , convert them to integers and send them , and again in the next call continue the loop, from where it was interrupted!
    Last edited by Masterx; 05-29-2009 at 06:32 AM.
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  12. #12
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    hey guys, i wrote another function, which i think makes more sense ,
    again the function would calculate each expression's multipicant and power in each call, and this is how it works
    suppose we have a formula like : 4X^2 + 3X^5 - 65X^-5
    so there are 3 expressions in the formula. because i declared 'i' as static, in each call, it would resume the process and continue from where it was intruptted and thus , fetching the next expression and calculating the stuff.
    however , its not working!and i know which part is malfunctioning but have no idea why it is doing so!
    can you tell me why?
    by the way i used those printf()s to trace the program and see whats going on down there! so that i can be able to figure out what the problem is :
    so far i undrstood that the problem is caused by the inner loop, which calculates Power!, i dont know why it keeps going and going! instead of stopping when encountered to either '-' or '+' ( meaning a new operator and thus meaning the end of this current expression)
    it seems it ignores the sign and keeps going! dont know how to get it out of that loop! it doesnt even check the if statement i placed inside the loop!

    guilty loop:
    Code:
     if ( string[i] =='^')
                            {
                                    i++;
                                    do {
    
                                            if ( k == 0)
                                            printf("\ninside 1...inside Power do while string = %c i = %d k = %d\n",string[i],i,k);
    
                                            Power_char[k] = string[i];
                                            i++;
                                            k++;
                                            
                                            printf("\ninside 2...inside Power do while string = %c i = %d k = %d\n",string[i],i,k);
    
                                            if ((string[i] == '-') || (string[i] == '+') )
                                            {
                                                    printf("\n in if(Power) string[%d] = %c",i,string[i]);
                                                   // i++;
                                                    break;
                                            }
    
                                       }while ((string[i] != '-') || (string[i] != '+') );
    
    
                                       if ((string[i] == '-') || (string[i] == '+') )
                                       {
                                               printf("\n in if(Power) string[%d] = %c",i,string[i]);
                                               //i++;
                                               break;
                                       }
                            }
    the whole function:

    Code:
    void return_expo(char string[],int size,double *Multipicant,double *Power)
    {
            char * expoo =" ";
            char Multipicant_char[5];
            char Power_char[5];
            static int i = 0;
            int j = 0;
            int count = 0;
            int counter = 0;
            int k =0;
    
    
            do
            {
                    printf("\ninside firs do..while..\n");
                    while (string[i]!='x' || string[i]!='X')
                    {
                            //printf("\ninside first do..while..inside Multipicant while string = %c i = %d j = %d\n",string[i],i,j);
                            Multipicant_char[j] = string[i];
                            i++;
                            j++;
                            //printf("\ninside first do..while..inside Multipicant while string = %c i = %d j = %d\n",string[i],i,j);
    
                            if (string[i] =='x' || string[i] =='X')
                            {
                                    i++;
                                    break;
                            }
    
                    }
                    printf("\ninside first do..while..after Multipicant while string = %c i = %d j = %d\n",string[i],i,j);
    
                            if ( string[i] =='^')
                            {
                                    i++;
                                    do {
    
                                            if ( k == 0)
                                            printf("\ninside 1...inside Power do while string = %c i = %d k = %d\n",string[i],i,k);
    
                                            Power_char[k] = string[i];
                                            i++;
                                            k++;
                                            
                                            printf("\ninside 2...inside Power do while string = %c i = %d k = %d\n",string[i],i,k);
    
                                            if ((string[i] == '-') || (string[i] == '+') )
                                            {
                                                    printf("\n in if(Power) string[%d] = %c",i,string[i]);
                                                  //  i++;
                                                    break;
                                            }
    
                                       }while ((string[i] != '-') || (string[i] != '+') );
    
    
                                       if ((string[i] == '-') || (string[i] == '+') )
                                       {
                                               printf("\n in if(Power) string[%d] = %c",i,string[i]);
                                             //  i++;
                                               break;
                                       }
                            }
    
                            printf("\n what? %c ",string[i]);
    
            }while ( (string[i] !='-') ||(string[i] !='+' ) );
    
            i++;
            printf("\nOutside the loop i = %d j = %d\n",i,j);
    
    
    
    
    
    
            *Multipicant = atof(Multipicant_char);
            *Power = atof(Power_char);
    
    
            return ;
    }
    tanx
    Last edited by Masterx; 05-30-2009 at 07:36 PM.
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  13. #13
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    heres a screenshot! can anyone explain why this happens ? it seems it just skips! the signs!
    http://i40.tinypic.com/33begpk.jpg
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  14. #14
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    492
    anyhelp, i would really appreciate any kind of tips or suggestion to solve this problem
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  15. #15
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Wow, something strange definitely happened to that "+". Use %d instead of %c in your printf statement to find out what:

    Code:
    printf("\ninside 2...inside Power do while string = %d i = %d k = %d\n",string[i],i,k);
    This will give the byte value of a signed char, a number between -128 and 127. These correspond to the ASCII table. Obviously, it is not a printable character, but it still must have a value and that may give you a clue (I would guess it is now 0 instead of 43, '+').

    Do you do anything to the string before it entered the return_expo() function?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help finding a simple 'shortest path' algorithm
    By ashley in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 12:38 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Finding the algorithm that's right for you.
    By sean in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 02-03-2002, 09:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21