A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
This is a very well-written essay which explains its computing concepts effectively and thoroughly. I upvoted.<p>However, the bit at the end with the balanced parentheses matchers being a bad interview question seems to be missing the forest for the trees. A simple solution to this problem which has nothing to do with any of the computational theory discussed:<p><pre><code>   def is_balanced_parens(s):
       nesting_depth = 0
       contains_nesting = False

       for c in s:
           if c == &#x27;(&#x27;:
               nesting_depth += 1
               contains_nesting = True
           elif c == &#x27;)&#x27;:
               nesting_depth -= 1
           else:
               return False

           if nesting_depth &lt; 0:
               return False

       return contains_nesting and nesting_depth == 0
</code></pre>
This isn&#x27;t that hard of a problem, and if an interview candidate couldn&#x27;t come up with a basic solution like this, I&#x27;d very much like to know that.