Algorithms and OOD (CSC 207 2014F) : Assignments
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [Learning Outcomes] [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Student-Curated Resources] [Java 8 API] [Java 8 Tutorials] [Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2014S (Rebelsky)] [CSC 207 2014F (Walker)] [CSC 207 2011S (Weinman)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Due: 10:30 p.m., Tuesday, 16 September 2014
Summary: In this assignment, you will explore strings and the parsing of strings. Along the way, you will consider the design and implementation of some simple classes, some issues in numeric computation, and the use of arrays in Java.
Purposes: To help you think about types in Java. To give you experience reading the Java API. To improve your skills at string processing (in Java and beyond). To continue exploring the relationships between C and Java.
Collaboration: You must do this assignment in groups of two, three, or four students. You may form a group yourself or you may ask me to randomly assign you to a group. If you form your group yourself, you may not choose partners who you worked with on the previous assignment. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Wrapper (Prologue): Individually read through this assignment and make sure that you understand what is required. Then use the form available at http://bit.ly/207hw4pro to indicate (a) how long you think this assignment will take and (b) what you think will be the most challenging aspect of this assignment.
Wrapper (Epilogue): When you are done with the assignment, fill out the form available at http://bit.ly/207hw4epi to indicate (a) how long the assignment took, (b) what the most challenging part of the assignment was, and (c) something important you learned from doing the assignment. If you find that the assignment took much less or much more time than you expected, also include (d) a note as to what might have led to that difference.
Submitting:
Please put all of your work in a GitHub repository named
csc207-hw4
. Email the address of that
repository to
grader-207-01@cs.grinnell.edu. Please use a subject of “CSC207
2014F Assignment 4 (Your Name)”.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
Since we'll be testing array procedures in this lab, you may find
the assertArrayEquals
is helpful. You'll find that
the assertArrayEquals
has the expected parameters.
You can read more at http://junit.sourceforge.net/javadoc/org/junit/Assert.html
a. Create a new Eclipse project for this assignment. You can name the project whatever you like, provided it's not in bad taste.
b. Create a new package in the project. You may choose the name
(again, provided it's in good taste). I would suggest
edu.grinnell.csc207.username.utils
.
c. Copy the Fraction
class from a recent lab into your
project. Make sure to add a note to the top of the class citing the
original authors of the class and the peers who helped you update the
class.
d. Create two utility classes, StringUtils.java
and
Calculator.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.
Fraction(String str)
constuctor. Your constructor
should accept all reasonable strings that describe fractions,
including strings that do and do not include a slash (e.g.,
new Fraction("1/2")
should create the fraction 1/2
and new Fraction("17")
should create the fraction
17/1). You need not handle strings that represent decimal values.
(You are aslo free to handle such strings, if you'd like.)
negate()
method that returns a new
fraction which is the additive inverse of the original fraction.
multiply(Fraction multiplicand)
method
that returns the new fraction that results of multiplying the fraction
by the multiplicand.
subtract(Fraction subtrahend)
method that returns the
new fraction that results from subtracting the subtrahend from the fraction.
divide(Fraction divisor)
method that returns the
new fraction that results from dividing the fraction by the divisor.
pow(int expt)
method that returns the new fraction that
results from raising the given fraction to the given exponent, which
may be positive, negative, or zero.
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).
The string segmentation problems stem from a laboratory on strings that I wrote in the distant past.
The first two fraction problems were inspired by the lab on fractions.
I've assigned variants of the calculator problems over the years. The first is copied directly form an assignment given in a previous semester. The second is new (at least in the current form), although the idea is not.