Check for balanced parentheses using stack

Check for balanced parentheses using stack

Check for balanced parentheses using stack

See complete series on data structures here:
   • Data structures  

Algorithm or program to check for balanced parentheses in an expression using stack data structure. This is a popular programming interview question.

See source code here:
https://gist.github.com/mycodeschool/…

For practice problems and more, visit: http://www.mycodeschool.com

Like us on Facebook: https://www.facebook.com/MyCodeSchool

Follow us on twitter: https://twitter.com/mycodeschool


Content

0.429 -> In our previous lesson, we saw one simple application of stack
3.75 -> we saw that stack can be used to
6.82 -> reverse a list or collection or may be to simply traverse
10.79 -> a list or collection in reverse order. In this lesson, we will discuss another
14.769 -> famous problem that can be solved using stack.
18 -> And this is also a popular programming interview question
21.85 -> and the problem is, given an expression in the form of
25.82 -> a string comprising of let's say constants,variables,
30.369 -> operators and parenthesis and when I say parenthesis I also want to include
35.999 -> curly braces and brackets and my definition of parenthesis.
39.519 -> so my expression or string can contain characters that can be
44.01 -> upper or lower case letters, symbols for operators
47.879 -> and an opening or closing parenthesis
51.519 -> or an opening or closing curly brace on an opening or closing square
56.28 -> bracket. Let's write down some expressions here. I'm going to write
60.17 -> a simple expression. We have one simple expression with one pair of opening
64.809 -> and closing parenthesis.
66.29 -> Here in this expression we have nested parenthesis.
69.79 -> Now given such expressions we want to write a program
73.65 -> that would tell us whether parenthesis in the expression
77.16 -> are balanced or not and what do we really mean by balanced parenthesis
81.61 -> what we mean by balanced parenthesis
83.76 -> is that corresponding to each opening parenthesis
87.3 -> or opening curly brace or opening bracket we should have
90.46 -> a closing counter part in correct
93.48 -> order. These two expressions here are balanced.
97.1 -> However this next expression is
100.23 -> not balanced.A closing curly brace is missing here
104.57 -> This next expression is also not balanced because we're missing
108.58 -> an opening square bracket here. This next one is also not balanced because
113.49 -> corresponding to this opening curly brace we do not have
116.35 -> a closing curly brace and corresponding to this closing
119.36 -> parenthesis we do not have an opening parenthesis. if we are opening
122.909 -> with a curly brace,we should also close with a curly brace.These
126.11 -> 2 count for each other.Checking for balanced parenthesis is one of the
131.079 -> tasks performed by a compiler, when we write a program we often miss
136.48 -> an opening or closing curly brace or an opening or closing parenthesis.
141.769 -> Compiler must check for this balancing and if symbols are not balanced
147.18 -> it should give you an error.In this problem here
150.65 -> what's inside parenthesis does not matter,
153.93 -> we do not want to check for correctness of anything that is inside
157.639 -> a parenthesis so in the string any character other than opening and closing
162.209 -> parenthesis or opening and closing curly brace or opening and closing
165.859 -> square bracket
166.79 -> can be ignored. This problem sometimes is better stated like this
171.54 -> "Given a string comprising only of opening and closing characters
175.9 -> of parenthesis braces or brackets
178.9 -> we want to check for balancing". So only these characters and their order is
184.739 -> important.
185.469 -> While parsing a real expression we can simply ignore other characters.
189.95 -> All we care about is these characters and their order.
193.129 -> Okay so now how do we solve this problem?. One straight forward thing that comes to
197.959 -> mind is
198.859 -> that because we should have a closing counter part for
202.709 -> an opening parenthesis or opening curly brace
205.989 -> or opening square bracket what we can do is, we can count the number of
210.219 -> opening and closing symbols for each of these
213.379 -> three types and they should be equal. So the number of opening parenthesis should
217.999 -> be equal to number of closing parenthesis.
219.95 -> and the number of opening curly braces should be equal to number of closings
224.2 -> curly braces and same should be true for square brackets as well
227.859 -> but it will not be good enough this expression here
231.709 -> has one opening parenthesis and one closing parenthesis
235.459 -> but it's not balanced this next one
238.859 -> is balanced but this one with same number of characters
242.9 -> of each type as the second expression is not balanced
246.829 -> so this approach won't work. Apart from count being equal that are some other
252.219 -> properties that must be conserved.
254.569 -> Every opening parenthesis must find a closing counterpart to its right
259 -> and every closing parenthesis must find an opening counterpart
263.77 -> in its left which is not true in the first expression.
268.02 -> And the other property that must be conserved is that a parenthesis
271.83 -> can close
272.66 -> only when all the parenthesis opened
275.68 -> after it are closed. This parenthesis has been opened after
280.55 -> this square bracket so this square bracket
284.04 -> can not close unless this parenthesis is closed.
287.7 -> Anything that is opened last
291.04 -> should be closed first. Well actually it should not
294.11 -> be last opened first closed in this example here
297.63 -> this is getting opened last but this guy I
301.9 -> that is open previous to this is closed first
305.01 -> and it is fine. The property that must be conserved is that
308.57 -> as we scan the expression from left to right
311.9 -> any closer should be for the previous unclosed parenthesis
316.67 -> any closer should be for the last unclosed.
320.7 -> Let's scan some expressions from left to right and see how it's true.
325.42 -> Let's scan this last one we will go from left to right
329.16 -> first character an opening of the square bracket
332.34 -> second one is an opening parenthesis
335.57 -> Lets mark opening of closed parenthesis in red.
340.2 -> Okay now we have a closer here , the third character is a closer.
344.44 -> this should be the closer for last unclosed.
348.48 -> So this should be the closer for this one, this guy,
352.85 -> this opening parenthesis. last unclosed now is this guy.
358.54 -> Next character once again is an opening parenthesis.
362.21 -> Now we have two unclosed parenthesis at this stage and this one is the last
366.76 -> unclosed,
368.25 -> the next one's a closure.So it should be closer for the last unclosed.
373.7 -> Now the last unclosed once again is the opening of square bracket
377.89 -> now when we have a closer it should be closer
381.15 -> for this guy.
384.509 -> we can use this approach to solve this problem what we can do is we can
387.96 -> scan the expression from left to right
390.449 -> and as we scan at any stage we can keep track of
394.169 -> all the unclosed parenthesis basically what we can do is whenever we
398.35 -> get an opening symbol an opening parenthesis an opening curly brace or
403.09 -> an opening square bracket, we can add it
406.539 -> to a list. If we get up closing symbol
410.46 -> it should be the closer for the last element in the list,
413.8 -> in case of an inconsistency like if
417.1 -> the last opening symbol in the list is not of the same type as the
420.87 -> closing symbol or if there is no last opening symbol at all because the list
425.51 -> is
425.949 -> empty. We can stop this whole process and say that
429.31 -> parenthesis are not balanced else we can removed the last opening symbol in the
433.83 -> list
434.36 -> because we have got its counterpart and continue this whole process.
438.82 -> Things will be further clear if I will run through an example.
442.22 -> I will run through this last example once again.
445.43 -> We are going to scan this expression from left to right
448.91 -> and we will maintain a list to keep track of all the
452.15 -> opening parenthesis that are not yet closed.
455.47 -> We will keep the track of all the unclosed parenthesis
458.76 -> opened but not closed. Initially this list is empty,
462.07 -> the first character that we have got is an opening of square bracket.
466.94 -> This will go into the list and we will move to the next character
470.44 -> the next character is an opening parenthesis so one stick,
473.849 -> once again it should go to the list. We should always insert at the end in the
479.07 -> list.
479.539 -> the next character is a closing of parenthesis now we must look at the
484.099 -> last
484.68 -> opening symbol in the list and if it is of the same type
488.9 -> then we have got it's counterpart and we should remove this.
492.08 -> Now we move on to the next character this is once again an opening
495.69 -> parenthesis,
496.53 -> it should go in the list at the end.
499.55 -> The next character is a closing of parenthesis so we will look at
503.49 -> the last element in the list, it's an opening parenthesis,
507.96 -> so we can remove it from the list and now we go to the last character which is
512.94 -> a closing of square bracket once again we need to look at
515.69 -> the last element in the list we have one
519.27 -> element only one element in the list at this stage, its
522.64 -> an opening of square bracket so once again we can remove it from the list.
526.839 -> Now we're done scanning the list and the list is empty once again
531 -> if everything is alright if parenthesis are balanced
534.13 -> we will always end with an empty list
537.32 -> and if list is not empty then some opening parenthesis haven't found its
542.38 -> closing counterpart
543.75 -> and expression is not balanced. One thing worth noticing here is that
548.18 -> we are always inserting and removing
551.23 -> one element at a time from the same end of the list
554.51 -> in this whole process whatever is coming in last in the list is going out first,
559.589 -> there is a special kind of list that
562.64 -> enforces this behavior that element should be inserted and removed
567.01 -> from the same end and we call it a stack.
570.72 -> In a stack we can insert and remove an element one at a time from the same
575.709 -> end in constant time. so what we can do is whenever we get
579.63 -> an opening symbol while scanning the list we can push it onto the stack
584.57 -> and when we get a closing symbol we can check whether
588 -> the opening symbol at the top of stack is of the same type
592.209 -> has the closing symbol, if its of the same type we can pop,
595.79 -> if it's not of the same type we can simply say that parenthesis are not
600.339 -> balanced
601.02 -> I will quickly write pseudocode for this logic
604.07 -> I'm going to write a function named CheckBalancedParenthesis() that will
607.86 -> take an expression
609.11 -> in the form of a string as argument.
612.68 -> first of all iI will store the number of characters
615.73 -> in the string in a variable and then
619.02 -> I will create a stack and I will create a stack of characters
623.68 -> and now I will scan the expression from left to right using
627.66 -> a loop, while scanning if the character is an opening symbol if
631.88 -> it's an opening parenthesis or opening curly brace or opening square bracket
636.579 -> we can push that character onto the stack, let's say this function
639.85 -> Push() will push up character onto
642.94 -> S else if exp[i] or the character
646.74 -> at ith position while scanning is a closing symbol of
650.48 -> any of the three types. We can have two scenarios if stack is empty,
655.55 -> or top of stack does not pair with the closing symbol
660.8 -> if we have a closing of Parenthesis then the top of stack should be an opening of
665.569 -> Parenthesis.
666.709 -> It cannot be an opening of curly brace, in such a scenario we can conclude that
671.14 -> the parenthesis
672.47 -> are not balanced else we can perform
675.6 -> a pop. Finally once a scanning is over
678.949 -> we can check whether a stack is empty or not if it's empty Parenthesis are balanced
683.39 -> if it's not they are not balanced.
686.41 -> so this is my pseudo code let's run through a couple of examples and see
690.76 -> whether this works for all scenarios all test cases or not.
694.68 -> Let's first look at this expression, the first thing that we're doing in our
698.52 -> code is that we're creating a stack of characters,
701.67 -> I have drawn logical representation of a stack here.
705.49 -> Okay now let's scan this string, let's say we have a zero-based index
709.63 -> and a string is just are character array, we are starting the scan and going inside
714.4 -> the loop.
715.329 -> This is a closing of Parenthesis so this if statement will not hold true
718.93 -> so we will go to the
720.24 -> else condition and now we will go inside the else
724.04 -> to check for this condition whether stack is empty or not
727.069 -> or whether the top of stack pairs
730.68 -> with this closing symbol or not, the stack is empty,
734.199 -> if the stack is empty there is no opening counterpart for this closing symbol.
739.079 -> so we will simply return false, returning means exiting the function
743.62 -> so we are simply concluding here that Parenthesis are not balanced and
747.29 -> exiting.
749.179 -> Let's go through this one now, first we have
751.92 -> an opening squad bracket so here we go to the first
755.439 -> if and push, next one is an
758.829 -> opening parenthesis once again it will be pushed next one
762.569 -> is a closing square bracket, so the condition for this else if will be true we
767.339 -> will go inside this
768.54 -> else if, now this time to top of stack
771.86 -> is an opening parenthesis it should have
774.98 -> been an opening square bracket and then only we would have
778.98 -> a pair so this time also we will have to return false
782.879 -> and exit. Okay now let's go through this one.
787.149 -> First we'll have a push, the next one
790.579 -> will also be a push, now next one is a closer of parenthesis
795.179 -> which pairs with the top of stack which is opening of parenthesis
799.379 -> so we will have a pop, we will go to the next character and this one once again
804.829 -> is an opening parenthesis so there will be a push.
807.41 -> next one is a closing parenthesis and the top is an opening parenthesis ,they
811.999 -> pair so there will be a pop, last character is a
815.579 -> closing curly brace so once again we will see whether the top of stack
820.369 -> is an opening curly brace or not? do we have a pair or not?
823.67 -> yes we have a pair so there will be a pop with this
827.679 -> our scanning will finish and finally stack should be empty
831.579 -> it is empty so we have balanced Parenthesis here
835.279 -> try implementing this pseudo code in the language of your choice and see whether
839.649 -> it works for all test cases or not.
841.589 -> If you want to look at my implementation you can check the description of this
844.999 -> video
845.6 -> for a link. In the coming lessons we will see some more problems on stack.
849.86 -> This is it for this lesson, thanks for watching!!

Source: https://www.youtube.com/watch?v=QZOLb0xHB_Q