Computer Science A
2019 FRQ 3
FRQ Question 3
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
- Many encoded strings contain delimiters. A delimiter is a non-empty string that acts as a boundary between different parts of a larger string. The delimiters involved in this question occur in pairs that must be balanced, with each pair having an open delimiter and a close delimiter. There will be only one type of delimiter for each string. The following are examples of delimiters.
Example 1
Expressions in mathematics use open parentheses ”(“ and close parentheses ”)” as delimiters. For each open parenthesis, there must be a matching close parenthesis.
(x + y) * 5is a valid mathematical expression.(x + (y)is NOT a valid mathematical expression because there are more open delimiters than close delimiters.
Example 2
HTML uses <B> and </B> as delimiters. For each open delimiter <B>, there must be a matching close delimiter </B>.
<B> Make this text bold </B>is valid HTML.<B> Make this text bold </UB>is NOT valid HTML because there is one open delimiter and no matching close delimiter.
In this question, you will write two methods in the following Delimiters class.
Check the Code Runner
FRQ Question Part A
A string containing text and possibly delimiters has been split into tokens and stored in String[] tokens. Each token is either an open delimiter, a close delimiter, or a substring that is not a delimiter. You will write the method getDelimitersList, which returns an ArrayList containing all the open and close delimiters found in tokens in their original order.
The following examples show the contents of an ArrayList returned by getDelimitersList for different open and close delimiters and different tokens arrays.
Example 1:
- Variable Value
- openDel: (
- closeDel: )
- tokens: ( , x + y , ) , * 5
- ArrayList of delimiters: ( , )
Example 2:
- Variable Value
- openDel:
- closeDel: </q>
- tokens:
, yy ,
, zz , </q> - ArrayList of delimiters:
,
, </q>
Class information for this question:
- public class Delimiters
- private String openDel
- private String closeDel
- public Delimiters(String open, String close)
- public ArrayList
getDelimitersList(String[] tokens) - public boolean isBalanced(ArrayList
delimiters)
Complete method getDelimitersList below.
- /** Returns an ArrayList of delimiters from the array tokens, as described in part (a).
- */public ArrayList
getDelimitersList(String[] tokens)
// CODE_RUNNER: <challenge text>
Code Runner Challenge
Complete the getDelimitersList and isBalanced methods in the Delimiters class
View IPYNB Source
// CODE_RUNNER: Complete the getDelimitersList and isBalanced methods in the Delimiters class
public class Delimiters
{
/** The open and close delimiters. */
private String openDel;
private String closeDel;
/** Constructs a Delimiters object where open is the open delimiter and close is the
* close delimiter.
* Precondition: open and close are non-empty strings.
*/
public Delimiters(String open, String close)
{
openDel = open;
closeDel = close;
}
/** Returns an ArrayList of delimiters from the array tokens, as described in part (a). */
public ArrayList<String> getDelimitersList(String[] tokens)
{ /* to be implemented in part (a) */ }
/** Returns true if the delimiters are balanced and false otherwise, as described in part (b).
* Precondition: delimiters contains only valid open and close delimiters.
*/
public boolean isBalanced(ArrayList<String> delimiters)
{ /* to be implemented in part (b) */ }
// There may be instance variables, constructors, and methods that are not shown.
}
Main.main(null);
(b) Write the method isBalanced, which returns true when the delimiters are balanced and returns false otherwise. The delimiters are balanced when both of the following conditions are satisfied; otherwise, they are not balanced.
- When traversing the
ArrayListfrom the first element to the last element, there is no point at which there are more close delimiters than open delimiters at or before that point. - The total number of open delimiters is equal to the total number of close delimiters.
Consider a Delimiters object for which openDel is "<sup>" and closeDel is "</sup>". The examples below show different ArrayList objects that could be returned by calls to getDelimitersList and the value that would be returned by a call to isBalanced.
Example 1
The following example shows an ArrayList for which isBalanced returns true. As tokens are examined from first to last, the number of open delimiters is always greater than or equal to the number of close delimiters. After examining all tokens, there are an equal number of open and close delimiters.
| “” | “” | “” | “” | “” | “” | | :— | :— | :— | :— | :— | :— |
Example 2
The following example shows an ArrayList for which isBalanced returns false.
| “” | ”</sup>” | ”</sup>” | “” |
|---|---|---|---|
| ↑ |
When starting from the left, at this point, condition 1 is violated.
Example 3
The following example shows an ArrayList for which isBalanced returns false.
| ”</sup>” |
|---|
| ↑ |
At this point, condition 1 is violated.
Example 4
The following example shows an ArrayList for which isBalanced returns false because the second condition is violated. After examining all tokens, there are not an equal number of open and close delimiters.
| “” | “” | “” | | :— | :— | :— |
Class Information for this Question in Code Runner
public class Delimiters { /** The open and close delimiters as specified by the constructor. */ private String openDel; private String closeDel;
/** Constructs a Delimiters object where open is the open delimiter and
* close is the close delimiter.
* Precondition: open and close are non-empty strings.
*/
public Delimiters(String open, String close)
{ /* implementation not shown */ }
/** Returns an ArrayList of delimiters from the array tokens, as described in part (a). */
public ArrayList<String> getDelimitersList(String[] tokens)
{ /* implementation not shown */ }
/** Returns true if the delimiters are balanced and false otherwise, as described in part (b).
* Precondition: delimiters contains only valid open and close delimiters.
*/
public boolean isBalanced(ArrayList<String> delimiters)
{ /* to be implemented in part (b) */ } }
Code Runner Challenge
Complete the getDelimitersList and isBalanced methods in the Delimiters class
View IPYNB Source
// CODE_RUNNER: Complete the getDelimitersList and isBalanced methods in the Delimiters class
// CODE_RUNNER: Complete the getDelimitersList and isBalanced methods in the Delimiters class
public class Delimiters
{
/** The open and close delimiters. */
private String openDel;
private String closeDel;
/** Constructs a Delimiters object where open is the open delimiter and close is the
* close delimiter.
* Precondition: open and close are non-empty strings.
*/
public Delimiters(String open, String close)
{
openDel = open;
closeDel = close;
}
/** Returns an ArrayList of delimiters from the array tokens, as described in part (a). */
public ArrayList<String> getDelimitersList(String[] tokens)
{ /* to be implemented in part (a) */ }
/** Returns true if the delimiters are balanced and false otherwise, as described in part (b).
* Precondition: delimiters contains only valid open and close delimiters.
*/
public boolean isBalanced(ArrayList<String> delimiters)
{ /* to be implemented in part (b) */ }
// There may be instance variables, constructors, and methods that are not shown.
}
Main.main(null);
Scoring Guidelines Part A
AP® COMPUTER SCIENCE A
2019 SCORING GUIDELINES
Question 3: Scoring Notes
Part (a) getDelimitersList (4 points)
| Points | Rubric Criteria | Responses earn the point even if they… | Responses will not earn the point if they… |
|---|---|---|---|
| +1 | Creates ArrayList |
• omit |
• omit the keyword new |
| +1 | Accesses all elements in array tokens (no bounds errors) | • return incorrectly inside the loop | • treat tokens as a single string • access elements of tokens as if from an ArrayList (e.g., tokens.get(i)) |
| +1 | Compares strings in tokens with both instance variables (must be in the context of a loop) | • access elements of tokens as if from an ArrayList (e.g., tokens.get(i)) | • use == for string comparison • treat tokens as a single string |
| +1 | Adds delimiters into ArrayList in original order | • add a delimiter by accessing tokens incorrectly (e.g., tokens.get(i)) | • add a token that is not a delimiter • do not maintain the original delimiter order |
Part (b) isBalanced (5 points)
| Points | Rubric Criteria | Responses earn the point even if they… | Responses will not earn the point if they… |
|---|---|---|---|
| +1 | Initializes accumulator(s) | • initialize inside the loop | • initialize an accumulator variable but don’t update it |
| +1 | Accesses all elements in ArrayList delimiters (no bounds errors) | • return incorrectly inside the loop | • access elements of delimiters as if from an array (e.g., delimiters[i]) |
| +1 | Compares strings in delimiters with instance variables and updates accumulator(s) accordingly | • access elements of delimiters as if from an array (e.g., delimiters[i]) | • use == for string comparison • adjust an accumulator without a guarding condition |
| +1 | Identifies and returns appropriate boolean value to implement one rule | • check for more closing delimiters (inside a loop) and return false • return true if the number of open and close delimiters is the same, and false otherwise (after a loop) |
|
| +1 | Identifies and returns appropriate boolean values for all cases | • have correct logic with the exception of a loop bounds error, accessing elements as if from an array, or using == for string comparison | • initialize accumulator inside a loop • fail to check for more closing delimiters inside a loop |