Monday, October 22, 2018

JavaScript pattern matching

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.

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){