Valid Parentheses - CPP Solution

1. Introduction

This post addresses a common problem in the domain of string processing and stack usage in C++: the validation of parentheses in a given string. The problem involves checking whether the open and close brackets in a string are correctly paired and ordered.

Problem

Given a string 's' containing just the characters '(', ')', '{', '}', '[' and ']', we need to determine if the input string is valid. A string is valid if:

- Open brackets are closed by the same type of brackets.

- Open brackets are closed in the correct order.

- Every close bracket has a corresponding open bracket of the same type.

2. Solution Steps

1. Use a stack to keep track of opening brackets.

2. Iterate through each character in the string.

3. If the character is an opening bracket, push it onto the stack.

4. If it's a closing bracket, check if it matches the top element of the stack.

5. If it matches, pop the top element from the stack. If not, the string is invalid.

6. After processing all characters, if the stack is empty, the string is valid. Otherwise, it's invalid.

3. Code Program

#include <iostream>
#include <stack>
using namespace std;

// Function to determine if the input string of parentheses is valid
bool isValid(string s) {
    stack<char> bracketStack;

    // Mapping closing brackets to their corresponding opening brackets
    unordered_map<char, char> bracketPairs = {{')', '('}, {']', '['}, {'}', '{'}};

    for (char c : s) {
        if (bracketPairs.find(c) != bracketPairs.end()) {
            // Check if the stack is empty or the top doesn't match
            if (bracketStack.empty() || bracketStack.top() != bracketPairs[c]) {
                return false;
            }
            bracketStack.pop(); // Pop the matching opening bracket
        } else {
            bracketStack.push(c); // Push opening bracket onto the stack
        }
    }
    return bracketStack.empty(); // Check if the stack is empty
}

int main() {
    string input = "{[]}";
    cout << "Is valid: " << isValid(input) << endl;
    return 0;
}

Output:

Is valid: 1

Explanation:

1. The input string "{[]}" is processed character by character.

2. Each opening bracket is pushed onto the stack.

3. For each closing bracket, the function checks if it matches the top of the stack.

4. In this case, all brackets are matched correctly and in the right order.

5. The stack is empty at the end, indicating that the parentheses are valid.

6. Thus, the function returns true (represented as 1), confirming the input string's validity.