Collective Fraction Tests

First, we’ll collect everyone’s unit tests and refine our own Fraction implementations to make sure we pass all of our tests.

Infix Expression Evaluation

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; the values stack should hold Fractions. You do not have to support sqrt. Make this the main method of Fraction.

( 407 / 409 )

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

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

NOTE: You’ll have to add algs4.jar to your repl.it project, and add

import edu.princeton.cs.algs4.*

to the top of Fraction in order to use classes like Stack and StdOut from the textbook.

Submission

Update your Main and Fraction classes as well. Be sure to include your name, date, email, lab description and collaboration statement.

Bonus

As we discussed in class we can evaluate postfix expressions using a single value stack and without any parentheses. Write a program PostfixEvaluator:

echo "3 4 2 * 1 6 - / +" | java PostfixEvaluator

7/5

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 - / +

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

7/5

​​Collective Fraction Tests

​​Infix Expression Evaluation

​​Submission

​​Bonus

Collective Fraction Tests

Infix Expression Evaluation

Submission

Bonus