Check for Balanced Parentheses

Problem Statement: Check Balanced Parentheses. Given string str containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, check if the input string is valid and return true if the string is balanced otherwise return false.

Note: String Str Valid होता है यदि –

• open brackets same type के brackets के द्वारा close होना चाहिए
• open brackets correct order में close होना चाहिए

Example 1:

Input: str = “( )[ { } ( ) ]”

Output: True

Explanation: As every open bracket has its corresponding 
close bracket. Match parentheses are in correct order 
hence they are balanced.

Example 2:

Input: str = “[ ( )”

Output: False

Explanation: As ‘[‘ does not have ‘]’ hence it is 
not valid and will return false.

Solution :

Intuition:

हमें previous और साथ ही recent opening brackets का भी track रखना होगा sequence का भी track रखना होगा क्योकि bracket को open करने के बाद bracket के opposite pair होने चाहिए | Corner cases को भी handle करे जैसे : [) (] जहा closing bracket पहले आता है जो एक Invalid Sequence है साथ ही साथ [(]) जहा most recent opening को इसकी opening pair नहीं मिलती है इसलिए यह भी Valid नहीं होगा 

Approach :

• जब हमें opening brackets प्राप्त होता है तो उसे हम Stack में push करेंगे |
• जब हमें closing brackets प्राप्त होता है तो हम check करेंगे Stack empty है या नहीं |
• यदि Stack empty होता है तो हम false return करेंगे और अगर यह non-empty है तो हम check करेंगे यही Stack का top-most element closing  bracket का opposite pair है या नहीं |
• यदि यह closing bracket का opposite pair नहीं होता है तो false return कर देंगे वरना आगे बढ़ेंगे|
• जब भी String से बहार निकलते है तो Stack empty होनी चाहिए यदि empty नहीं है तो इसे  invalid के रूप में return कर दे वरना यह एक valid  String है

C++ Code : 

#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
        stack<char>st; 
        for(auto it: s) {
            if(it=='(' || it=='{' || it == '[') st.push(it); 
            else {
                if(st.size() == 0) return false; 
                char ch = st.top(); 
                st.pop(); 
                if((it == ')' and ch == '(') or  (it == ']' and ch == '[') or (it == '}' and ch == '{')) continue;
                else return false;
            }
        }
        return st.empty(); 
    }
int main()
{
    string s="()[{}()]";
    if(isValid(s))
    cout<<"True"<<endl;
    else
    cout<<"False"<<endl;
}

Java Code : 

import java.util.*;
class DW {
public static boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();
        for (char it : s.toCharArray()) {
            if (it == '(' || it == '[' || it == '{')
                st.push(it);
            else {
                if(st.isEmpty()) return false;
                char ch = st.pop(); 
                if((it == ')' && ch == '(') ||  (it == ']' && ch == '[') || (it == '}' && ch == '{')) continue;
                else return false;
            }
        }
        return st.isEmpty();
    }

 public static void main (String[] args) {
		
		String s="()[{}()]";
		if(isValid(s)==true)
		System.out.println("True");
		else
		System.out.println("False");
	}
}

Output: True

Time Complexity: O(N)

Space Complexity: O(N)