Check if a string has balanced parentheses

Question

I'm currently working on a Ruby Problem quiz, but I'm not sure if my solution is correct. After starting the check, this shows that the compilation was successful, but I'm just worried that this is not the right answer.

Problem:

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

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

For example, "(() (()) ())" is correctly nested and "())" is not.

Write function

def nesting(s) 

which sets the string S, returns 1 if S is correctly nested and 0 otherwise. Suppose that the length S does not exceed 1,000,000 people. Suppose that S consists only of the characters '(' and ')'.

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

Decision:

 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

Here are descriptions of two algorithms that should fulfill the goal. I will leave this as a reading exercise to turn them into code (unless you explicitly request a solution for the code):

• Start with the variable set to 0 and pass through each character in the line: when you see the character '(', add it to the variable when you see ')', subtract from the variable. If the variable is always negative, you have seen too many ")" and you can immediately return 0 . If you end the loop through characters, and the variable is not exactly 0 , then you have too much "('and should return 0 .

• Delete all the lines '()' in the line (replace with ''). Continue to do this until you find that nothing has been replaced (check the gsub! return value gsub! ). If the string is empty, the brackets match. If the string is not empty, it is incompatible.

Answer 2

You should not just list the examples given. You must solve the problem as a whole. You should also not check that the length is below 1,000,000, you can assume that.

The most direct solution to this problem is to iterate through the line and keep track of how many brackets are open now. If you see a closing parenthesis when the parentheses are not open, the line is not balanced. If any parentheses remain open when you reach the end, the line is not balanced. Otherwise it is.

Alternatively, you can also include the specification directly in the regex pattern using the ruby ​​1.9 recursive regex function if you were so prone.

Answer 3

You can solve this problem theoretically. Using a grammar like this:

 S ← LSR | LR L ← ( R ← ) 

Grammar should be easily solvable by a recursive algorithm. That would be the most elegant solution. Otherwise, as already mentioned, count the open parentheses.

Answer 4

Here's a neat way to do this with an injection:

 class String def valid_parentheses? valid = true self.gsub(/[^\(\)]/, '').split('').inject(0) do |counter, parenthesis| counter += (parenthesis == '(' ? 1 : -1) valid = false if counter < 0 counter end.zero? && valid end end > "(a+b)".valid_parentheses? # => true > "(a+b)(".valid_parentheses? # => false > "(a+b))".valid_parentheses? # => false > "(a+b))(".valid_parentheses? # => false 

Answer 5

My algorithm will use stacks for this purpose. Stacks are designed to solve such problems.

Algorithm

• Define a hash that contains a list of balanced parentheses for instance {"(" => ")", "{" => "}" and so on ...}
• Declare a stack (in our case, an array), i.e. brackets = []
• Scroll the line using each_char and compare each character with hash keys and press it in brackets
• Inside the same loop, compare it with hash values ​​and enter the character from the brackets

• In the end, if the stack of brackets is empty, the brackets are balanced.

  def brackets_balanced?(string) return false if string.length < 2 brackets_hash = {"(" => ")", "{" => "}", "[" => "]"} brackets = [] string.each_char do |x| brackets.push(x) if brackets_hash.keys.include?(x) brackets.pop if brackets_hash.values.include?(x) end return brackets.empty? end

Answer 6

You are right to worry; I think that your end of the stick is very wrong and you solve the problem too literally (the information that the line does not exceed 1,000,000 characters is just so that people don’t worry about how slowly their code will work if the length was 100 times, and the examples are just examples - not the final list of strings you can expect to get)

I will not do the homework for you (by writing the code), but will give you a pointer to the solution that happens to me:

A line is correctly nested if each left bracket has a right bracket to the right of it or a correctly enclosed bracket between them. So, what about a recursive function or loop that deletes a string, matches "()". When your matches end, what are you left with? Nothing? Then it was a correctly nested string. Something else (for example, ')' or ') (' etc.) would mean that it was not properly nested in the first place.

Answer 7

Define Method:

 def check_nesting str pattern = /\(\)/ while str =~ pattern do str = str.gsub pattern, '' end str.length == 0 end 

And test it:

 >ruby nest.rb (()(())()) true >ruby nest.rb (() false >ruby nest.rb ((((())))) true >ruby nest.rb (() false >ruby nest.rb (()(((())))()) true >ruby nest.rb (()(((())))() false 

Answer 8

Your solution returns the correct answer for the strings "(() (()) ())" and "())". You definitely need a solution that works for any string!

How to start, how about counting the number of occurrences ( and ) and viewing if they are equal?