Balanced Parentheses

Problem Statement: Balanced Parentheses

balanced parentheses : Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in exp.

Example:

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

Output: Balanced

Input: exp = "[(])"

Output: Not Balanced

Approach: Using Stack

This is very classical problem for using stacks. If you know that you need to use stack here, it becomes nice and easy.

What is balanced parentheses? It is when we meet some close bracket, it means that we need to find corresponding open bracked of the same type. We traverse our s and if we:

Steps to be followed:

1. See open bracket we put it to stack

2. See closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.

3. In the end, if and only if we have empty stack, we have valid string.

Internally we maintain a stack of tuples, where the first value represents the value added to the stack, and the second represents the minimum value in the stack at the point of insertion.

Because push and pop operations only occur at the top of the stack, we know that the things elements below the top element won't change. This means that we can know the minimum at any given point by just comparing the top most value with the one immediately before it.

#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;
}

class Solution:
    def balancedparenth(self, s):
        stack = []
        for char in s:
            if char == "(" or char == '{' or char == "[":
                stack.append(char)
            elif len(stack) <= 0:
                return False
            elif char == ")" and stack.pop() != "(":
                return False
            elif char == "}" and stack.pop() != "{":
                return False
            elif char == "]" and stack.pop() != "[":
                return False
        if len(stack) == 0:
            return True
        return False
ob1 = Solution()
print(ob1.balancedparenth("[()]{}{[()()]()}"))

Time Complexity: O(n)

Auxiliary Space: O(n), Since we are using stack for storing