Assignment 4: Playful Parsing in Java

Your fraction class will need the following constructors and methods, many of which you may have created in a previous laboratory. Add any that it does not yet include.

Suppose we decide that fractions are always represented in simplest form. That is, the numerator and denominator have no common fractors, the denominator is always positive, and if the numerator is 0, then the denominator is 1.

Update the Fraction class so that it follows this policy.

Programmers often find it convenient to store compound data in a text file with one line per entry. To separate the components of the entry, they use some designated symbol, such as a colon. For example, we might store movie ratings in a form like the following:

movietitle:rating:rater:date

Write and test a procedure, StringUtils.splitAt, that takes as input a string and a character to use in splitting the string and returns an array of the appropriate substrings. For example,

assertArrayEquals(new String[] { "a", "b", "c" },
                  StringUtils.splitAt("a:b:c", ':'));
assertArrayEquals(new String[] { "a", "b", "c" },
                  StringUtils.splitAt("a b c", ' '));
assertArrayEquals(new String[] { "a:b:c" },
                  StringUtils.splitAt("a:b:c", ' '));
assertArrayEquals("one field", new String[] { "a" },
                  StringUtils.splitAt("a", ':'));
assertArrayEquals("empty inner field", new String[] { "a", "", "c" },
                  StringUtils.splitAt("a::c", ':'));
assertArrayEquals("leading empty field", new String[] { "", "a" },
                  StringUtils.splitAt(":a", ':'));
assertArrayEquals("trailing empty field", new String[] { "a", "" },
                  StringUtils.splitAt("a:", ':'));

In implementing splitAt you may not use use the split method of java.util.String. (Yes, that's right, you have to implement a simpler version of that method by hand. Don't worry, it's good experience.)

One disadvantage of the “split at this character” strategy is that you cannot easily use the separator within one of the fields. Data designers have chosen a variety of approaches to handle the issue. One of the most common is to say “if the separator appears within text surrounded by double quotation marks, take it as part of the field, rather than as a separator”.

For example, consider the following input file.

Reilly,Computer Science,2014
Smith,Reilly,Math,2015
"Smith,Reilly",GenSci/CS,2016

But even that approach has its own potential problems. For example, what if we want both the separator and a quote in a field. Once again, there is a common solution: “if two double quotation marks appear in sequence, treat them as a single character, rather than as the end of a string”.

For example, consider the following input file.

a,the first letter of the English alphabet
',a single quotation mark
"",the empty string
",",a comma
"""",a double-quotation mark
""",""",a comma surrounded by double-quotation marks

Write and test a procedure, StringUtils.splitCSV, that splits a string using those policies, with a comma as the separator, and returns an array of the fields. For example,

assertArrayEquals(new String[] { "a", "b", "c" },
                  StringUtils.splitCSV("a,b,c"));
assertArrayEquals(new String[] { "a,b", "c" },
                  StringUtils.splitCSV("\"a,b\",c"));
assertArrayEquals(new String[] { "a", "b,b\"", "c" },
                  StringUtils.splitCSV("a,\"b,b\"\"\",c"));
assertArrayEquals(new String[] { "a", "b\"b", "c" }, 
                  StringUtils.splitCSV("a,\"b\"\"b\",c"));

(Yeah, aren't backslash quotation marks a wonder in C-like languages?)

You may assume that the input is in correct CSV format. (So you don't need to deal with strings that have an odd number of quotation marks.) Of course, those who want to do an exceptional job probably deal with erroneous input in a sensible way, reporting where the error occurred.

If you're not sure how a line of CSV should be parsed, save it in a file with a .csv suffix and open it with a spreadsheet application such as LibreOffice, Google Spreadsheets, Microsoft Excel, or Excel365.

As you know, one of the primary uses of computers is to compute with numbers - that is, to calculate. A typical computer calculator needs to read and parse textual input, do the computation, and return a result. In this part of the assignment, we will simulate that behavior.

Write a method, Calculator.eval0, that takes as input a string that represents an arithmetic expression over the integers and returns the result of evaluating that expression (as a BigInteger). You may assume that numbers and operators are separated by spaces. You should use the “naive” approach to calculation: Do operations in the order they appear, rather than paying attention to precedence. You should support the operations +, -, *, /, and ^ (exponentation). For example,

assertEquals(BigInteger.valueOf(0), Calculator.eval0("0"));
assertEquals(BigInteger.valueOf(2), Calculator.eval0("1 + 1"));
assertEquals(BigInteger.valueOf(4), Calculator.eval0("1 + 2 + 1"));
assertEquals(BigInteger.valueOf(9), Calculator.eval0("1 + 2 * 3"));

Your calculator must support arbitrarily large integers. For example, you should get the correct answer for Calculator.eval0 ("2 ^ 64"). You can achieve this result by using java.lang.BigInteger for your data values.

Write a method, Calculator.eval1, that takes as input a string that represents an arithmetic expression over fractions and returns the result of evaluating that expression (as a Fraction). You may assume that numbers and operators are separated by spaces. You should use the “naive” approach to calculation: Do operations in the order they appear, rather than paying attention to precedence. You should support the operations +, -, *, /, and ^ (exponentation).