# **Balanced Parentheses and Brackets**

A string w of parentheses ( and ) and brackets [ and ] is balanced if it satisfies one of the following conditions:

* w is the empty string

* w = (x) for some balanced string x

* w = [x] for some balanced string x

* w = xy (concatenation) for some balanced strings x and y

For example, the string
w=([()][]())[()()]() is balanced, because w=xy, where x=([()][]()) and y=[()()]()

# **Solution 1**
**Problem**
Describe and analyze an algorithm to determine whether a given string of parentheses and brackets is balanced.

**Algorithm**
The following algorithm uses the function ```isBalanced(x)``` to correctly determine if a given string of parentheses and brackets is balanced. The function uses a stack to keep track of matching parentheses or brackets. If an open bracket or parenthesis appears, it is pushed onto the stack. If a closing bracket or parenthesis appears, it is compared to the top of the stack to check if it matches.

fun isBalanced(x){
    
    var S = [];
    
    for(int i = 0; i < len(x); i++){
        if(x[i] == '(' or x[i] == '['){
            push(S, x[i]);
        }
        else if(x[i] == ')'){
            if(len(S) == 0 or S[len(S) - 1] != '(')
                return false;
            pop(S);
        }
        else if(x[i] == ']'){
            if(len(S) == 0 or S[len(S) - 1] != '[')
                return false;
            pop(S);
        }
    }
    
    if(len(S) == 0){
        return true;
    }
    
    return false;
}

**Correctness Proof**
Goal: Prove that isBalanced(x) correctly returns true if x is balanced.

Base Case:
x is empty: the loop does not execute and the stack is empty --> returns true

Inductive Hypothesis: Assume the algorithm correctly checks if a string is balanced for all strings shorter than n

1. if '(' or '[' appears, the open bracket is recorded
2. if ')' or ']' appears, the closing bracket is matched to the most recently stored open bracket
3. the stack will be empty at the end only if each opening bracket has a matching closing bracket

By induction, the algorithm correctly determines if a string is balanced

**Time Complexity**
Each character in the string is processed once

T(n) = O(n)

# **Solution 2**
**Problem**
Describe and analyze an algorithm to compute the length of a longest balanced subsequence of a given string of parentheses and brackets.

**Algorithm**
The following algorithm uses the function ```longestBalancedSubseq(x)``` to correctly find the length of the longest balanced subsequence of a given string of parentheses and brackets. The function uses a stack to keep track of the base index of the current subsequence. When a matching closing bracket is found, the stack is popped and the length is updated as the new longest length. If there is a bracket that does not match, its index is set as the new base index for the next subsequence.

fun longestBalancedSubseq(x) {

    var s = [];
    push(s, -1); 
    var max_len = 0;

    for (var i = 0; i < len(x); i++) {
        var ch = x[i];

        if (ch == '(' or ch == '[') {
            push(s, i);
        } 
        else { // closing bracket
            if (len(s) > 0) {
                var top_idx = top(s);

                if ((ch == ')' and x[top_idx] == '(') or 
                    (ch == ']' and x[top_idx] == '[')) {

                    pop(s);
                    if (len(s) > 0)
                        max_len = max(max_len, i - top(s));
                    else
                        push(s, i);
                } 
                else {
                    push(s, i);
                }
            } 
            else {
                push(s, i);
            }
        }
    }

    return max_len;
}

**Correctness Proof**
Goal: Prove that longestBlancedSubseq(x) correctly finds and returns the length of the longest balanced subsequence

Base Case:
* x is empty: no iterations, s = [-1], max_len = 0 --> correct

Inductive Hypothesis:
Assume the algorithm correctly finds and computes the length of the longest balanced subsequence for all strings shorter than n.

1. if there is an opening bracket --> push index into stack
2. if there is a matching closing bracket --> pop opening bracket index and compute length of current balanced segment --> ```i - top(s)```
3. if a bracket that doesn't match appears --> reset base index --> ```push(s, i)```

The algorithm correctly finds and computes the longest balanced subsequence length.

**Time Complexity**
Each character is pushed and popped from the stack at most once

T(n) = O(n)