Valid Parentheses solution

In this tutorial, we will help you to understand how to solve Valid Parentheses problem of leet code 20 problem.

This problem is also known as check for balanced brackets in an expression using stack.

Suppose, you are given a string str having just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and / or ‘]‘. You will have to verify whether the input string is valid or not.

An input string will be valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "[{()}]" 

Output: true

Example 2:

Input: s = "()[]{}" 

Output: true

Example 3:

Input: s = "(]" 

Output: false

Example 4:

Input: s = "[{(]})" 

Output: false

Algorithm to solve the problem:

Create the stack
- Iterate over the string
- Check If character of string belongs to either [ or { or ( .
- If it belongs to then push this character to stack
- If it doesn’t belong to then :
  - Get the top value of stack
  - If character of string is ( then popped value of stack must be ). If they are not matching then return the false value.
  - If character of string is [ then popped value of stack must be ]. If they are not matching then return the false value.
  - If character of string is { then popped value of stack must be }. If they are not matching then return the false value.
  - Pop the element from the stack.
If all the condition are met then return true value.

Code with valid parentheses in string:

#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
    stack<char> st;
        
    for(int i = 0; i < s.length(); i++) {

        // Check if character belongs to "( or { or ["
        if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
            st.push(s[i]);
        } else if(s[i] == ')' || s[i] == '}' || s[i] == ']') {
            // Check whether stack is empty or not
            if(st.empty()) 
                return false;
                
            // Get the top value of stack
            char ch = st.top();
            
            // Match the popped value with iterated character of string
            if(s[i] == ')' && ch != '(') {
                return false;
            } else if(s[i] == '}' && ch != '{') {
                return false;
            } else if(s[i] == ']' && ch != '[') {
                return false;
            }
            // Pop the value from stack
            st.pop();
        }
    }
    // After iterating over the string, It will return true if stack is empty else false.
    return st.empty(); 
}
    
int main()
{
    string s = "[{()}]";
    
    cout<<isValid(s);

    return 0;
}

Output:

Output: true

Code with invalid parentheses in string:

#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
    stack<char> st;
        
    for(int i = 0; i < s.length(); i++) {

        // Check if character belongs to "( or { or ["
        if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
            st.push(s[i]);
        } else if(s[i] == ')' || s[i] == '}' || s[i] == ']') {
            // Check whether stack is empty or not
            if(st.empty()) 
                return false;
                
            // Get the top value of stack
            char ch = st.top();
            
            // Match the popped value with iterated character of string
            if(s[i] == ')' && ch != '(') {
                return false;
            } else if(s[i] == '}' && ch != '{') {
                return false;
            } else if(s[i] == ']' && ch != '[') {
                return false;
            }
            // Pop the value from stack
            st.pop();
        }
    }
    // After iterating over the string, It will return true if stack is empty else false.
    return st.empty(); 
}
    
int main()
{
    string s = "[{()]})";
    
    cout<<isValid(s);

    return 0;
}

Output:

Output: false

*** there can be many ways to solve this problem but the best way of valid parentheses solution is to solve by using stack.

To learn more about C++ pls refer given below link:

https://www.techieindoor.com/category/leetcode/

References:

https://www.cplusplus.com/reference/vector/vector/?kw=vector

Leetcode 20: Valid Parentheses solution