Stack Practice Question | Parenthesis Checker | Learn DSA Concepts | GeeksforGeeks

Key Takeaways

hello everyone my name is Karan mashu welcome to this video so in the last video we saw about the basics of stack and we also saw some of the applications one of them was checking for the balanced parenthesis so in this uh video we'll be looking at its uh exit implementation and how it works so in this video we will be looking at the solution of parenthesis Checker first of all let us start by understanding the question what does question say given an expression string X so X we are given which is an expression string okay examine whether the pairs and the orders of opening brackets of and closing brackets of three different types are in correct expression for example the function should return return true for this example and should return return false for this example as you can see here uh the square bracket is opening then circular bracket is opening then square bracket is closing which is not a valid option okay the driver code prints balanced IF function returns true otherwise it prints not balanced okay so we just need to return true or false if the string is balanced or not and the driver code will print balanced or not depending upon the condition so if I look at this example see this is a completely Bal balanced parenthesis so we will return return true okay and if we look at this example this is also balanced if we look at this example here there is no closing bracket so this will print false this is a function problem you only need to complete the function e pair that takes a string as a parameter and returns a Boolean value true if brackets are balanced and returns otherwise returns false the printing is done automatically by the driver code the expected time complexity is bigger of modulus X that is the length of string X and the expected auxillary space is also length of the string X that is the expression and the constraints are given here so now if we think about solving this problem so basically see we will be given an expression X in the input and we need to tell whether it is balanced or not now understand one thing in the expression X there are four six characters one is this curly opening bracket curly closing bracket Square opening bracket Square closing bracket circular opening bracket and circular closing bracket okay so what do we mean by a balanced parenthesis or a balanced expression it means if we can represent a mathematical expression successfully in it so uh if I have a balanced parenthesis let's say like this can I represent a mathematical expression properly in this yes absolutely how I can say 2 into 3 plus 4 into 5 4 + 5 and let's say this okay or let's say uh I will keep keep here A minus sign so this is completely balanced okay but if I say you this then here you cannot place any uh proper uh mathematical expression because let's say you place 2 into 3 + 6 but this is not balanced there should be a opening bracket with respect to this which is absent here first thing so every opening bracket must have a respective closing bracket and the same closing bracket okay I cannot say like this this is not balanced okay first thing second thing that a closing bracket should not come more than the opening brackets before so what I mean by that is let's say here there are two opening brackets and two closing brackets of the same type but is this balanced no here there are two closing brackets but if we look at the first three characters there are two closing bracket and one opening bracket which is not quite possible because the opening bracket comes first then the respective closing bracket comes if it is balanced so this will this is also not balanced okay so this is not balanced if the number of brackets are less is not balanced if the brackets are uh not of the same type and not of the not in proper order that is not balanced then this is also not balanced okay this is also not balanced because this opening bracket came afterwards so this closing bracket should come here now this much is balanced but if you say me this this is not balanced right uh this closing bracket should come after after this or this opening bracket should come here the square opening bracket this is not balanced so we need to keep of these things in mind now how can we solve it efficiently so we can solve this question with the help of our state data structure okay so how can we solve it with the help of the St data structure so what we can do is whenever we see if you remember in the stack we can uh access the element from the top only right and uh whenever we want to insert an element that also we can do on the top of the St only so what we can do is we can Traverse the expression from left to right whenever we get a opening bracket of any type whether it be this or this or this we will push it inside the stack whenever we get a closing bracket we will match it with the top of the stack right if that opening bracket is same as same kind as that closing bracket we will consider it as a pair and we will pop out the top element of the stack right so we have found one pair but if they do not match then that is not balanced right and if the stack is empty there is no opening bracket with respect to a closing bracket then also it is not balanced if at the end of this process if my stack is not empty it means there are more opening brackets than closing bracket that is also not balanced okay so what I'm trying to say is let us take this example so it is like this okay so whenever there is opening bracket I will push it inside my stack okay this is also opening bracket I will push it inside my stack now this is a closing bracket so I will match it with the top of the stack are they of the same kind yes both of them are circular so I will pop this element out and I will consider this and this to be a pair okay so now my stack contains only closing bracket now I got this opening bracket so whenever I get opening bracket I push it inside my stack now I got this closing bracket so I match it with the top of the stack why we match it with the top of the stack because the opening bracket which came last the respective closing bracket will come first okay why this is not balanced because the last opening bracket was circular but the first closing bracket was a square circular would have come first right that's why we are taking the stack data structure because in this last in comes first out so whatever is the last opening bracket the respective closing bracket should come first in the string okay so now we match it with this so this and this are same kind this is closing bracket so I'll pop it out from this and assume that this and this are pair okay now again I have a closing bracket I will compare it with the stop of stack the top of the stack is this these two are the both the square brackets so I will pop this out this also out so after I complete the traversal if my stack is empty and at any step of at every step whenever I got a closing bracket I found a respective opening bracket at the top of the stack and after completing this process if my stack is empty it means that this is a balanced parenthesis because for every opening bracket there was a respective closing bracket and that to in the same order that's why our stack was empty at uh at the end of the process and we didn't found any mistake in between okay now let's run on this okay uh let's run on this so first of all I'll push this inside the stack uh then uh this is the closing bracket so I will pop this out the so I will form this pair and I will move further now this is a closing bracket but my stack is empty there is no respective opening bracket so at this point of time I can say there is no opening bracket with respect to this so it is not possible I will break out from the loop and I will return false okay so this is not possible so this is done this is done uh now let's have a look at this so this is the opening bracket I will push it here uh then uh this is the closing bracket so I will see the top of the stack but this is circular this is square they are not of the same kind so they do not form a pair so again I will return false okay so this is also not possible uh now here also similar thing will happen uh opening closing closing opening so first of all I'll push opening bracket inside the stack then I see this closing bracket I will pop this out then I again see closing bracket but my stack is empty so there is no opening bracket with respect to this okay so this is also not valid uh then we look if we look at this so it is like this right so first of all I push inside the St this opening bracket uh then I push inside the St this opening bracket then I found a closing bracket now that closing bracket is not matching with the top of the stack opening bracket okay they are not of the same kind so they also cannot form a pair and this is also not valid so in this way basically what we will do is we will move from left to right whenever we encounter opening bracket we will push it inside the stack whenever we encounter a closing bracket we match it with the top of the stack if they are of the same kind we consider it to be a pair and pop the top element of the stack if they are not of the same kind or if the stack is empty we assume that uh the parenthesis is not balanced and we Mark answer is false and after completing the process if the stack is not empty in that case also the number of opening brackets are more as compared to closing brackets and in that case also we will return false for example if my uh string is this okay so first of all I will push this inside my stack then there is again opening bracket so I will push it inside my stack then there is closing bracket so I will pop it out from my stack I have completed but stack is not empty so there is no closing bracket with respect to this opening bracket so this is also not possible now let's look at its actual implementation so if we look at the actual implementation so this is the function which we need to complete this is string X which is given to us in the input this is the stack x uh this is the stack s which I'm taking which is of type character and I have taken a size of the expression string I have taken one variable I and I have taken one flag variable F I have marked it as one so it means that I'm assuming that parenthesis is balanced if at any point of time I found that the brackets are not matching or I do not get a pair for a particular bracket then I will make FS zero okay so that is why I have used flag variable F then I have used the loop from I = to 0 to n if x of I is opening bracket or this or this so if the x ofi is opening bracket of any kind push it inside the stack else if it is not a opening bracket then find the respective pair on the top of the stack if exist if stack is empty so there is no respective open bracket for the closing bracket I will Mark F variable as zero and I will break out of the full loop there is no need to check further if the stack is not empty then check if the stack. top is this opening bracket and if x of I is this closing bracket then po it out well and good if the top bracket in the stack is this and if the x of I is this then also they are forming a pair well and good pop it out if the top of the stack is this opening bracket and if x of I is this closing bracket then also they are forming a pack pair well and good pop it out from the uh stack other than this any other pairs do not match okay so I will Mark flag variable as zero and break out of the for Loop so when I come out I also need to check if the stack is empty or not if stack is not empty then also I need to Mark flag variable as false because the number of opening brackets are more than the number of closing brackets at the end if my flag variables remains one I will return true that the parenthesis balanced if at any point of time my flag variable BEC zero I will return false okay so this is the implementation what will be the time complexity time complexity will be big of n because at every step I am either pushing an element inside the stack or popping at element outside of the stack this is n size full loop and these are all constant time operations and what will be the auxilary space the auxiliary space here will also be Big O of n why because we are pushing the element inside the stack whenever we get a opening bracket so a stack is used okay let's say there are n by2 opening brackets first and N by2 closing brackets afterwards so we push n by2 elements inside the stack so that is nothing but big go of n space right so this is the time complexity and this is the auxiliary space now let's submit this code so let's submit it so we have solved this question successfully I hope you have understood this solution completely thank you