CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8
  1. #1
    Join Date
    Apr 2009
    Posts
    5

    Question search algorithm for formatted fractions

    Hello,

    I'm currently writing a program for a java class, and I'm currently having trouble working out an efficient search algorithm. The program is supposed to take a text file and parse it, and any time that it finds a statement of the form (A/B operand X/Y), where A,B,X, and Y are integers, and the operand can be +,-,*, or /. It then takes the statement and creates a Fraction class, for each fraction, and performs the stated operand.

    I'm just wondering what the easiest way to recognize this pattern in a text file would be. The only reasonable solution I can think of would be using the next() function to assure that and array of booleans read true for finding the correct types in order, which would be very inefficient.

    Any help would be greatly appreciated!

  2. #2
    Join Date
    May 2006
    Location
    UK
    Posts
    4,473

    Re: search algorithm for formatted fractions

    Have you considered using a regex to search for the pattern.

  3. #3
    Join Date
    Feb 2008
    Posts
    966

    Re: search algorithm for formatted fractions

    Well it depends: is everything going to be spaced out (whitespace in between) like this: "this fraction 5/6 * 3/9 ..." or like "thisfraction3/4*9/5is..."?

    Second thing: are the fractions themselves spaced or together?
    "5/6 * 9/4" or 5 / 6 * 9 / 4"?

    If the words are properly space (guaranteed) and the fractions are combined then it will be a lot easier for you (if you can control the input). You can read them in a word at a time, keeping a reference to the previous word, and when you find an operand you know the previous fraction (because you kept a reference to the previous) and you can read in the next fraction.

    If you cannot control the data then this becomes a little bit trickier and you have to do something else. The something else might be using a Stack and when you see a "/" you pop the previous characters/word that contains the dividend, pop on the "/" and check the next characters/word to see if it is numeric. If so add it to the stack.
    Then you have to check for the operand, if it is one of your four add it to the stack, otherwise pop everything off of the stack. And you keep doing this until you have found a/b * c/d.

    That is, of course, how I would do it.

  4. #4
    Join Date
    Apr 2009
    Posts
    5

    Re: search algorithm for formatted fractions

    I can't guarantee the formatting of the text file, however I believe that I could use some class to format the file so that there are no spaces, because the text that isn't fraction computation is irrelevant.

  5. #5
    Join Date
    Apr 2009
    Posts
    5

    Re: search algorithm for formatted fractions

    The class that I'm in is a first year java class, and the use of Regex seems a little complex for the class, but if there is no other way to search the file than to confirm each part of the expression, I may have to learn to use it.

  6. #6
    Join Date
    May 2006
    Location
    UK
    Posts
    4,473

    Re: search algorithm for formatted fractions

    If you can't use a Regex (they are not as difficult as they first look but they are almost certainly beyond a first year Java class) and you can't guarantee the format of the input text then you'll need to do as ProgramThis has suggested.

  7. #7
    Join Date
    Feb 2008
    Posts
    966

    Re: search algorithm for formatted fractions

    I am really shocked to hear you say that this is a "first year programming class". At what school MIT? India Institute?

  8. #8
    Join Date
    Apr 2009
    Posts
    5

    Re: search algorithm for formatted fractions

    Quote Originally Posted by ProgramThis View Post
    I am really shocked to hear you say that this is a "first year programming class". At what school MIT? India Institute?
    I was pretty surprised myself... It's just a standard state school, University of Oregon. Not even an advanced class or anything. The last term just started, and It's significantly harder than anything we did the first two terms.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured