It 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...
Yes, 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"...
No, 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.
Efficiency, on the other hand, is not the best.