Detecting bad syntax in a string

Question

I just went through those interview coding quizzes for the first time and I'm somewhere between submerging myself in a tub of dran-o and investing in No Tears bubble bath products along with a bunch of toasters.

The problem was as follows:

If you're given a string like "zx(c)abcde[z{x]}", write a function that returns true if the syntax is correct and false if the syntax is incorrect: for example, in that string the brackets and braces are messed up. In other words "{hello}mot[o]" will pass but "{hello}mo{[t}" would not.

My throught process went like: keep a list of opening and closing bracket/brace/parens positions, then see if there is overlap. But that wasn't an optimal solution so I bombed it.

I'd like some help understanding how to solve this problem.

Thanks in advance.

how did you keep a track of their positions? This could be boiled down to how you evaluate infix expressions. Just push open bracket to stack and pop when you encounter close bracket and in the end check if stack is empty — noMAD, Jun 06 '14 at 19:47
@noMAD could you explain this as an answer? I had something like that in the back of my mind but I totally froze and felt like I had an aneurysm — dsp_099, Jun 06 '14 at 19:50

Cary Swoveland · Accepted Answer · 2014-06-06T23:01:02.730

5

[Edit: I've incorporated both of @sawa's excellent suggestions.]

One way you can do this is with a stack.

MATCH   = { '['=>']', '('=>')', '{'=>'}' }
OPENING = MATCH.keys
CLOSING = MATCH.values

def check_for_match(str)
  str.chars.each_with_object([]) do |c, arr|
    case c
    when *OPENING
      arr << c
    when *CLOSING
      return false unless c.eql?(MATCH[arr.pop])
    end
  end.empty?
end

check_for_match("zx(c)abcde[z{x]}") #=> false
check_for_match("zx(c)abcde[z{x}]") #=> true

edited Jun 06 '14 at 23:01

answered Jun 06 '14 at 19:59

Cary Swoveland

106,649
6
63
100

@meagar, I think we did the same edit simultaneously, but thanks! – Cary Swoveland Jun 06 '14 at 20:04
`case c; when *OPENING; ...; when *CLOSING; ...` would be better. – sawa Jun 06 '14 at 20:37
You can also simplify `return false if (arr.empty? or (c != MATCH[arr.last])); arr.pop` to `return false unless c == MATCH[arr.pop]`. – sawa Jun 06 '14 at 20:41
It should not be `c = MATCH[arr.pop]` but `c == MATCH[arr.pop]`. – sawa Jun 06 '14 at 21:26
Can you explain what does the * before OPENING and CLOSING do? Never seen that before. – dsp_099 Jun 07 '14 at 00:16
@dsp_099, It's called the "splat" operator. Here `when *['(', '[', '{']` is the same as `when '(', '[', '{'`. Read [this article](http://endofline.wordpress.com/2011/01/21/the-strange-ruby-splat/) and you'll understand both how it's used and why it's called "splat". – Cary Swoveland Jun 07 '14 at 01:11

Cary Swoveland · Answer 2 · 2014-06-07T01:16:28.933

[Edit: I thought this question seemed familiar. I and several others answered it a while ago.]

Another way to do this is to first strip out the irrelevant characters, then sequentially remove adjacent matching pairs until either the string is empty (return true) or the string is not empty and there are no more matching adjacent pairs (return false).

def check_for_match(str)
  str = str.gsub(/[^\(\)\[\]\{\}]/, '')
  while str.gsub!(/\(\)|\[\]|\{\}/, ''); end
  str.empty?
end

check_for_match("zx(c)abcde[z{x]}") #=> false
check_for_match("zx(c)abcde[z{x}]") #=> true

Reader challenge: provide a proof that the syntax is incorrect when false is returned.

score 1 · Answer 3 · answered Jun 06 '14 at 19:50

1

I would replace each bracket with an XML tag, and just run it through an XML validator. It'll pick out weird stuff like this:

<bracket>stuff<curly>morestuff</bracket></curly>

This will fail XML validation, so you can just return that.

answered Jun 06 '14 at 19:50

Nelson

2,040
17
23

An XML validator is absolutely **massive** overkill for this, and a huge dependancy to drag in for such a simple problem. – user229044 Jun 06 '14 at 20:01
Well, to be fair, it's an interview exam, and this will raise eyebrows. :) I realize using XML validator is very massive overkill, but at the end of the day, it needs to work and work reliably, quickly, and without crazy debugging. I can't imagine a RegEx be any easier to debug... easier to run an XML validator than to debug a RegEx IMO. – Nelson Jun 09 '14 at 15:37
To be honest I personally would've used the RegEx solution :) But the XML validator has way more testing backing than other methods because W3C won't let something like this slip, and it has huge amounts of credibility. – Nelson Jun 09 '14 at 23:12

Detecting bad syntax in a string

3 Answers3