Java stack algorithm: validate nested delimiters

Java 8+. Use a JDK that supports this release.

State the input grammar

The validator accepts only six delimiter characters: parentheses, brackets, and braces. An unexpected character throws rather than silently disappearing. This is a delimiter validator, not a Java parser; a quote or comment needs a separate lexical rule.

For an opening token, push the required closing token. For a closing token, the stack must be nonempty and its top must match. This representation avoids a separate mapping lookup at every close.

If the final stack is nonempty, the input contains openings with no closing partner. An empty input is valid under this grammar. Those cases are part of the contract, not afterthoughts.

Preserve nesting, not just counts

The input ([)] has equal opening and closing counts but incorrect nesting. A pair of counters cannot detect that defect. The stack records the order of pending obligations.

Use ArrayDeque through the Deque contract. Its push and pop operate at the same end. Mixing push with removeLast changes the policy to a different order.

Working program

import java.util.ArrayDeque;
import java.util.Deque;

public class DelimiterValidator {
    static boolean valid(String delimiters) {
        Deque<Character> expected = new ArrayDeque<>();
        for (int index = 0; index < delimiters.length(); index++) {
            char token = delimiters.charAt(index);
            switch (token) {
                case '(': expected.push(')'); break;
                case '[': expected.push(']'); break;
                case '{': expected.push('}'); break;
                case ')': case ']': case '}':
                    if (expected.isEmpty() || expected.pop() != token) return false;
                    break;
                default: throw new IllegalArgumentException("Unsupported token");
            }
        }
        return expected.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(valid("{[()]}"));
        System.out.println(valid("([)]"));
        System.out.println(valid(""));
    }
}

Output

true
false
true

Cost and design choices

Each of n tokens is examined once. Deque endpoint operations give amortised O(n) total work. The maximum outstanding nesting depth d requires O(d) stored entries, with O(n) as the worst-case bound.

Reject excessively long input at the entry point when memory has a fixed budget. Replacing recursion with a heap-backed stack avoids call-stack exhaustion but does not remove the storage requirement.

Common Mistakes

• Do not validate nesting using counts alone.
• Do not pop an empty stack.
• Do not claim this handles delimiters inside arbitrary source-code strings.

Connect the contracts

Compare the boundary explained in Explicit traversal stack with the assumptions made by this program.