Fraction Class Calculator

Problem

Each input line is OPERATION a b c d, where OPERATION is add, sub, mul or div, and the line means the fractions a/b and c/d. Print the result as a reduced fraction n/d with a positive denominator. If the denominator is 1, print only n. Print error if any denominator is zero, or if you divide by a fraction that is zero. Write a Fraction class with one method for each operation.

Constraints

  • 1 <= lines <= 10^4
  • |numbers| <= 10^6

Examples

Input

add 1 2 1 3
div 1 2 0 5

Output

5/6
error

Solutions

Best approachTime O(n log V)Space O(n)

Reducing inside the constructor means every Fraction object is always in its simplest form. Moving the minus sign to the numerator makes the output unique. Dividing by a zero fraction gives a zero denominator, so the same check catches it.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several lines.
 * Output  : One result per line.
 * Approach: A Fraction class.
 * Time    : O(n log V)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A Fraction keeps a numerator and a denominator. The constructor reduces it and keeps the sign on top.
        static final class Fraction {
            private final long numerator;
            private final long denominator;

            Fraction(long numerator, long denominator) {
                if (denominator == 0) {
                    throw new ArithmeticException("zero denominator");
                }
                long divisor = gcd(Math.abs(numerator), Math.abs(denominator));
                if (divisor == 0) {
                    divisor = 1;
                }
                long sign = denominator < 0 ? -1 : 1;
                this.numerator = sign * numerator / divisor;
                this.denominator = sign * denominator / divisor;
            }

            private static long gcd(long a, long b) {
                return b == 0 ? a : gcd(b, a % b);
            }

            // Step 2: Each operation returns a new Fraction. The old objects do not change (immutable).
            Fraction add(Fraction other) {
                return new Fraction(numerator * other.denominator + other.numerator * denominator, denominator * other.denominator);
            }

            Fraction subtract(Fraction other) {
                return new Fraction(numerator * other.denominator - other.numerator * denominator, denominator * other.denominator);
            }

            Fraction multiply(Fraction other) {
                return new Fraction(numerator * other.numerator, denominator * other.denominator);
            }

            Fraction divide(Fraction other) {
                return new Fraction(numerator * other.denominator, denominator * other.numerator);
            }

            @Override
            public String toString() {
                return denominator == 1 ? String.valueOf(numerator) : numerator + "/" + denominator;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        String[] output = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            String[] part = lines[i].split(" ");

            // Step 3: Make the fractions and choose the operation. A zero denominator throws an exception, and we print error.
            try {
                Fraction first = new Fraction(Long.parseLong(part[1]), Long.parseLong(part[2]));
                Fraction second = new Fraction(Long.parseLong(part[3]), Long.parseLong(part[4]));
                Fraction result;
                if (part[0].equals("add")) {
                    result = first.add(second);
                } else if (part[0].equals("sub")) {
                    result = first.subtract(second);
                } else if (part[0].equals("mul")) {
                    result = first.multiply(second);
                } else {
                    result = first.divide(second);
                }
                output[i] = result.toString();
            } catch (ArithmeticException error) {
                output[i] = "error";
            }
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (1)
  1. Where does the minus sign go?