Re: Suggested Extension to Euphoria

new topic     » goto parent     » topic index » view thread      » older message » newer message

>>    En passant: What is the best way to implement a stack or a queue
>>                structure in Euphoria?

I'm not sure that you should ever ask the "best" way to code something. ;)


You probably want to wrap the stack or queue in a function. push() is easy:

   function push( object d )
      -- push d onto stack s, returning new stack
      return append( stack, d )
   end function


The problem with the stack is that pop() alters the stack, and returns a
value. You can handle it by passing two values back, such as:


   function pop( sequence s )
      -- pop stack, no error checking
      return {s[length(s)], s[1..length(s)-1]
   end function

Then you have to parse it into something like:

   stack = push( stack, 12 )
   s = pop( stack )
   val = s[1]
   stack = s[2]


Personanlly, i *hate* code like this. It makes me wish Euphoria had compound
assignment, like ABC and Python:

   val, stack = pop( stack )

but we don't.. :(  so:

If you are lazy, you can make the stack variable a module level variable,
and have a 'push' and 'pop' function:

   -- declare the stack
   sequence stack
   stack = {}

   procedure push( object d )
      -- push d onto stack s
      stack = append( stack, d )
   end procedure

   function pop()
      -- return top of stack, popping item off stack
      object d
      if length( stack ) = 0 then
         -- can't pop empty stack
         puts( 1, "Stack Underflow!\n" )
         abort( 0 )
      else
         -- pop stack
         d = stack[length(stack)]
         stack = stack[1..length(stack)-1]
      end if
      return d
   end if

You can just call it in code like:

   push( 23 )
   push( 3 )
   push( "+" )
   x = pop()

Much cleaner looking, no?

Another aside: wouldn't the pop function look better if we could write:

   function pop()
      -- return top of stack, popping item off stack
      object d
      if length( stack ) = 0 then
         -- can't pop empty stack
         puts( 1, "Stack Underflow!\n" )
         abort( 0 )
      else
         -- pop stack
         d = stack[end]
         stack = stack[1..end-1]
      end if
      return d
   end if

If you have multiple stacks and you want to still use this method, just set
up a sequence of stacks, and pass the index:

   -- example of multiple stacks
   sequence sos          -- stack of stacks
   sos = repeat( {}, 100 )    -- set up 100 stacks
   constant    dataStack = 1, -- hold data
          opStack   = 2  -- hold operators

   procedure push( integer i, object d )
      -- push d onto stack sos[i]
      return sos[i] = ( sos[i], d )
   end procedure

   function pop( integer i )
      -- return top of stack s[i], popping item off stack
      object d
      if length( sos[i] ) = 0 then
         -- can't pop empty stack
         puts( 1, "Stack Underflow!\n" )
         abort( 0 )
      else
         -- pop stack
         d = sos[i][length(sos[i])]
         sos[i] = sos[i][1..length(sos[i])-1]
      end if
      return d
   end if

   -- example of use
   push( dataStack, 1 )
   push( opStack, "+" )
   push( dataStack, 2 )
   x = pop( opStack )

Queues are pretty much the same thing. I haven't bothered to debug any of
the above code (not that you'd really want to use it).

 -- David Cuny

new topic     » goto parent     » topic index » view thread      » older message » newer message

Search



Quick Links

User menu

Not signed in.

Misc Menu