Balanced Parentheses Problem Since this is such a famous programming problem, the chances are that most of us would have solved this during the CS101 course or somewhere else. Nevertheless, I still insist that we do skim through the problem statement once, before moving to the next sections. Let’s say that we’ve have got an . Then, our input string is said to be balanced when it meets two criteria: input string that can only contain brackets [], parentheses (), and braces {} LOFC ( ) implies that the one that opens last is the first one to close Last Opened First Closed LOFC takes into consideration that the open and close parentheses belong to the same pair, namely (), [], and {} Further, . if the input string is empty, then we’d say that it’s balanced Sample Input Data Next, let’s take a look at a few sample input strings and find out if they’re balanced or not: [()[]{}]{} is balanced [ ][ ]() is balanced () is balanced ))(( is not balanced {) is not balanced Biased Minds Have a Small Room for Headspace Yes, I know some of us would have already created a mental picture of a stack to start solving this problem. Though, that’s a good thing that you’ve solved this before, or maybe you read this problem for the first time and came up with a stack-based solution in no time. However, I urge you to , so that your thoughts are not biased. free up your headspace for now Solution using Headspace The whole as we’ll see. Further, by no means do I mean that it’s a better approach in terms of the time complexity of the algorithm! point of solving it with regular expressions is that it’s more intuitive to code First, let's revisit the first one in the list of sample inputs from the previous section: [()[]{}]{} Now, let’s try to it. We can be a genius to solve it fast, but we need to observe this thinking process slowly. Further, we should do everything in mind. That means we must refrain from using a pen and paper. observe our minds while we’re trying to solve Although we shouldn’t need more than , nonetheless, we can take as much time as we need to finish this activity with satisfaction. 3 minutes There’s no point in going further unless we spend some time here. Nobody is judging us if we’re slow — The slower, the better, but we must focus entirely on this activity to complete it in a single stretch. And, whenever we’re ready, let’s try to answer some questions: Did we solve it in a single stretch? Were we able to focus on patterns such as (), {}, and [] in the string? What did we do when we spotted the balanced patterns, namely (), {}, []? Let’s pat our mind for giving us a spacious headspace to visualize the complete process of solving it. Now, everybody could have visualized this differently. For now, let me put forward how I visualized it. First, I was quickly able to spot the three patterns of (), [], {} inside the wider square bracket, along with the {} pattern on the extreme right side. However, I must mention that I didn’t actually see that there’s a wider bracket that contains the three balanced parentheses. Then, once I had spotted a few balanced patterns, I tried to focus a bit more by ignoring the already discovered ones from my sight. As a result, I was able to see that there’s one pattern of [] that contained the earlier observed patterns. Next, I know there were no more new patterns that I could spot, and if I ignore all these patterns, then I had nothing but an empty string. Of course, I had to focus more as I advanced towards the next step. As they say, a picture is worth a thousand words, so I tried to sketch this activity later, to portray a better view of the entire process: Implementation Using sed Ah! I know. I know. Execution is what excites a lot of us — We, the developers like action. Seeing code in action thrills us. Isn’t it? But, ? Really, sed? Not Java, Python, Kotlin, Go, Haskell. Not even C? sed Yes, sed, it is. 🙂 . In fact, it’s a . So, why not! sed is an excellent tool for pattern matching Turing complete programming language Anyway, we’re following the headspace approach, and will let us formalize our thoughts around patterns in the form of code quite easily: sed :combine s/ //g s/ //g s/ //g t combine s/^$/balanced/p t s/.*/Unbalanced/p \( \) \{ \} \[ \] That’s all our code literally. Moreover, . Isn’t it wonderful? it works for an input stream, not just for a single string As much as I’m in love with this simple solution, I also agree, if you’re not familiar with sed, then these lines could be a bit overwhelming for you. So, let me summarise it for you. As such, . For substitution, it uses the , substitution function of sed with the global flag, to apply the effect at all occurrences: our script uses the concepts of a simple loop and substitution using regex s g s replacement /regex/ /g Further, we continue doing the pattern matching and substitutions until we can’t find any of the three patterns. We stay in the loop using the , test function: t t label For this, we had earlier : defined our label called combine using the : (label) function : label We must note that the , test function branches out to the label if the last substitution was successful, else the flow continues line-by-line. t Once we’ve come out of the loop, we’ll either have an empty string for balanced cases or a non-empty string for unbalanced ones. As a result, we again use the , substitution function with the print, flag to display a message saying “balanced” or “unbalanced.” s p But, wait, at the second last line, we didn’t use any label to do conditional branching using the , test function: t t That also happens when all the commands in the script have finished executing for the current cycle. Without the label, the test function restarts the execution cycle for the next line in the input stream. Now, let’s take a leap of faith and test this with a few sample input strings. Does Our code work? First, let’s take a look at our input strings: % nl input_parantheses.txt 1 [()[]{}]{} 2 [][]() 3 () 4 ))(( 5 {) 6 (()()) 7 )) 8 () 9 )()( Finally, let’s execute our script and see the fruit of our labor: % sed -E -n -f balanced_parantheses.sed input_parantheses.txt | nl 1 balanced 2 balanced 3 balanced 4 Unbalanced 5 Unbalanced 6 balanced 7 Unbalanced 8 balanced 9 Unbalanced Sigh! We can see that the output for each line of input meets the expected result. Conclusion In this tutorial, we relied on our intuitions and headspace to arrive at a . Additionally, we tasted a few basic regular expressions while implementing the solution in sed. good enough solution for the problem of balanced parentheses References [1] Leetcode Valid Parentheses Problem [2] Regular Expressions [3] , Stream Editor sed [4] , Line Numbering Utility nl
