This time College Board has us working with ArrayLists on the Delimiters free response question on the 2019 AP Computer Science Exam.
What we’re beiong asked to implement is a couple of methods that determine if a sentence is properly balanced using delimiters.
For example, (x + y) = (y + x)
is properly delimited because there are the same number of opening delimiters (
as closing delimiters )
and every opening delimiter has a matching closing delimiter. For example, (x + y)) = (y + x
is not properly delimited. There are the right number of opening and closing delimiters, but they don’t partner up correctly.
Head on over to the College Board website for the full problem, but we need to talk about instance variables. The Delimiters
class has 2, and we’ll need them for our solutions.
private String openDel;
private String closeDel;
These are the opening and matching closing delimiters to use in our solutions.
In Part A we’re implementing a method that goes through an array of tokens and adds the delimiters it finds into an ArrayList.
For example, in the string ( x + y ) = ( y + x )
, and assuming that openDel.equals("(")
and closeDel.equals(")")
, it should return the list ["(", ")", "(", ")"]
.
public ArrayList<String> getDelimitersList(String[] tokens) {
ArrayList<String> out = new ArrayList<>();
for (String t: tokens) {
if (t.equals(openDel) || t.equals(closeDel))
out.add(t);
}
return out;
}
What I did was to iterate through tokens and every time it finds a matching open or closing delimiter it adds it onto the end of out and then returns out at the end.
Next up we need to determine is a statement is balanced based on the ArrayList returned from Part A.
A statement is considered balanced if
public boolean isBalanced(ArrayList<String> delimiters) {
int open = 0;
int close = 0;
for (String d: delimiters) {
if (d.equals(openDel)) {
open++;
} else if (d.equals(closeDel)) {
close++;
}
if (close > open) return false;
}
return open == close;
}
What I did was to iterate through and count the number of opening and closing delimiters as it goes. If, at any point in the iteration it finds that the code has counted more closing delimiters than opening delimiters it returns false
because it has failed the first condition.
At the end it returns true
if the two counts match or false
if not.