Analysis and Implementation of Parenthesis Matching Using Stack Algorithm

Algorithm Principle Analysis

Parenthesis matching is a classic problem in computer science, primarily used to check whether brackets in an expression are correctly paired. The stack data structure, due to its last-in-first-out nature, is naturally suited for solving such problems. When a left bracket is encountered, it is pushed onto the stack; when a right bracket is encountered, the top element of the stack is checked for a match. If matched, it is popped; otherwise, a mismatch is returned. Ultimately, the stack should be empty, indicating that all brackets are correctly paired.

Original Code Issue Diagnosis

The original code exhibits logical confusion in handling curly braces. There are duplicate if(c == '{') checks, and the first check directly returns false, which clearly violates the basic logic of parenthesis matching. Additionally, the code structure lacks clarity, resulting in poor readability and maintainability.

Corrected Implementation Solution

Based on the best answer's correction, we have reimplemented the parenthesis matching algorithm:

public static boolean isParenthesisMatch(String str) {
    Stack<Character> stack = new Stack<Character>();
    
    char c;
    for(int i = 0; i < str.length(); i++) {
        c = str.charAt(i);
        
        if(c == '(' || c == '{') {
            stack.push(c);
        } else if(c == ')') {
            if(stack.isEmpty()) return false;
            if(stack.peek() == '(') {
                stack.pop();
            } else {
                return false;
            }
        } else if(c == '}') {
            if(stack.isEmpty()) return false;
            if(stack.peek() == '{') {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Detailed Algorithm Execution Flow

Using the input string "({})" as an example, the algorithm execution process is analyzed in detail:

1. Encounter '(', push onto stack, stack content: ['(']
2. Encounter '{', push onto stack, stack content: ['(', '{']
3. Encounter '}', check stack top is '{', match successful, pop stack top, stack content: ['(']
4. Encounter ')', check stack top is '(', match successful, pop stack top, stack content: []
5. Final stack is empty, return true

Error Case Analysis

For mismatched input, such as "({}":

1. Encounter '(', push onto stack
2. Encounter '{', push onto stack
3. Encounter '}', pop stack top
4. Processing ends, stack still has unmatched '(', return false

Performance Analysis and Optimization

The algorithm has a time complexity of O(n), where n is the length of the input string, as each character is processed only once. The space complexity is O(n) in the worst case, when all characters are left brackets and the stack size reaches its maximum.

Extended Discussion

Referencing implementations from other answers, the algorithm can be further extended to support more types of brackets, such as square brackets []. Using a mapping table to manage the correspondence between opening and closing brackets can enhance the code's scalability and maintainability.