Write it
Balanced brackets
A functionPython or Java18 tests, 12 of them hidden
On a phone? Put the lines in order instead
A school's online code editor warns students when the brackets in a line of code do not match up. Write a function that returns whether the brackets in a piece of text are balanced. Use a list (an ArrayList in Java) as a stack.
- The brackets are
(with),[with], and{with}. Every other character is ignored. - The brackets are balanced when every closing bracket closes the most recent bracket still open, and that bracket is of the same kind. So
([])is balanced, and([)]is not. - A closing bracket with no bracket open makes the text unbalanced.
- A bracket still open at the end makes the text unbalanced.
- Text with no brackets at all, including empty text, is balanced.
- The text has at most 100 characters, all of them printable ASCII. Write the stack yourself: the shortcuts listed with this question are not allowed.
Only the True or False (in Java, true or false) your function returns is checked.
def balanced(text: str) -> bool
You cannot use these in this question:
- .replace()
- .count()
- import re
An exam question like this one tests whether you can use a stack. Removing pairs of brackets with replace, or matching them with a regular expression, skips the stack, so those shortcuts are not allowed.
Examples
Your function is tested on 18 cases: the 6 examples below, and 12 hidden ones that check the rules above.
- balanced("x = (a[0] + b)") should return True: a [ ] inside a ( ), and other characters ignored (rules 1 and 2)
- balanced("([)]") should return False: the ) closes the [ that is still open, so the kinds do not match (rule 2)
- balanced("f(x))") should return False: the last ) has no bracket open to close (rule 3)
- balanced("{[()") should return False: the { and [ are still open at the end (rule 4)
- balanced("(]") should return False: a ( closed by a ] (rule 2)
- balanced("{)") should return False: a { closed by a ) (rule 2)
public static boolean balanced(String text)
Running Java here comes later. You can put this answer's lines in order instead. You can still write your Java answer (it stays while this page is open) and compare it with our worked solution. Or try this exercise in Python.Checking whether Java answers can run here.
You cannot use these in this question:
- .replace()
- .replaceAll()
- .replaceFirst()
- .matches()
- import java.util.regex
An exam question like this one tests whether you can use a stack. Removing pairs of brackets with replace, or matching them with a regular expression, skips the stack, so those shortcuts are not allowed.
Examples
Your function is tested on 18 cases: the 6 examples below, and 12 hidden ones that check the rules above.
- balanced("x = (a[0] + b)") should return true: a [ ] inside a ( ), and other characters ignored (rules 1 and 2)
- balanced("([)]") should return false: the ) closes the [ that is still open, so the kinds do not match (rule 2)
- balanced("f(x))") should return false: the last ) has no bracket open to close (rule 3)
- balanced("{[()") should return false: the { and [ are still open at the end (rule 4)
- balanced("(]") should return false: a ( closed by a ] (rule 2)
- balanced("{)") should return false: a { closed by a ) (rule 2)