try to understand matching brackets & evaluation.

  • (2 Pages)
  • +
  • 1
  • 2

25 Replies - 1460 Views - Last Post: 30 January 2014 - 05:09 PM Rate Topic: -----

#1 heaphyg  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 30-August 13

try to understand matching brackets & evaluation.

Posted 28 January 2014 - 11:38 PM

Getting frustrated with trying to understand line 6. I'm pretty sure that the c parameters in this line refer to values that are to be matched up with potential key pairs in our left_symbols hash and that if no key is associated with the inputted value nil is returned. Other wise I am trying to work out the logic of this line. I am thrown off by left_symbols.key occurring twice in this line since I am interpreting that each occurrence of left_symbols.key outputs the same value in a single iteration of str. Thanks for any help.


def valid_string?(str)
  stack = []
  left_symbols = { '{' => '}', '[' => ']', '(' => ')' }
  str.each_char do |c|
    stack << c if left_symbols.key?(c)    # check if a string char is a left-bracket - if so stack it
    return false if left_symbols.key(c) && left_symbols.key(c) != stack.pop  # return the key associated with the inputed value if value exists - else nil
  end
  stack.empty?
end

puts valid_string?('[ ]')                  # returns true
puts valid_string?('[  ')                  # returns false
puts valid_string?('[ ( text ) {} ]')       # returns true
puts valid_string?('[ ( text { ) } ]')     # returns false


This post has been edited by modi123_1: 29 January 2014 - 01:53 PM
Reason for edit:: fixing title


Is This A Good Question/Topic? 0
  • +

Replies To: try to understand matching brackets & evaluation.

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7625
  • View blog
  • Posts: 12,855
  • Joined: 19-March 11

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 12:32 AM

So I'm actually a total ruby novice as well, but I can tell you that c is taking the value of each char in str, in turn. So in other languages you'd see something like

for c in str:
  # do stuff


but in ruby, you do it sort of inside out from that:

str.each_char do |c| {
  # do stuff
}


It's kind of cute, really. each_char returns an enumerator:

irb(main):058:0> "foo".each_char
=> #<Enumerable::Enumerator:0xb739da98>



and we pass that to the code block, where it works on each element of the enumeration.

The other thing that might be confusing here is

return false if left_symbols.key(c) && left_symbols.key(c) != stack.pop


This is lazy evaluation at work - you see this in many languages. A boolean operator evaluates its arguments from left to right, until it knows whether it can return true or false. && knows that it if the first argument is false, then the whole && is false (because false && true is false, and false && false is false) so it doesn't bother evaluating the right hand side, and the return is not executed. So that should clear up your other question.

As an aside, I'm not sure if there's a version issue or what it is but I'm getting an error on

left_symbols.key(c)


but when I change it to access the value with square brackets it seems to work fine so I'm going to assume that's what's meant.
Was This Post Helpful? 3
  • +
  • -

#3 heaphyg  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 30-August 13

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 10:44 AM

Sorry about that. I fixed it up. This works for me.

def valid_string?(str)
  stack = []
  left_symbols = { '{' => '}', '[' => ']', '(' => ')' }
  str.each_char do |c|
    stack << c if left_symbols.key?(c)    # check if a string char is a left-bracket - if so stack it.
    return false if left_symbols.key(c) && left_symbols.key(c) != stack.pop
  end
  stack.empty?
end

#puts valid_string?('[ ]')                  # returns true
#puts valid_string?('[  ')                  # returns false
puts valid_string?('[ ( text ) {} ]')       # returns true
#puts valid_string?('[ ( text { ) } ]')     # returns false


Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7625
  • View blog
  • Posts: 12,855
  • Joined: 19-March 11

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 10:48 AM

It's probably got something to do with the fact that I still have ruby 1.9.3 installed. I ought to update that, I guess
Was This Post Helpful? 1
  • +
  • -

#5 heaphyg  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 30-August 13

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 11:39 AM

Thanks again for explanation of the 'lazy evaluation'. That was definitely the missing key to my understanding.
Was This Post Helpful? 0
  • +
  • -

#6 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3326
  • View blog
  • Posts: 11,246
  • Joined: 12-December 12

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 01:14 PM

Apologies for piggy-backing but I'm still slightly confused by this. I understand the idea of lazy loading but am not sure how this function is working:

What happens to the right-brackets? Only the left-brackets are added to stack.
Does the popping all happen in one go?

I'll wrestle with it more myself but if someone can offer a description I will be grateful ;)
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7625
  • View blog
  • Posts: 12,855
  • Joined: 19-March 11

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 01:20 PM

Just looked it up: the key() method returns the key for a particular value. So I was wrong to read it as an access, it's a reverse lookup. So if the hash has a key for c, and the key for c is not the next thing on the stack, then we have an unbalanced paren situation
Was This Post Helpful? 1
  • +
  • -

#8 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3326
  • View blog
  • Posts: 11,246
  • Joined: 12-December 12

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 01:32 PM

I'm trying to break it down for the last example:
puts valid_string?('[ ( text { ) } ]')     # returns false

stack builds up like this:

Quote

["["]
["["]
["[", "("]
["[", "("]
["[", "("]
["[", "("]
["[", "("]
["[", "("]
["[", "("]
["[", "(", "{"]
["[", "(", "{"]
false

So.. it must return when it encounters ')' which is mis-matched? Mmm.. still haven't got it, must be a bit dim today :dontgetit:
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7625
  • View blog
  • Posts: 12,855
  • Joined: 19-March 11

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 01:41 PM

Quote

So.. it must return when it encounters ')' which is mis-matched?


Yep.

return false if left_symbols.key(c) && left_symbols.key(c) != stack.pop


left_symbols.key© returns a non-false value, so it's true, so it pops the stack and finds a mismatch, so the && is true on both sides, so it returns false. Up to that point, it either finds a left symbol, and stacks it, or it finds a non-right symbol, and ignores it.
Was This Post Helpful? 3
  • +
  • -

#10 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3326
  • View blog
  • Posts: 11,246
  • Joined: 12-December 12

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 02:33 PM

Thanks @jon, got it ;)

What was confusing me was the double-use of key:

key?(key) returns true or false if the key exists. This bit I understood.

key(value) returns the key (for value) or nil. Read in isolation this now makes sense, but seeing both versions for the first time, in the same code, was what threw me.

Aside: The docs for key?(key) has an example, but the example doesn't use key? it uses has_key?

Ruby is weird :whatsthat:

This post has been edited by andrewsw: 29 January 2014 - 02:37 PM

Was This Post Helpful? 0
  • +
  • -

#11 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7625
  • View blog
  • Posts: 12,855
  • Joined: 19-March 11

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 02:34 PM

Obviously, I was confused by that as well.
Was This Post Helpful? 0
  • +
  • -

#12 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3326
  • View blog
  • Posts: 11,246
  • Joined: 12-December 12

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 02:49 PM

    stack << c if left_symbols.key?(c)    
    # bung all the left-brackets on this stack
    return false if left_symbols.key(c) && left_symbols.key(c) != stack.pop
    # if this is a right-bracket then get its key, which is the corresponding left-bracket;
    # if this left-bracket isn't the last one added to the stack then bail (return false),
    # otherwise.. the left-bracket has been matched (to the right bracket) and is
    # removed from the stack.

Any characters other than left or right-brackets are ignored.

When the sequence finishes all left-brackets will either have been removed, having been paired with their right-brackets, or there are one or more unmatched left-brackets left in stack.

The function will only return true if all left-brackets have been correctly matched, and popped, and the stack is therefore empty.
Was This Post Helpful? 1
  • +
  • -

#13 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7625
  • View blog
  • Posts: 12,855
  • Joined: 19-March 11

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 02:54 PM

Quote

Any characters other than left or right-brackets are ignored.

When the sequence finishes all left-brackets will either have been removed, having been paired with their right-brackets, or there are one or more unmatched left-brackets left in stack.

The function will only return true if all left-brackets have been correctly matched, and popped, and the stack is therefore empty.


I think that's correct


Quote

Ruby is weird



That too.

One more thing that's not obvious: the result of the last evaluation is returned. This is not hugely weird, but it's certainly not obvious.
Was This Post Helpful? 0
  • +
  • -

#14 heaphyg  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 85
  • Joined: 30-August 13

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 02:57 PM

This is how I bork it down. The break down is in the comments.

def valid_string?(str)
  stack = []
  left_symbols = { '{' => '}', '[' => ']', '(' => ')' }
  str.each_char do |c|
    stack << c if left_symbols.key?(c)       # check if a string char is a left-bracket - if so stack it.
    return false if left_symbols.key(c) && left_symbols.key(c) != stack.pop  # the stack is only popped when right bracket are currently being iterated through and the match the last item stacked.
  end
  stack.empty? #this returns true or false
end

=begin
Line six immediately returns false on the left side of the && statement if the current character
in the iteration is a left-sided bracket. We are trying to match up right-sided brackets with 
the left-sided brackets most recently collected in our stack.
In other words if the current character in the iteration is a left-sided bracket false is returned automatically preventing
access to the stack.pop side of the && statement.
stack elements can only be 'popped' off when the current character in the iteration has a key
that matches the last char that was added to stack. If the stack is empty at the end of this
iteration the order/closure of brackets was correct - false if not correct. Stacks are sweet.
=end

puts valid_string?('[ ]') == true                 #=> true
puts valid_string?('[  ') == false                #=> true
puts valid_string?('[ ( text ) {} ]') == true     #=> true
puts valid_string?('[ ( text { ) } ]') == false   #=> true



The double use of key was very confusing.

This post has been edited by xclite: 29 January 2014 - 03:45 PM
Reason for edit:: Fixed some broke-ass code tags.

Was This Post Helpful? 0
  • +
  • -

#15 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3326
  • View blog
  • Posts: 11,246
  • Joined: 12-December 12

Re: try to understand matching brackets & evaluation.

Posted 29 January 2014 - 03:07 PM

Quote

The double use of key was very confusing.

Yes, that threw us all.

jon said:

One more thing that's not obvious: the result of the last evaluation is returned. This is not hugely weird, but it's certainly not obvious.

This is one thing that I really like, it's kinda cool ;). I think there are other languages that do this as well(?).




Quote

In Ruby only false and nil are falsey. Everything else is truthy (yes, even 0 is truthy).

from here

.. this must catch a lot of people out as well.

This post has been edited by andrewsw: 29 January 2014 - 03:08 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2