2 import java.util.Scanner;
3 import java.util.Locale;
4 import java.util.NoSuchElementException;
5 import java.util.Formatter;
6 import java.util.Formattable;
7 import java.util.regex.Pattern;
8 import static java.util.FormattableFlags.ALTERNATE;
9 import static java.util.FormattableFlags.LEFT_JUSTIFY;
10 import java.util.FormatFlagsConversionMismatchException;
11 import java.util.IllegalFormatPrecisionException;
12 import java.util.IllegalFormatException;
13
14 /**
15 * A rational number is stored as an integer pair (numerator, denominator).
16 * The numerator is in the range [-Integer.MAX_VALUE, Integer.MAX_VALUE].
17 * The denominator is in the range of [1, Integer.MAX_VALUE].
18 * The fraction is reduced and zero is stored with denominator 1.
19 * Rational is a value-based class.
20 * @author H.Drachenfels
21 * @version 20.1.2026
22 */
23 public final class Rational extends Number
24 implements Comparable<Rational>, Formattable {
25
26 /**
27 * The number 0 as Rational.
28 */
29 public static final Rational ZERO = new Rational(0, 1);
30
31 /**
32 * The number 1 as Rational.
33 */
34 public static final Rational ONE = new Rational(1, 1);
35
36 /**
37 * The largest positive value of type Rational, Integer.MAX_VALUE.
38 */
39 public static final Rational MAX_VALUE
40 = new Rational(Integer.MAX_VALUE, 1);
41
42 /**
43 * The smallest positive nonzero value of type Rational,
44 * 1 / Integer.MAX_VALUE.
45 */
46 public static final Rational MIN_VALUE
47 = new Rational(1, Integer.MAX_VALUE);
48
49 /**
50 * The numerator part of the rational number.
51 */
52 private final int numerator;
53
54 /**
55 * The denominator part of the rational number.
56 * Always greater or equal 1.
57 * The denominator is 1 if numerator is 0.
58 */
59 private final int denominator;
60
61 /**
62 * Rational number with numerator n and denominator d.
63 * @param n the numerator
64 * @param d the denominator (must not be 0)
65 * @return a Rational with the specified value
66 * @throws ArithmeticException
67 * if numerator n or denominator d is out of range
68 */
69 public static Rational valueOf(int n, int d) {
70 return new Rational(n, d);
71 }
72
73 /**
74 * Converts an integer to a rational number.
75 * This factory method is provided in preference to an (int) constructor
76 * because it allows for reuse of frequently used Rationals.
77 * @param n the integer to convert
78 * @return a Rational with the specified value
79 */
80 public static Rational valueOf(int n) {
81 switch (n) {
82 case 0:
83 return ZERO;
84 case 1:
85 return ONE;
86 case Integer.MAX_VALUE:
87 return MAX_VALUE;
88 default:
89 return new Rational(n, 1);
90 }
91 }
92
93 /**
94 * Converts a string to a rational number.
95 * The string must have the format specified by toString.
96 * @param s the string to convert
97 * @return a Rational with the specified value
98 * @throws NumberFormatException
99 * if the String s does not match the Rational regular expression
100 * @throws ArithmeticException
101 * if numerator n or denominator d is out of range
102 */
103 public static Rational valueOf(String s) {
104 Scanner sc = new Scanner(s);
105 if (!sc.hasNext(FORMAT)) {
106 throw new NumberFormatException(s);
107 }
108
109 sc.useDelimiter("/");
110
111 if (!sc.hasNextInt()) {
112 throw new ArithmeticException("numerator overflow: " + s);
113 }
114 int n = sc.nextInt();
115
116 if (!sc.hasNextInt()) {
117 throw new ArithmeticException("denominator overflow: " + s);
118 }
119 int d = sc.nextInt();
120
121 return new Rational(n, d);
122 }
123
124 private static final Pattern FORMAT = Pattern.compile("^[+-]?\\d+/\\d+$");
125
126 private Rational(long n, long d) {
127 if (d == 0) {
128 throw new ArithmeticException("invalid denominator 0");
129 }
130
131 if (n == 0) {
132 this.numerator = 0;
133 this.denominator = 1;
134 return;
135 }
136
137 int sign = Long.signum(n) * Long.signum(d);
138 long nn = Math.abs(n);
139 long dd = Math.abs(d);
140
141 if (dd != 1) {
142 long f = gcd(nn, dd);
143 nn /= f;
144 dd /= f;
145 }
146
147 if (nn > Integer.MAX_VALUE) {
148 throw new ArithmeticException(
149 String.format("numerator overflow: %d/%d", sign * nn, dd));
150 }
151
152 if (dd > Integer.MAX_VALUE) {
153 throw new ArithmeticException(
154 String.format("denominator overflow: %d/%d", sign * nn, dd));
155 }
156
157 this.numerator = sign * (int) nn;
158 this.denominator = (int) dd;
159 }
160
161 /**
162 * Computes the greates common divisor using Euclid's algorithm.
163 * For negative numbers, the result is undefined.
164 * @param a a positive number
165 * @param b a positive number
166 * @return the gcd of a and b
167 */
168 private static long gcd(long a, long b) {
169 while (a > 0 && b > 0) {
170 if (a > b) {
171 a = a % b;
172 } else {
173 b = b % a;
174 }
175 }
176
177 return Math.max(a, b);
178 }
179
180 /**
181 * Returns the numerator part of the reduced rational number.
182 * @return the numerator
183 */
184 public int numerator() {
185 return this.numerator;
186 }
187
188 /**
189 * Returns the denominator part of the reduced rational number.
190 * @return the denominator
191 */
192 public int denominator() {
193 return this.denominator;
194 }
195
196 /**
197 * Returns the signum function of this Rational.
198 * @return -1, 0 or 1 as the value of this Rational is
199 * negative, zero or positive.
200 */
201 public int signum() {
202 return Integer.signum(this.numerator);
203 }
204
205 /**
206 * Returns a Rational with inverted sign.
207 * @return -this
208 */
209 public Rational negate() {
210 return new Rational(-this.numerator, this.denominator);
211 }
212
213 /**
214 * Returns a Rational with numerator and denominator swapped.
215 * @return 1/this
216 * @throws ArithmeticException if the result is out of range
217 */
218 public Rational invert() {
219 return new Rational(this.denominator, this.numerator);
220 }
221
222 /**
223 * Returns a Rational whose value is (this + r).
224 * @param r value to be added to this Rational
225 * @return this + r
226 * @throws ArithmeticException if the result is out of range
227 */
228 public Rational add(Rational r) {
229 if (this.denominator == r.denominator) {
230 return new Rational((long) this.numerator + r.numerator,
231 this.denominator);
232 }
233
234 long n = (long) this.numerator * r.denominator
235 + (long) r.numerator * this.denominator;
236 long d = (long) this.denominator * r.denominator;
237 return new Rational(n, d);
238 }
239
240 /**
241 * Returns a Rational whose value is (this - r).
242 * @param r value to be subtracted from this Rational
243 * @return this - r
244 * @throws ArithmeticException if the result is out of range
245 */
246 public Rational subtract(Rational r) {
247 if (this.denominator == r.denominator) {
248 return new Rational((long) this.numerator - r.numerator,
249 this.denominator);
250 }
251
252 long n = (long) this.numerator * r.denominator
253 - (long) r.numerator * this.denominator;
254 long d = (long) this.denominator * r.denominator;
255 return new Rational(n, d);
256 }
257
258 /**
259 * Returns a Rational whose value is (this * r).
260 * @param r value to be multiplied by this Rational
261 * @return this * r
262 * @throws ArithmeticException if the result is out of range
263 */
264 public Rational multiply(Rational r) {
265 long n = (long) this.numerator * r.numerator;
266 long d = (long) this.denominator * r.denominator;
267 return new Rational(n, d);
268 }
269
270 /**
271 * Returns a Rational whose value is (this / r).
272 * @param r value by which this Rational is to be divided
273 * @return this / r
274 * @throws ArithmeticException if the result is out of range
275 */
276 public Rational divide(Rational r) {
277 long n = (long) this.numerator * r.denominator;
278 long d = (long) this.denominator * r.numerator;
279 return new Rational(n, d);
280 }
281
282 /**
283 * Returns a string representation of this Rational.
284 * The string representation of the numerator, including the sign,
285 * is followed by '/' and the string representation of the denominator.
286 * @return string representation of this Rational.
287 */
288 @Override
289 public String toString() {
290 return this.numerator + "/" + this.denominator;
291 }
292
293 @Override
294 public boolean equals(Object o) {
295 if (o instanceof Rational) {
296 Rational r = (Rational) o;
297 return this.numerator == r.numerator
298 && this.denominator == r.denominator;
299 }
300
301 return false;
302 }
303
304 @Override
305 public int hashCode() {
306 return this.numerator * 31 + this.denominator;
307 }
308
309 @Override
310 public int intValue() {
311 return (int) ((double) this.numerator / this.denominator);
312 }
313
314 @Override
315 public long longValue() {
316 return (long) ((double) this.numerator / this.denominator);
317 }
318
319 @Override
320 public double doubleValue() {
321 return (double) this.numerator / this.denominator;
322 }
323
324 @Override
325 public float floatValue() {
326 return (float) this.doubleValue();
327 }
328
329 @Override
330 public int compareTo(Rational r) {
331 if (this.denominator == r.denominator) {
332 return Integer.compare(this.numerator, r.numerator);
333 }
334
335 return Long.compare((long) this.numerator * r.denominator,
336 (long) r.numerator * this.denominator);
337 }
338
339 @Override
340 public void formatTo(Formatter f, int flags, int width, int precision) {
341
342 if (precision != -1) {
343 throw new IllegalFormatPrecisionException(precision);
344 }
345
346 if ((flags & ALTERNATE) == ALTERNATE) {
347 throw new FormatFlagsConversionMismatchException("#", 's');
348 }
349
350 String s = this.toString();
351
352 if (width <= s.length()) {
353 f.format(s);
354 return;
355 }
356
357 if ((flags & LEFT_JUSTIFY) == LEFT_JUSTIFY) {
358 f.format("%-" + width + "s", s);
359 return;
360 }
361
362 f.format("%" + width + "s", s);
363 }
364 }
365
366 /**
367 * Test driver.
368 */
369 final class RationalTest {
370 private RationalTest() { }
371
372 /**
373 * Evaluates an arithmetic postfix expression with rational numbers.
374 * Example: java RationalTest 1/2 3/4 add 5/6 multiply
375 * @param args the arithmetic postfix expression with rational numbers
376 */
377 public static void main(String[] args) {
378 Rational[] stack = new Rational[args.length];
379 int top = 0;
380
381 Locale.setDefault(Locale.ENGLISH);
382 Scanner input = new Scanner(System.in);
383
384 for (String arg : args) {
385 try {
386 switch (arg) {
387 case "stackdump":
388 for (int j = 0; j < top; ++j) {
389 System.out.printf("%d: %s (%.15e)%n",
390 j, stack[j], stack[j].doubleValue());
391 }
392 continue;
393 case "negate":
394 stack[top - 1] = stack[top - 1].negate();
395 break;
396 case "invert":
397 stack[top - 1] = stack[top - 1].invert();
398 break;
399 case "add":
400 stack[top - 2] = stack[top - 2].add(stack[top - 1]);
401 --top;
402 break;
403 case "subtract":
404 stack[top - 2] = stack[top - 2].subtract(stack[top - 1]);
405 --top;
406 break;
407 case "multiply":
408 stack[top - 2] = stack[top - 2].multiply(stack[top - 1]);
409 --top;
410 break;
411 case "divide":
412 stack[top - 2] = stack[top - 2].divide(stack[top - 1]);
413 --top;
414 break;
415
416 case "numerator":
417 System.out.printf("%s: %d%n",
418 arg, stack[top - 1].numerator());
419 continue;
420 case "denominator":
421 System.out.printf("%s: %d%n",
422 arg, stack[top - 1].denominator());
423 continue;
424 case "signum":
425 System.out.printf("%s: %d%n",
426 arg, stack[top - 1].signum());
427 continue;
428
429 case "toString":
430 System.out.printf("%s: %s%n",
431 arg, stack[top - 1].toString());
432 continue;
433 case "hashCode":
434 System.out.printf("%s: %d%n",
435 arg, stack[top - 1].hashCode());
436 continue;
437 case "equals":
438 System.out.printf("%s: %b%n",
439 arg,
440 stack[top - 2].equals(stack[top - 1]));
441 continue;
442
443 case "intValue":
444 System.out.printf("%s: %d%n",
445 arg, stack[top - 1].intValue());
446 continue;
447 case "longValue":
448 System.out.printf("%s: %d%n",
449 arg, stack[top - 1].longValue());
450 continue;
451 case "doubleValue":
452 System.out.printf("%s: %.15e%n",
453 arg, stack[top - 1].doubleValue());
454 continue;
455 case "floatValue":
456 System.out.printf("%s: %.7e%n",
457 arg, stack[top - 1].floatValue());
458 continue;
459
460 case "compareTo":
461 System.out.printf("%s: %d%n",
462 arg,
463 stack[top - 2].compareTo(stack[top - 1]));
464 continue;
465
466 case "formatTo":
467 System.err.print("Enter format string: ");
468 try {
469 System.out.printf("%s: " + input.next() + "%n",
470 arg, stack[top - 1]);
471 } catch (NoSuchElementException x) {
472 System.err.println("no input");
473 System.exit(1);
474 }
475 continue;
476
477 case "ZERO":
478 stack[top++] = Rational.ZERO;
479 continue;
480 case "ONE":
481 stack[top++] = Rational.ONE;
482 continue;
483 case "MAX_VALUE":
484 stack[top++] = Rational.MAX_VALUE;
485 continue;
486 case "MIN_VALUE":
487 stack[top++] = Rational.MIN_VALUE;
488 continue;
489
490 case "int":
491 System.err.print("Enter integer: ");
492 try {
493 stack[top] = Rational.valueOf(input.nextInt());
494 ++top;
495 } catch (ArithmeticException x) {
496 System.err.println(input.next() + ": invalid input");
497 System.exit(1);
498 }
499 continue;
500 case "intint":
501 System.err.print("Enter numerator and denominator: ");
502 try {
503 stack[top] = Rational.valueOf(input.nextInt(),
504 input.nextInt());
505 ++top;
506 } catch (ArithmeticException x) {
507 System.err.println(input.next() + ": invalid input");
508 System.exit(1);
509 }
510 continue;
511 default:
512 stack[top] = Rational.valueOf(arg);
513 ++top;
514 continue;
515 }
516
517 System.out.println(arg);
518
519 } catch (ArrayIndexOutOfBoundsException x) {
520 System.err.println(arg + ": missing operand");
521 System.exit(1);
522 } catch (NumberFormatException x) {
523 System.err.println(x.getMessage() + ": not a rational number");
524 } catch (ArithmeticException x) {
525 System.err.println(x.getMessage());
526 } catch (IllegalFormatException x) {
527 System.err.printf("%s: %s%n", arg, x);
528 }
529 }
530
531 for (int j = 0; j < top; ++j) {
532 System.out.printf("%d: %s (%.15e)%n",
533 j, stack[j], stack[j].doubleValue());
534 }
535 }
536 }
537