If you like JavaScript (and I have been writing quite a bit again recently) then you probably also love Reg “raganwald” Braithwaite's mind stretching JavaScript articles and books.
I have just been enjoying a recent post on pattern matching that is elegant and demanding of the reader. Fabulous stuff which I enjoyed greatly but all the time I was reading the piece there was a niggle at the back of my head. The niggle kept trying to intrude with the message "matching parentheses is what stacks are for". OK, not strictly true - stacks are for a lot of things but the thought that JavaScript arrays act as an archetypal stack out of the box doubled down on the message.
I had to try "my way" to see how that went.
The strings lefts and rights store the characters to be balanced in a nice extendable way. The first line that splits the function string argument uses the empty string as a delimiter so that the resulting array is constructed with each character in the input string becoming an individual array element.
The process is simple. If a left hand bracket character (lefts) is found then it is pushed onto the stack. If a right hand bracket character (rights) is found then the top element of the stack should be the matching left hand character. If the match is found then it is popped from the stack with any unmatched right hand items being added to the stack to force the correct result and to aid debugging. [If the test strings were likely to be long then you would probably force a return at that point.] The function returns true if the stack is empty after the process has run and otherwise false.
Works with raganwald's test strings such as ({}(()))(() => false and ({()[]})[[(){}]] => true.
Do we go with elegant or (brutal) pragmatic?
<Edit> Of course one of those lines of code should have been
</Edit>
<Addendum>
</Addendum>
I have just been enjoying a recent post on pattern matching that is elegant and demanding of the reader. Fabulous stuff which I enjoyed greatly but all the time I was reading the piece there was a niggle at the back of my head. The niggle kept trying to intrude with the message "matching parentheses is what stacks are for". OK, not strictly true - stacks are for a lot of things but the thought that JavaScript arrays act as an archetypal stack out of the box doubled down on the message.
I had to try "my way" to see how that went.
function balanced(str){
let chrs = str.split("");
let lefts = "({[";
let rights = ")}]";
let stack = [];
for(let i = 0; i < chrs.length; i++){
if(lefts.indexOf(chrs[i])>-1){
stack.push(chrs[i]);
} else {
let idx = rights.indexOf(chrs[i]);
if(idx >= 0 && idx <= 2){
if(stack[stack.length-1] === lefts.substr(idx,1)){
stack.pop();
} else {
stack.push(chrs[i]);
}
}
}
}
return stack.length === 0;
}
The strings lefts and rights store the characters to be balanced in a nice extendable way. The first line that splits the function string argument uses the empty string as a delimiter so that the resulting array is constructed with each character in the input string becoming an individual array element.
The process is simple. If a left hand bracket character (lefts) is found then it is pushed onto the stack. If a right hand bracket character (rights) is found then the top element of the stack should be the matching left hand character. If the match is found then it is popped from the stack with any unmatched right hand items being added to the stack to force the correct result and to aid debugging. [If the test strings were likely to be long then you would probably force a return at that point.] The function returns true if the stack is empty after the process has run and otherwise false.
Works with raganwald's test strings such as ({}(()))(() => false and ({()[]})[[(){}]] => true.
Do we go with elegant or (brutal) pragmatic?
<Edit> Of course one of those lines of code should have been
if(idx >= 0){
</Edit>
<Addendum>
2 comments:
I do trust all of the ideas you've presented on your post.
They're really convincing and can definitely work.
Nonetheless, the posts are too quick for
newbies. Could you please lengthen them a bit from next time?
Thanks for the post.
Hi Anonymous, this was not intended as a stand alone "how to" post but was supposed to be an extended comment on the raganwald post (linked above).
A stack structure is often used to help evaluate things like numeric expressions that include brackets and (of course) arithmetic operators with varied precedence. [You multiply or divide before adding or subtracting.] Brackets are resolved by pushing left hand brackets onto the stack to be followed by any enclosed arithmetic expressions. Once a right hand bracket turns up then the expression on the stack running back to the left hand bracket is evaluated. The left hand bracket is "popped" from the stack and the result of the arithmetic expression between the brackets pushed back onto the stack in it's place.
The little function in my post does the same sort of thing but without any arithmetical terms. It simply pushes left hand brackets (of all types) onto the stack as they are found in the original string. When a right hand bracket turns up any matching left hand bracket on the stack is popped off. At the end of the process, if the stack has one or more left hand bracket left then the string contains unmatched brackets.
Post a Comment