Collective Fraction Test

First, we’ll collect everyone’s unit tests and we refine our own implementations to make sure we pass all of our tests. Use the new repl.it link in the Google Classroom; only change Main.java

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

Submit an updated Fraction.java file (with a new main) in a zipped folder named cmsc201-lab2.5-lastname-firstname. You can 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 Test

​​Infix Expression Evaluation

​​Submission

​​Bonus

Collective Fraction Test

Infix Expression Evaluation

Submission

Bonus