Guided Project: Valid Bracket Sequence

Step 1: Define the Validator Class

public class BracketValidator {
    private static final Map bracketPairs = Map.of(
        '(', ')',
        '{', '}',
        '[', ']'
    );
    
    private static final Set openBrackets = bracketPairs.keySet();
    private static final Set closeBrackets = new HashSet<>(bracketPairs.values());
    
    public boolean isValid(String input) {
        if (input == null || input.isEmpty()) {
            return true;
        }
        
        Stack stack = new Stack<>();
        
        for (char c : input.toCharArray()) {
            if (openBrackets.contains(c)) {
                stack.push(c);
            } else if (closeBrackets.contains(c)) {
                if (stack.isEmpty()) {
                    return false;
                }
                
                char lastOpen = stack.pop();
                if (bracketPairs.get(lastOpen) != c) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

Understanding the Algorithm

The bracket validation algorithm leverages a stack's Last-In-First-Out (LIFO) property to track and validate nested brackets.

Key Concepts:

• Bracket Pairing: Each opening bracket must match with its corresponding closing bracket type
• Proper Nesting: Brackets opened last must be closed first (LIFO order)
• Complete Matching: Every opening bracket must have a matching closing bracket

Visual Walkthrough:

// Input: "{[()]}"
// Tracing the algorithm step by step:

// Process '{': Push to stack
// Stack: ['{']

// Process '[': Push to stack
// Stack: ['{', '[']

// Process '(': Push to stack
// Stack: ['{', '[', '(']

// Process ')': Compare with top of stack
// Pop '(' from stack, matches with ')'
// Stack: ['{', '[']

// Process ']': Compare with top of stack
// Pop '[' from stack, matches with ']'
// Stack: ['{']

// Process '}': Compare with top of stack
// Pop '{' from stack, matches with '}'
// Stack: []

// Stack is empty after processing all characters
// Result: Valid bracket sequence

Edge Cases to Handle:

• Empty Input: An empty string is considered valid
• Unmatched Closing Bracket: Closing bracket without matching opening bracket (stack is empty)
• Mismatched Bracket Types: Opening and closing brackets of different types
• Unclosed Brackets: Opening brackets without matching closing brackets (stack not empty at end)

Step 2: Write Unit Tests

@Test
public class BracketValidatorTest {
    private BracketValidator validator;
    
    @BeforeEach
    void setUp() {
        validator = new BracketValidator();
    }
    
    @Test
    void testValidBrackets() {
        assertTrue(validator.isValid("()"));
        assertTrue(validator.isValid("()[]{}"));
        assertTrue(validator.isValid("{[]}"));
        assertTrue(validator.isValid(""));
    }
    
    @Test
    void testInvalidBrackets() {
        assertFalse(validator.isValid("(]"));
        assertFalse(validator.isValid("([)]"));
        assertFalse(validator.isValid("{[}"));
        assertFalse(validator.isValid("((()"));
    }
}

Implementation Variations

1. Using Java's Deque Interface

For better performance and flexibility, use Deque instead of the legacy Stack class:

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

public boolean isValidWithDeque(String input) {
    if (input == null || input.isEmpty()) {
        return true;
    }
    
    Deque<Character> stack = new ArrayDeque<>();
    
    for (char c : input.toCharArray()) {
        if (openBrackets.contains(c)) {
            stack.push(c);
        } else if (closeBrackets.contains(c)) {
            if (stack.isEmpty()) {
                return false;
            }
            
            char lastOpen = stack.pop();
            if (bracketPairs.get(lastOpen) != c) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}

2. Without Using Collections

For environments with limited resources, implement using a basic array-based stack:

public boolean isValidWithArray(String input) {
    if (input == null || input.isEmpty()) {
        return true;
    }
    
    char[] stack = new char[input.length()];
    int top = -1;
    
    for (char c : input.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack[++top] = c;
        } else if (c == ')' || c == '}' || c == ']') {
            if (top == -1) {
                return false;
            }
            
            char lastOpen = stack[top--];
            if ((lastOpen == '(' && c != ')') || 
                (lastOpen == '{' && c != '}') || 
                (lastOpen == '[' && c != ']')) {
                return false;
            }
        }
    }
    
    return top == -1;
}

3. With Detailed Error Reporting

For applications needing better diagnostics:

public ValidationResult validateWithDetails(String input) {
    if (input == null || input.isEmpty()) {
        return new ValidationResult(true, "Empty input is valid", -1);
    }
    
    Deque<BracketPosition> stack = new ArrayDeque<>();
    
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        
        if (openBrackets.contains(c)) {
            stack.push(new BracketPosition(c, i));
        } else if (closeBrackets.contains(c)) {
            if (stack.isEmpty()) {
                return new ValidationResult(
                    false, 
                    "Closing bracket '" + c + "' at position " + i + " without matching opening bracket", 
                    i
                );
            }
            
            BracketPosition lastOpen = stack.pop();
            if (bracketPairs.get(lastOpen.bracket) != c) {
                return new ValidationResult(
                    false,
                    "Mismatched brackets: '" + lastOpen.bracket + "' at position " + 
                    lastOpen.position + " and '" + c + "' at position " + i,
                    i
                );
            }
        }
    }
    
    if (!stack.isEmpty()) {
        BracketPosition unmatched = stack.peek();
        return new ValidationResult(
            false,
            "Unclosed bracket '" + unmatched.bracket + "' at position " + unmatched.position,
            unmatched.position
        );
    }
    
    return new ValidationResult(true, "Valid bracket sequence", -1);
}

static class BracketPosition {
    final char bracket;
    final int position;
    
    BracketPosition(char bracket, int position) {
        this.bracket = bracket;
        this.position = position;
    }
}

Time and Space Complexity

• Time Complexity: O(n) - We process each character exactly once
• Space Complexity: O(n) - In the worst case, the stack could hold all characters (e.g., all opening brackets)

Optimization Tips:

• Early Validation: If the string length is odd, it cannot be balanced
• Fixed Maps: Use fixed-size arrays instead of Map for known bracket pairs
• Character Checks: Use switch statements for character comparisons instead of collections lookups

// Optimized implementation with early validation
public boolean isValidOptimized(String input) {
    if (input == null) {
        return true;
    }
    
    int length = input.length();
    
    // Quick validation - if odd length, cannot be balanced
    if (length % 2 != 0) {
        return false;
    }
    
    if (length == 0) {
        return true;
    }
    
    Deque<Character> stack = new ArrayDeque<>(length / 2);
    
    for (int i = 0; i < length; i++) {
        char c = input.charAt(i);
        
        switch (c) {
            case '(':
            case '{':
            case '[':
                stack.push(c);
                break;
            case ')':
                if (stack.isEmpty() || stack.pop() != '(') return false;
                break;
            case '}':
                if (stack.isEmpty() || stack.pop() != '{') return false;
                break;
            case ']':
                if (stack.isEmpty() || stack.pop() != '[') return false;
                break;
            default:
                // Ignore non-bracket characters
                break;
        }
    }
    
    return stack.isEmpty();
}

1. Enhanced Bracket Validator

Extend the bracket validator to handle more complex scenarios:

• Support angle brackets <>
• Handle escaped brackets in strings
• Track and report error positions
• Support nested comments

Example Implementation:

public class EnhancedBracketValidator {
    private final Map bracketPairs;
    private boolean inString;
    private char stringDelimiter;
    private int position;
    
    public ValidationResult validate(String input) {
        // Your implementation here
    }
    
    public static class ValidationResult {
        private final boolean valid;
        private final String message;
        private final int errorPosition;
        
        // Constructor and getters
    }
}

Implementation Hints:

1. Add angle brackets to your bracket pairs map: bracketPairs.put('<', '>')
2. Use a boolean flag to track when you're inside a string: inString
3. Check for escape characters \\ to skip the next character
4. Use a separate state for tracking comments (both inline and block comments)

2. Code Block Analyzer

Create a tool that analyzes code blocks and their nesting levels:

• Identify different types of code blocks
• Calculate nesting depth
• Detect unbalanced blocks
• Report statistics on code structure

Implementation Approach:

public class CodeBlockAnalyzer {
    private final Stack blockStack = new Stack<>();
    private int maxDepth = 0;
    private int currentDepth = 0;
    
    public CodeAnalysis analyze(String code) {
        // Reset state
        blockStack.clear();
        maxDepth = 0;
        currentDepth = 0;
        
        // Track blocks, depths, and statistics
        for (int i = 0; i < code.length(); i++) {
            char c = code.charAt(i);
            
            if (isOpeningBlock(c)) {
                blockStack.push(new BlockInfo(c, i, currentDepth));
                currentDepth++;
                maxDepth = Math.max(maxDepth, currentDepth);
            }
            else if (isClosingBlock(c)) {
                if (blockStack.isEmpty()) {
                    return new CodeAnalysis(false, "Unmatched closing block at position " + i, 
                                          currentDepth, maxDepth, Collections.emptyList());
                }
                
                BlockInfo opening = blockStack.pop();
                if (!isMatchingPair(opening.blockType, c)) {
                    return new CodeAnalysis(false, "Mismatched block types at positions " + 
                                          opening.position + " and " + i, 
                                          currentDepth, maxDepth, Collections.emptyList());
                }
                
                currentDepth--;
            }
        }
        
        if (!blockStack.isEmpty()) {
            BlockInfo unmatched = blockStack.peek();
            return new CodeAnalysis(false, "Unclosed block at position " + unmatched.position, 
                                 currentDepth, maxDepth, Collections.emptyList());
        }
        
        return new CodeAnalysis(true, "Valid code structure", 
                             0, maxDepth, generateBlockStatistics());
    }
    
    // Helper methods and inner classes
}

3. Expression Evaluator

Build a calculator that evaluates mathematical expressions using stacks:

• Support basic operations (+, -, *, /)
• Handle parentheses for precedence
• Support functions (sin, cos, sqrt)
• Provide detailed error reporting

Implementation Approach:

public class ExpressionEvaluator {
    // Two stacks: one for operators, one for operands
    private final Stack operators = new Stack<>();
    private final Stack values = new Stack<>();
    
    // Maps for operator precedence and functions
    private final Map precedence = Map.of(
        '+', 1, '-', 1, '*', 2, '/', 2, '^', 3
    );
    
    public double evaluate(String expression) {
        operators.clear();
        values.clear();
        
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            
            if (Character.isDigit(c) || c == '.') {
                // Parse number
                StringBuilder numBuilder = new StringBuilder();
                while (i < expression.length() && 
                       (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
                    numBuilder.append(expression.charAt(i++));
                }
                i--; // Back up one character
                values.push(Double.parseDouble(numBuilder.toString()));
            }
            else if (c == '(') {
                operators.push(c);
            }
            else if (c == ')') {
                while (!operators.isEmpty() && operators.peek() != '(') {
                    values.push(applyOperator(operators.pop(), values.pop(), values.pop()));
                }
                operators.pop(); // Remove the '('
            }
            else if (isOperator(c)) {
                while (!operators.isEmpty() && hasPrecedence(c, operators.peek())) {
                    values.push(applyOperator(operators.pop(), values.pop(), values.pop()));
                }
                operators.push(c);
            }
        }
        
        while (!operators.isEmpty()) {
            values.push(applyOperator(operators.pop(), values.pop(), values.pop()));
        }
        
        return values.pop();
    }
    
    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
    }
    
    private boolean hasPrecedence(char op1, char op2) {
        if (op2 == '(' || op2 == ')') {
            return false;
        }
        return precedence.getOrDefault(op1, 0) <= precedence.getOrDefault(op2, 0);
    }
    
    private double applyOperator(char operator, double b, double a) {
        switch (operator) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
            case '^': return Math.pow(a, b);
            default: throw new IllegalArgumentException("Unknown operator: " + operator);
        }
    }
}

Test Cases:

• "3 + 4" should output 7.0
• "3 * (4 + 2)" should output 18.0
• "10 / 2 - 3" should output 2.0
• "2 ^ 3 + 1" should output 9.0