7 ms·
I really like this solution, because it generalizes in (what might be) a surprising way. The basic approach works by associating '(' with the number 1, ')' wit
by Twisol 8y ago
I really like this solution, because it generalizes in (what might be) a surprising way.
The basic approach works by associating '(' with the number 1, ')' with the number -1, and replacing string concatenation with addition. The empty string is just 0. A balanced string of parenthesis is one where every prefix has a non-negative valuation and the whole string has a zero valuation.
This valuation function is a monoid homomorphism: the sum of the values of two strings is the same as the value of their concatenation. Membership in our language is a matter of checking the valuation of some set of related strings (here, all prefixes). Converting the problem into this valuation monoid ends up being super convenient.
This solution breaks down into three interwoven but logically separate pieces: identifying the related strings to check, computing their valuations, and validating the valuations. You can tweak any of these steps individually and get a different language.
import operator
def scan(f, initial, iterable):
accumulator = initial
for value in iterable:
accumulator = f(accumulator, value)
yield accumulator
def valuation(ch):
return {'(': 1, ')': -1}[ch]
def is_balanced_parentheses(s):
values = map(valuation, s)
for value in scan(operator.add, 0, values):
if value < 0:
return False
return (value == 0)
- braythwayt 8y ago> A balanced string of parenthesis is one where every prefix has a non-negative valuation and the whole string has a zero valuation. Speaking of coming up with solutions from first principles, I had a candidate come up with the following: Map the opening and closing parentheses to indices, in two arrays. Example: For the string `(())()`, the two arrays would be `[0, 1, 4]` for `(` and `[2, 3, 5]` for `)`. If the arrays of indices are not the same length, it isn't balanced. If they are the same length, go through the two arrays in pairs. The candidate didn't express it this way, but I thought "zip the arrays" in my mind, so I'll express it that way, we get `[[0, 2], [1, 3], [4, 5]]`. The candidate then said, if in each of these pairs, the index for `)` is greater than the index for `(`, the parentheses are balanced. Which is mathematically equivalent to a stack or a counter (the optimized degenerate case) or the prefix valuation. Of course it's not as efficient as other solutions, and I don't see it generalizing, but hey... It was inventive, in my mind.
- Anon84 8y agoIt actually generalizes pretty well... You just need an array for each type of parenthesis, so if your language is "(){}" you would need 4 vectors and play the same "zipped" game two by two. You can also generalize the counting solution (where "(" = +1 and ")" = -1) to this scenario using vectors ("(" = [1,0], "{" = [0, 1], ")" = [-1, 0], "}" = [0, -1]), etc. If you are only interested in pairs of tokens, there's probably a bitstring solution too... Efficiency, on the other hand, is not the best.
- braythwayt 8y agoI may not understand you. What about the string `({)}`? That is not balanced, so how would any counting or pairwise comparison work?
- Twisol 8y agoNo, you're right -- I had the same thought as 'Anon84 before I realized I was thinking of a different kind of language. The language 'Anon84 is thinking of is useful for thinking about concurrent systems, where each kind of bracket is associated with a particular agent. What's important is not that the brackets are mutually well-nested, but only that each kind of bracket is independently well-nested. This independence property means that "({)}" is a well-formed string, since ignoring everything but round parentheses gives "()", and ignoring everything but curly braces gives "{}". The Dyck language family is different. The entanglement between types of brackets means that you can't do a simple tensor like we'd like to.
- Anon84 8y agoYes, you are both quite correct (I was thinking along the lines mentioned by Twisol). I was looking at the basic approach as a walk in 1D. In the students representation, this means that each tuple is ordered, implying a move forward (you start with a "(" and eventually end at a ")". As a walk, this means that you return to the origin without ever becoming negative. In my rush, I generalized too quickly for the case of the two brackets as just a similar random walk in 2D. This of course doesn't work in the example you mentioned. If () corresponds to the xx dimension and {} to the yy axis: - With "({)}" you do return to the origin [[1, 0], [1,1], [0, 1], [0, 0]] but not in a valid path. - You basically need one extra rule. At each step, you can move forward in any direction (open a new type of bracket), but you can only move back in the direction you just came from (close the previous one). This of course is just a weird way of representing a stack, because you still need to keep track of the entire history anyway (which you could just store as the brackets themselves. To paraphrase one of my idols, "More (dimensions) is different"...