Delimiters Solution

This time College Board has us working with ArrayLists on the Delimiter free response question on the 2019 AP Computer Science exam.

What we’re being asked to implement is a couple of methods that determine if a sentence is properly using delimiters.

For example, (x + y) = (y + x) is properly delimited because there are the same number of opening delimiters ( as closing ) and every opening delimiter has a matching closing delimiter after. 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.

Delimiters class

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.

getDelimitersList

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=="(" and closeDel==")" , 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.

isBalanced

Next up we need to determine if a statement is balanced based on the ArrayList returned from Part A.

A statement is considered balanced if

  • At no point going through the ArrayList have we found more closing delimiters than opening delimiters
  • There are the same number of opening and closing delimiters in the list
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.

CompSci.rocks Newsletter

Want to stay in touch and keep up to date with the latest posts @ CompSci.rocks?

Leave a Reply

Your email address will not be published. Required fields are marked *