ruby - 检查字符串是否有平衡括号

Question

我目前正在做一个 Ruby 问题测验，但我不确定我的解决方案是否正确。运行检查后，它显示编译成功，但我只是担心这不是正确的答案。

问题:

A string S consisting only of characters '(' and ')' is called properly nested if:

• S is empty,
• S has the form "(U)" where U is a properly nested string,
• S has the form "VW" where V and W are properly nested strings.

For example, "(()(())())" is properly nested and "())" isn't.

Write a function

def nesting(s)

that given a string S returns 1 if S is properly nested and 0 otherwise. Assume that the length of S does not exceed 1,000,000. Assume that S consists only of characters '(' and ')'.

For example, given S = "(()(())())" the function should return 1 and given S = "())" the function should return 0, as explained above.

解决方法:

def nesting ( s )
    # write your code here

    if s == '(()(())())' && s.length <= 1000000
        return 1
    elsif s == ' ' && s.length <= 1000000
        return 1
    elsif 
        s == '())'
        return 0
    end
end

Answer 1

以下是应该实现该目标的两种算法的描述。我将把它作为练习留给读者将它们转化为代码(除非您明确要求代码解决方案):

1. 从一个设置为 0 的变量开始并遍历字符串中的每个字符:当您看到 '(' 时，将变量加一；当您看到 ')' 时, 从变量中减去一个。如果变量变为负数，则表示您看到了太多 ')' 并且可以立即返回 0。如果您完成对字符的循环并且变量不完全是 0，那么您有太多的 '(' 并且应该返回 0。

2. 删除字符串中每次出现的“()”(替换为“”)。继续这样做，直到您发现没有任何内容被替换(检查 gsub! 的返回值)。如果字符串为空，则匹配括号。如果字符串不为空，则表示不匹配。