Loading...

​​Lab 2.5: Rational Expressions

​​Bard College – Computer Science – Data Structures

​​

​​In the next lab, we will build upon our Fraction​ class from last week. 

​​

​​First, we’ll collect everyone’s unit tests and refine your own implementation to make sure it passes all of our tests.

​​

​​Next, we’ll provide a more user-friendly calculator to perform Rational arithmetic, or in other terms, adding, subtracting, multiplying, and dividing fractions. 

​​

​​​​$\frac{407}{409} + \frac{409}{419} + \frac{419}{421} + \frac{421}{431} = \frac{122618373044}{31095439321}$​

​​

​​Using BigInteger​ & Fraction​ was a little cumbersome, but allowed exact arithmetic.

​​

​​Fraction f1 = new Fraction(407, 409);

​​Fraction f2 = new Fraction(409, 419);

​​Fraction f3 = new Fraction(419, 421);

​​Fraction f4 = new Fraction(421, 431);

​​System.out.println(f1.add(f2).add(f3).add(f4));

​​122618373044/31095439321

​​

​​It would be nicer to write these expressions more like traditional math:

​​

​​( ( 407 / 409 ) + ( 409 / 419 ) + ( 419 / 421 ) + ( 421 / 431 ) )            [input]

​​122618373044/31095439321                                                     [output]

​​

​​Adapt Dijkstra’s Two-Stack Algorithm for Expression Evaluation (Evaluate​ on pg. 129) to use Fraction arithmetic.  

​​( 407 / 409 ) 

​​( ( 407 / 409 ) + ( 409 / 419 ) )

​​( ( ( 407 / 409 ) + ( 409 / 419 ) ) + ( 419 / 421 ) )

​​Submission

​​Submit an updated Fraction.java​ file (with a new main​) in a zipped folder named cmsc201-lab2.5-lastname-firstname​. You can update your FractionTest​  and Fraction​ classes as well. Bring hard copies of the Java code to class on Friday. Be sure to include your name, date, email, lab description and collaboration statement. 

​​Bonus

​​The book’s Evaluate​ class assumes the expressions are fully parenthesized. Implement the shunting yard algorithm to convert arbitrary infix mathematical expressions to postfix. 

​​

​​echo "3 + 4 * 2 / ( 1 - 6 )" | java PostfixConverter

​​3 4 2 * 1 6 - / +

​​

​​Then use the code we discussed in class to evaluate those postfix expressions.

​​

​​echo "3 + 4 * 2 / ( 1 - 6 )" | java PostfixConverter | java PostfixEvaluator

​​7/5

​​

​​

​​