ITPEC FE Subject B April 2024 Question 13

Topic: Stack

From the answer group below, select the correct combination of answers to be inserted into A through C in the program. Here, the array index starts at 1.

The function are_brackets_balanced checks for balanced brackets. It parses the given array of characters and when an opening bracket (“(”, “[”, “{”) is encountered, this is pushed onto the stack. When a closing bracket (“)”, “]”, “}”) is encountered, an element is popped from the stack and tested if it corresponds to the opening bracket. If the closing bracket matches its corresponding opening bracket, the process continues. Otherwise, it fails and the function returns false. After all characters have been processed, it returns false if any characters remain on the stack, otherwise it returns true. For simplicity, only brackets are considered as arguments to the function. The table shows examples of arguments provided to are_brackets_balanced and the return values.

Table Examples of arguments provided to the function are_brackets_balanced and the return values

Function callReturn value
are_brackets_balanced({"(", "{", "}", ")", "[", "]"})true
are_brackets_balanced({"(", "{", "}", "[", "]"})false
are_brackets_balanced({"(", "{", ")", "}", "[", "]"})false

The function are_brackets_balanced uses class Stack. The figure describes class Stack.

ConstructorDescription
Stack()Initialize a stack.
MethodReturn valueDescription
push(character: arg)NonePushes arg onto the stack.
pop()characterReturns the value popped from the stack.
isEmpty()booleanReturns true if the stack is empty.

Figure Class Stack

[Program]
global: character [][]: brackets ← {
{"(", ")"},
{"{", "}"},
{"[", "]"}
}
○ boolean: are_brackets_balanced(character[]: expr)
Stack: stack ← Stack()
character: c, stacked_bracket
for (c in expr)
if (is_opening_bracket(c))
stack.push(c)
else
if (stack.isEmpty())
return false
endif
stacked_bracket ← stack.pop()
if (get_closing_bracket(stacked_bracket) A)
return false
endif
endif
endfor
return B
○ boolean: is_opening_bracket(character: c)
character []: chars
for (chars in brackets)
if (chars[1] = c)
return true
endif
endfor
return false
○ character: get_closing_bracket(character: c)
character []: chars
for (chars in brackets)
if (chars[1] = c)
return C
endif
endfor
return undefined

Answer group

OptionABC

Explanation

A: ≠ c, B: stack.isEmpty(), C: chars[2] — a closing bracket must be the partner of the last opening bracket, and no opening bracket may be left over at the end.

Each row of brackets is a pair {opening, closing}, so chars[1] is the opening and chars[2] the closing bracket. get_closing_bracket finds the row whose chars[1] is the popped opening bracket and must return its partner, chars[2] (blank C).

When a closing bracket c arrives, the partner of the popped opening bracket must equal c; the function fails when it does not, so blank A is ≠ c.

After the loop, every matched pair has been popped. Anything still on the stack is an opening bracket that was never closed, so the result is true only when the stack is empty: return stack.isEmpty() (blank B). The three table examples:

  • •(, {, }, ), [, ]: every closing bracket matches its popped partner and the stack ends empty, so true
  • •(, {, }, [, ]: all matches succeed but ( is left on the stack, so false
  • •(, {, ), …: ) pops {, whose partner } differs from ), so false

Answer (h)

Why not others:

  • •(a), (b), (c) and (d) — A as = c fails on a correct match: the first example returns false as soon as } closes {
  • •(a), (b), (e) and (f) — B as not stack.isEmpty() inverts the final test: a balanced expression returns false and one with an unclosed ( returns true
  • •(a), (c), (e) and (g) — C as chars[1] returns the opening bracket itself, which never equals a closing bracket, so with ≠ c any expression that closes a bracket fails

Key rule: With a stack, a closing bracket must match the most recently opened one, and the input is balanced only if the stack is empty once every character has been read.

Stack · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.