Delimiters: 2019 FRQ 3

Matching opening and closing symbols — parentheses in math, tags in HTML — comes up everywhere in programming, and this AP Computer Science A free-response question builds a small, general-purpose checker for exactly that pattern: first pulling the delimiters out of a larger array of tokens, then verifying they're properly balanced.

What This FRQ Tests

• AP CSA units: Unit 6 (Array), Unit 7 (ArrayList)
• Core skill: filtering a plain array down into a new ArrayList by checking each element against a condition
• Secondary skill: validating a balanced/nested sequence with a single running counter, without needing a stack
• Official category: "Array/ArrayList" — always FRQ 3 on the AP CSA exam

The Setup

• The given Delimiters class has:
  • private String openDel and private String closeDel — the specific open/close delimiter strings for this object (e.g. "(" and ")", or "<sup>" and "</sup>")
  • A constructor: Delimiters(String open, String close)
• You're asked to write two methods:
  • getDelimitersList(String[] tokens) — returns an ArrayList<String> containing only the tokens that are exactly an open or close delimiter, in their original order
  • isBalanced(ArrayList<String> delimiters) — returns whether that list of delimiters is validly balanced
• "Balanced" has two precise conditions, both of which must hold:
  1. Scanning left to right, the running count of close delimiters seen so far never exceeds the running count of open delimiters seen so far.
  2. By the end, the total count of open delimiters equals the total count of close delimiters.

Part (a): Writing getDelimitersList(String[] tokens)

Step-by-Step Approach

1. Create an empty ArrayList<String> to collect matches.
2. Loop over every index of the tokens array.
3. Check whether that token is exactly equal to openDel or exactly equal to closeDel.
4. If either matches, add it to the ArrayList — otherwise skip it (it's just ordinary text, not a delimiter).
5. Return the ArrayList after the loop finishes.

The Code

public ArrayList<String> getDelimitersList(String[] tokens)
{
    ArrayList<String> result = new ArrayList<String>();

    for (int i = 0; i < tokens.length; i++)
    {
        if (tokens[i].equals(openDel) || tokens[i].equals(closeDel))
        {
            result.add(tokens[i]);
        }
    }

    return result;
}

Why Each Piece Matters

• tokens[i].equals(openDel) — a String comparison always uses .equals(), never ==, exactly as in 2022's Textbook.canSubstituteFor(). Two different String objects can hold identical text but still fail a == check.
• The || means a token only needs to match one of the two delimiters to be kept — it can never match both, which would be impossible for any single token anyway.
• Non-matching tokens are simply never added — there's no else branch needed, since "skip it" and "do nothing" are the same action here.
• result.add(tokens[i]) preserves the original order automatically, since the loop visits tokens strictly left to right.

Tracing the Example

Using Example 2 from the question, where openDel is "<q>" and closeDel is "</q>":

Final result: ["<q>", "</q>", "</q>"] — matches the question's expected ArrayList exactly.

Common Mistakes to Avoid

• Using == instead of .equals() to compare tokens[i] against openDel/closeDel — a classic AP CSA point loss any time Strings are compared.
• Using if/else if instead of ||, and accidentally only ever checking one of the two delimiters.
• Forgetting that non-delimiter text (like "yy" or " * 5") should simply be skipped, not added as-is or replaced with anything.

Part (b): Writing isBalanced(ArrayList<String> delimiters)

The Rule, Broken Down

1. Walk through the list from front to back, keeping a running difference between opens seen and closes seen.
2. If that running difference ever goes negative, the sequence is unbalanced immediately — stop and return false.
3. If the scan finishes without ever going negative, the sequence is balanced only if the running difference is exactly zero at the very end.

Step-by-Step Approach

1. Start a counter at 0.
2. Loop over every element of the delimiters list.
3. If the element equals openDel, increment the counter; otherwise (it must be closeDel, per the method's precondition) decrement it.
4. After each update, check whether the counter went negative — if so, return false right away.
5. After the loop finishes normally, return whether the counter equals exactly 0.

The Code

public boolean isBalanced(ArrayList<String> delimiters)
{
    int count = 0;

    for (int i = 0; i < delimiters.size(); i++)
    {
        if (delimiters.get(i).equals(openDel))
        {
            count++;
        }
        else
        {
            count--;
        }

        if (count < 0)
        {
            return false;
        }
    }

    return count == 0;
}

Why Each Piece Matters

• The else branch (rather than an explicit .equals(closeDel) check) relies on the method's own precondition — delimiters contains only valid open and close delimiters, so anything that isn't an open delimiter must be a close one.
• Checking count < 0 inside the loop, immediately after each update, is what catches condition 1 ("never more closes than opens at any point"). Checking only at the very end would miss a mid-sequence violation that happens to get balanced back out later.
• return count == 0 (rather than return true) after the loop is what enforces condition 2 — a sequence that never goes negative but ends with leftover unmatched opens is still not balanced.
• delimiters.get(i) is how you read one element from an ArrayList by position — the ArrayList equivalent of tokens[i] for a plain array.

Tracing the Example

Using Example 1 from the question, where openDel is "<sup>" and closeDel is "</sup>":

The count never goes negative, and it ends at exactly 0 — isBalanced returns true, matching the question.

The other three examples in the question confirm both failure conditions:

• Example 2 ("<sup>", "</sup>", "</sup>", "<sup>") goes negative at the third token — two closes have now been seen against only one open — so condition 1 fails there, and the method returns false immediately, without ever looking at the fourth token.
• Example 3 ("</sup>") goes negative on the very first token, since there's no matching open yet — condition 1 fails immediately.
• Example 4 ("<sup>", "<sup>", "</sup>") never goes negative, but ends at count = 1, not 0 — condition 2 fails, caught only by the final return count == 0 check.

Common Mistakes to Avoid

• Only checking the final count and skipping the mid-scan count < 0 check. This would incorrectly accept a sequence that has a close delimiter appear before any matching open, as long as the totals happen to balance out by the very end.
• Checking count <= 0 instead of count < 0. A count of exactly 0 in the middle of a valid sequence (right after a "</sup>" closes out an earlier "<sup>") is perfectly fine and shouldn't trigger a false failure.
• Returning true as soon as the loop finishes, without the final == 0 check — this incorrectly accepts sequences with leftover unmatched opens as balanced.

Key Takeaways

• Filtering an array into a new ArrayList is a two-step loop pattern: check a condition, then add() only the elements that pass.
• A balanced/nested sequence — parentheses, tags, anything with matching open/close pairs — can be checked with a single running counter instead of a full stack: increment on open, decrement on close, and watch for it going negative.
• Two separate failure conditions on the same problem ("goes negative" vs. "doesn't end at zero") need two separate checks — one inside the loop, one after it — don't try to catch both with a single test.