Valid Parentheses

class Validator {
private:
    unordered_map<char, char> bracketMap;
    
public:
    Validator() {
        bracketMap[')'] = '(';
        bracketMap['}'] = '{';
        bracketMap[']'] = '[';
    }
    bool checkValidity(string str) {
        stack<char> bracketStack;
        for (char ch : str) {
            if (bracketMap.find(ch) != bracketMap.end()) {  // Check if it's a closing bracket
                char topElem = bracketStack.empty() ? '#' : bracketStack.top();
                bracketStack.pop();
                if (topElem != bracketMap[ch]) {
                    return false;
                }
            } else {  // It's an opening bracket
                bracketStack.push(ch);
            }
        }
        return bracketStack.empty();
    }
};

The code defines a class Validator in C++ used to verify the correctness of a string containing different types of parentheses. The code efficiently checks whether the given input string has valid matching braces using a stack and a hash map.

• The Validator class has a private member bracketMap, which initializes a mapping between closing and corresponding opening brackets in the constructor.

• checkValidity is a public method that determines whether the input string str has balanced brackets using a stack to track the unmatched opening brackets.

  • The method iterates over each character in the string.
  • If the current character is a closing bracket, it checks against the top of the stack, which holds the last unmatched opening bracket.
  • If the stack is empty or the top element of the stack does not match the mapped opening bracket for the current closing bracket, the method returns false, indicating imbalance.
  • If a match is found, the method pops the top element from the stack.
  • If the character is an opening bracket, it pushes it onto the stack.

• Finally, after processing all characters, the method checks if the stack is empty. An empty stack indicates that all opening brackets found matching closing brackets, returning true. If the stack is not empty, it means there are unmatched opening brackets, so it returns false.

This setup ensures efficient validity checking of strings containing brackets by using the properties of stack data structure, optimizing for a quick mismatch detection and easy tracking of the last unmatched opening bracket.

class Validator {
    private HashMap<Character, Character> bracketMapping;
    
    public Validator() {
        this.bracketMapping = new HashMap<>();
        this.bracketMapping.put(')', '(');
        this.bracketMapping.put('}', '{');
        this.bracketMapping.put(']', '[');
    }
    
    public boolean isBalanced(String expression) {
        Stack<Character> tempStack = new Stack<>();
    
        for (int idx = 0; idx < expression.length(); idx++) {
            char currentChar = expression.charAt(idx);
    
            if (bracketMapping.containsKey(currentChar)) {
                char topChar = tempStack.empty() ? '#' : tempStack.pop();
    
                if (topChar != bracketMapping.get(currentChar)) {
                    return false;
                }
            } else {
                tempStack.push(currentChar);
            }
        }
    
        return tempStack.isEmpty();
    }
}

This Java solution involves checking if a given string of parentheses is balanced or not. It defines a class named Validator with a HashMap, bracketMapping, to store closing and their corresponding opening brackets. This is initialized in the constructor of the class.

The primary method isBalanced(String expression) uses a Stack<Character> to help determine if the parentheses are balanced:

• Iterates over each character in the input string.
• If the current character is a closing bracket (as checked by bracketMapping.containsKey(currentChar)), it either pops the top character from the stack if the stack is not empty or sets a placeholder character if it is.
• Compares the popped character (or placeholder if the stack was empty) with the expected opening bracket from the hash map. If they do not match, it returns false, indicating the string is not balanced.
• If the character is an opening bracket, it is simply pushed onto the stack for later comparison.
• At the end of the iteration, checks if the stack is empty. An empty stack implies all opening brackets had matching closing brackets in the correct order, and hence it returns true.
• If there are still elements in the stack (implying unmatched opening brackets), then isBalanced returns false.

This method effectively validates whether an expression with different types of brackets is correctly balanced, using a combination of stack operations and hash map lookups to check matching pairs efficiently.

typedef struct {
    char key[3];
    char val;
    UT_hash_handle hh;
} char_hash;
char_hash* hash_table = NULL;
    
void create_hash_table() {
    char open_chars[3] = {'}', ']', ')'};
    char close_chars[3] = {'{', '[', '('};
    for (int i = 0; i < 3; i++) {
        char_hash* entry = malloc(sizeof *entry);
        entry->key[0] = open_chars[i];
        entry->key[1] = '\0';
        entry->val = close_chars[i];
        HASH_ADD_STR(hash_table, key, entry);
    }
}
    
bool check_validity(char* sequence) {
    create_hash_table();
    int top = -1;
    char* parse_stack = (char*)malloc(strlen(sequence) + 1);
    for (int i = 0; sequence[i]; i++) {
        char_hash* found = NULL;
        char key_pair[3] = {sequence[i], '\0'};
        HASH_FIND_STR(hash_table, key_pair, found);
        if (found == NULL) {
            parse_stack[++top] = sequence[i];
        } else {
            if (top < 0 || parse_stack[top--] != found->val) {
                return false;
            }
        }
    }
    bool valid = top == -1;
    HASH_CLEAR(hh, hash_table);
    free(parse_stack);
    return valid;
}

The given C code is designed to check if a string consisting of bracket characters ('{', '}', '[', ']', '(', ')') is valid. Here's a breakdown of how it achieves this:

• Data Structures: Implements a custom hash table using the UTHASH library to map closing brackets to their corresponding opening brackets. This hash table is populated in the create_hash_table function.

• Hash Table Initialization: Three pairs are added to the hash table:

  • '}' to '{'
  • ']' to '['
  • ')' to '('

  This setup aids in quickly finding the matching opening bracket for a given closing bracket.

• Primary Function - check_validity:

  1. Initializes the hash table with bracket mappings.
  2. Allocates a character array parse_stack to simulate a stack data structure for opening brackets.
  3. Iterates through each character in the input sequence:
     • If the character is a closing bracket, it searches for the character in the hash table:
       • If found, checks the stack to see if the last character is the matching opening bracket.
       • If it matches, pop the opening bracket from the stack; if not, return false.
     • If the character is an opening bracket, it pushes it onto the stack.
  4. After processing all characters, if the stack is empty (top == -1), the string is valid, otherwise, it is invalid.

• Memory Management: The code appropriately frees allocated memory for the hash table and the stack after validation is complete, ensuring no memory leaks.

• Return Value: The check_validity function returns true if the sequence is valid, and false otherwise, effectively determining the balance of the brackets in the given string.

This implementation efficiently checks string validity concerning bracket balancing using a hash table and stack, typical in compiler syntax checks and similar algorithms.

var checkValidity = function (inputStr) {
    const bracketsMap = {
        ")": "(",
        "}": "{",
        "]": "[",
    };
    const tempStack = [];
    for (let char of inputStr) {
        if (bracketsMap[char]) {
            const lastChar = tempStack.length ? tempStack.pop() : "#";
            if (lastChar !== bracketsMap[char]) {
                return false;
            }
        } else {
            tempStack.push(char);
        }
    }
    return tempStack.length === 0;
};

The "Valid Parentheses" problem in JavaScript involves checking if the input string of parentheses is valid, where valid means every opening bracket has a corresponding and correctly placed closing bracket. The provided JavaScript function, checkValidity, uses a stack-based approach to solve the problem. Here's a breakdown of how it works:

• A bracketsMap object is created to easily find matching pairs of parentheses.
• tempStack is used to keep track of unmatched opening brackets.
• The function iterates through each character in the input string:
  • If the current character is a closing bracket, it checks the last item in tempStack:
    • If it does not match the corresponding opening bracket from bracketsMap, the function immediately returns false.
  • If the character is an opening bracket, it's pushed onto tempStack.
• After all characters are processed, if tempStack is empty, it means all brackets are properly matched and closed, and the function returns true. If there are still items left in tempStack, the input string is not valid, and the function returns false.

This approach ensures that all the brackets are not only matched but also correctly nested within each other, providing a robust solution to the Valid Parentheses problem.

class Solution(object):
    def checkParenthesis(self, expression: str) -> bool:
        # Use stack to keep open parentheses
        parenthesis_stack = []
            
        # Mapping pairs of parentheses
        matching_bracket = {")": "(", "}": "{", "]": "["}
            
        # Evaluate each character in the expression
        for char in expression:
            # Check if it's a closing bracket
            if char in matching_bracket:
                # Pop from stack or use dummy if stack is empty
                last_open = parenthesis_stack.pop() if parenthesis_stack else "#"
                    
                # If the brackets do not match, return False
                if matching_bracket[char] != last_open:
                    return False
            else:
                # It's an opening bracket, push to stack
                parenthesis_stack.append(char)
    
        # Confirm stack is empty for a valid expression
        return not parenthesis_stack

The provided Python code defines a method for checking the validity of strings containing parentheses. This method, checkParenthesis, ensures that each type of opening parenthesis is properly closed in the correct sequence. The implementation uses a stack data structure to manage the open parentheses encountered as the string is processed.

Follow the key aspects of this solution:

• A dictionary named matching_bracket is initialized to pair each type of closing bracket with its corresponding opening bracket.
• An empty list, parenthesis_stack, is used to maintain a stack of opening brackets.
• The method iterates over each character in the input string, expression.
  • If the character is a closing bracket, it checks if there is an opening bracket at the top of the stack (if the stack isn't empty) that matches. If they don't match or the stack is empty when a closing bracket is encountered, it returns False.
  • If the character is an opening bracket, it is pushed onto the stack.
• The validity of the entire expression hinges on the stack being empty at the end of the iteration, indicating that all opening brackets have been properly closed.

Key benefits of this approach include direct mapping of brackets for efficient match checking and use of a stack to dynamically track open brackets and ensure matches occur in the correct order. This technique effectively handles various combinations of nested and sequential brackets.