检测字符串中的错误语法

Question

我刚刚第一次接受了那些采访编码测验,而我正介于淹没在一个dran-o的浴缸和投资No Tears泡泡浴产品以及一堆烤面包机之间.

问题如下:

如果给你一个字符串"zx(c)abcde[z{x]}",写一个函数,如果语法正确则返回true,如果语法不正确则返回false:例如,在该字符串中,括号和大括号混乱.换句话说,"{hello}mot[o]"会通过,但"{hello}mo{[t}"不会.

我的整个过程如下:保持一个开始和结束括号/括号/ parens位置列表,然后查看是否有重叠.但这不是最佳解决方案,因此我对其进行了轰炸.

我想帮助理解如何解决这个问题.

提前致谢.

Answer 1

[编辑:我已经纳入了@ sawa的优秀建议.]

一种方法是使用堆栈.

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