What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this.
It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting.
> What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this.
Two critiques, one minor, and one major:
Minor critique: is_balanced is a pure function. It doesn't need to be wrapped in a class, and an object doesn't need to be instantiated to call it. This adds complexity and in general is a bad habit. Languages like Java require classes, but that's Java exposing details of its underlying implementation, not a pattern to be imitated.
Major critique: try your function with the string "((((((]]]]]". In general, your approach doesn't work, because for whatever numbers you use (such as x=1 and y=1.2) the scores will "collide" at when there are lcm(x,y) where lcm is the least common multiple function. There's an even subtler bug for the string "{)(}".
> It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting.
Yes, once you're generalizing I think the PDA becomes basically the simplest solution.
> P.S. your site is down
Thanks! It actually wasn't down, my HN profile was just linking to an old URL. I fixed it. :)
Thanks! Wow my implementation sucks! What do you mean by PDA?
The whole Solution().runFunc() thing I just kind of picked up from LeetCode-esque constructions, but I definitely see your point on it being a pure function.
What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this.
It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting.
P.S. your site is down