Implementation lab in Stacks and Expression Processing

Mission

Decide whether (), [], and {} delimiters are balanced.

Learning outcome: Implement balanced-delimiter validation

Correctness contract

Invariant: Only the top element is removed, and size equals pushes minus successful pops.

Required technique: Use a stack of unmatched opening delimiters and compare every closing delimiter with the current top.

Complexity target: time O(n); space O(n).

Input and output

Input: One non-empty delimiter string containing only (), [], and {} characters. Whitespace may be spaces or line breaks.

Output: Print exactly true or false in lowercase. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The expression contains only delimiter characters.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use a stack of unmatched opening delimiters and compare every closing delimiter with the current top.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

([]{})

Sample output

true

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Each close must match the most recent unmatched opening delimiter, and no opening may remain. Input `([]{})` therefore produces `true`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: A closing delimiter with an empty stack is already a complete counterexample.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.