Most efficient way to process arguments from the command-line in prefix notation

Question

Hello,

our homework is to write a ruby script who calculate a subset of wordlist depending on the expression.

regular binary operations are

&& And operator
|| Or operator
++ Concatenate operator
! Negation operator

A valid call would be like

./eval.rb wordlist && a c
or
./eval.rb wordlist && || a b c

First call means generate a new wordlist which all words have at least one 'a' and 'c'. So my question is how do I process the arguemnts in a efficent way? Maybe recursiv? I'm stuck...

Thanks in advance.

Answer 1

Use a stack. The max size would be the number of arguments.

Answer 2

Looks like a grammer with prefix notation. A stack is indeed your friend, and the easiest stack to use is the call stack. For example, given this grammar:

expression ::= number | operand number number
operand ::= '+' | '-'

This is the code to evaluate it:

#!/usr/bin/ruby1.8

@tokens = ['*', 2, '+', 3, 4]

def evaluate
  token = @tokens.shift    # Remove first token from @tokens
  case token
  when '*'
    return evaluate * evaluate
  when '+'
    return evaluate + evaluate
  else
    return token
  end
end

puts evaluate    # => 14

Although this is Ruby, it's close enough to pseudo-code. I've put explicit returns in, although Ruby does not require them, because it may be clearer to someone who does not know Ruby.