
April 6th, 2009, 09:40 AM
#1
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!

April 6th, 2009, 10:07 AM
#2
Re: search algorithm for formatted fractions
Have you considered using a regex to search for the pattern.

April 6th, 2009, 10:13 AM
#3
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.

April 6th, 2009, 10:24 AM
#4
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.

April 6th, 2009, 10:27 AM
#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.

April 6th, 2009, 12:10 PM
#6
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.

April 7th, 2009, 07:07 AM
#7
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?

April 7th, 2009, 10:22 AM
#8
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.
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

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
