CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: search algorithm for formatted fractions

1. Junior Member
Join Date
Apr 2009
Posts
5

## 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. Elite Member Power Poster
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. Member +
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. Junior Member
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. Junior Member
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. Elite Member Power Poster
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. Member +
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. Junior Member
Join Date
Apr 2009
Posts
5

## Re: search algorithm for formatted fractions

Originally Posted by ProgramThis
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.

#### Posting Permissions

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