Class: SimpleExpression

Inherits:
Object
  • Object
show all
Defined in:
lib/expressionparser.rb,
lib/simpleexpression.rb

Constant Summary collapse

NUMBER_REGEXP = 
/^([-+0-9.]+(e[-+]?[0-9]+)?)(.*)$/
OPERATORS = 
"-+/*()[]{}^"
OPERATOR_REGEXP = 
Regexp.new("[#{Regexp.escape(OPERATORS)}]")
FUNCLIST = 
["sin", "cos", "tan"]
PAREN_LIST = 
["(", "[", "{"]

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(arg) ⇒ SimpleExpression

Returns a new instance of SimpleExpression.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
# File 'lib/simpleexpression.rb', line 14

def initialize(arg)
  if arg.kind_of?(String)
    @expression = arg
    arg = expression_from_string(arg)
  else
    @expression = "(not given)"
  end

  @parse_tree = arg
  @variables = SimpleExpression.vars_from_parse_tree(@parse_tree)

  @constant = false
  if @variables.empty?
    @constant = true
  end
end

Class Method Details

.full_grouping_pass(tokens, grouptestproc, tokenchangeproc, indexchangeproc = lambda { |tokens, index| index + 1 }) ⇒ Object

The full_grouping_pass function iterates over the entire parse tree, examining unparsed sections and testing (with grouptestproc) to see if they can be partially parsed. If so, tokenchangeproc is used to determine the new token string after replacement.



226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/expressionparser.rb', line 226

def self.full_grouping_pass(tokens, grouptestproc, tokenchangeproc,
        indexchangeproc = lambda { |tokens, index| index + 1 } )
  return [] if tokens.nil? or tokens.empty?

  finaltokens = grouping_iter(tokens, &lambda { |tokens|
    return [] if tokens == []
    return tokens if parsed?(tokens)

    newtokens = [ ]
    index = 0

    while index < tokens.length
	if grouptestproc.call(tokens, index)
 newtokens = tokenchangeproc.call(tokens, newtokens, index)
 index = indexchangeproc.call(tokens, index)
	else
 newtokens += [ tokens[index] ]
	end

	index += 1
    end

    newtokens
  }) # end lambda and function call

  finaltokens
end

.fully_parsed?(tree) ⇒ Boolean

Returns:

  • (Boolean) 


402
403
404
405
 
# File 'lib/expressionparser.rb', line 402

def self.fully_parsed?(tree)
  parsed?(tree) and
    tree.select{|item| item.kind_of?(Array) }.all?{|arr| fully_parsed?(arr)}
end

.function?(string) ⇒ Boolean

Returns:

  • (Boolean) 


87
88
89
 
# File 'lib/expressionparser.rb', line 87

def self.function?(string)
  FUNCLIST.include?(string)
end

.group_functions(tokens, funclist, parenlist) ⇒ Object 



308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'lib/expressionparser.rb', line 308

def self.group_functions(tokens, funclist, parenlist)
  full_grouping_pass(tokens,
       # test if we should group as function
       proc { |tokens, index|
	 return false if index == (tokens.length - 1)
	 function?(tokens[index]) and
	   tokens[index+1].kind_of?(Array) and
	   parenlist.include?(tokens[index + 1][0])
       },
       proc { |tokens, newtokens, index|
	 newtokens + [ EPNode.new([ tokens[index],
				    tokens[index + 1] ]) ]
       })
end

.group_left_right(tokens, oplist) ⇒ Object 



375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/expressionparser.rb', line 375

def self.group_left_right(tokens, oplist)
  full_grouping_pass(tokens,
       # test if we should group around a binary op
       proc { |tokens, index|
	 return false if index == 0
	 return false if index == (tokens.length - 1)
	 oplist.include?(tokens[index]) and
	   operand?(tokens[index-1]) and
	   operand?(tokens[index + 1])
       },
       proc { |tokens, newtokens, index|
	 popped_token = newtokens[-1]
	 newtokens = newtokens[0..-2]
	 newtokens + [ EPNode.new([ tokens[index],
				    popped_token,
				    tokens[index+1] ]) ]
       })
end

.group_operands(tokens) ⇒ Object 



338
339
340
341
342
343
344
345
346
347
348
349
350
 
# File 'lib/expressionparser.rb', line 338

def self.group_operands(tokens)
  full_grouping_pass(tokens,
       # test if we should group two terms adjacent
       proc { |tokens, index|
	 return false if index == (tokens.length - 1)
	 operand?(tokens[index]) and
	   operand?(tokens[index + 1])
       },
       proc { |tokens, newtokens, index|
	 newtokens + [ EPNode.new([ "*", tokens[index],
				    tokens[index + 1] ]) ]
       })
end

.group_parens(tokens, open_paren, close_paren) ⇒ Object 



254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
 
# File 'lib/expressionparser.rb', line 254

def self.group_parens(tokens, open_paren, close_paren)
  group_stack = []
  savedindex = -1
  savedtokens = nil

  newtokens = full_grouping_pass(tokens,
       proc { |tokens, index|
	 if savedindex >= index and group_stack != []
	   raise "Unmatched '#{open_paren}' in '#{tokens}' " +
	     "in group_parens!"
	 end
	 savedindex = index

	 return true if tokens[index] == open_paren
	 return true if tokens[index] == close_paren
	 false
       },
       proc { |tokens, newtokens, index|
	 if tokens[index] == open_paren
	   group_stack += [ newtokens ]
	   return []
	 end
	 if tokens[index] == close_paren
	   if group_stack == []
	     raise "Unmatched '#{close_paren}' parsing " +
	       "'#{tokens}' in group_parens!"
	   end
	   rettokens = group_stack[-1] +
	     [ EPNode.new([open_paren] + [ newtokens ]) ]
	   group_stack = group_stack[0..-2]

	   rettokens
	 end
       },
       proc { |tokens, index| index }
  )  # end full_grouping_pass()

  if group_stack != []
    raise "Unmatched '#{open_paren}' in '#{tokens}' in group_parens!\n"
  end

  newtokens
end

.group_right_left(tokens, oplist) ⇒ Object 



358
359
360
361
362
363
364
365
366
 
# File 'lib/expressionparser.rb', line 358

def self.group_right_left(tokens, oplist)
  return [] if tokens.nil? or tokens.empty?

  newtokens = parse_tree_reverse(tokens, oplist)

  grouped_tokens = group_left_right(newtokens, oplist)

  finaltokens = parse_tree_reverse(grouped_tokens, oplist)
end

.group_unary(tokens, oplist) ⇒ Object 



323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'lib/expressionparser.rb', line 323

def self.group_unary(tokens, oplist)
  full_grouping_pass(tokens,
       # test if we should group unary minus or plus
       proc { |tokens, index|
	 return false if index == (tokens.length - 1)
	 oplist.include?(tokens[index]) and
	   operand?(tokens[index + 1]) and
	   (index == 0 or not operand?(tokens[index - 1]))
       },
       proc { |tokens, newtokens, index|
	 newtokens + [ EPNode.new([ tokens[index],
				    tokens[index + 1] ]) ]
       })
end

.grouping_iter(tokens, &myproc) ⇒ Object

If the argument is an array containing arrays, this will call the function in question (which takes and returns an array) on each subarray, then on the top-level array with the replaced subarrays.



195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/expressionparser.rb', line 195

def self.grouping_iter(tokens, &myproc)
  return [] if tokens.nil? or tokens.empty?
  tokenclass = tokens.class

  newtokens = tokens.collect do |token|
    token.kind_of?(Array) ? grouping_iter(token, &myproc) : token
  end

  # Preserve EPNode-ness
  tokenclass.new(myproc.call(tokenclass.new(newtokens)))
end

.legal_variable_name?(name) ⇒ Boolean

Returns:

  • (Boolean) 


58
59
60
61
 
# File 'lib/simpleexpression.rb', line 58

def self.legal_variable_name?(name)
  return true if (name =~ /^([_A-Za-z][_A-Za-z0-9]*)$/)
  false
end

.number?(quantity) ⇒ Boolean

Returns:

  • (Boolean) 


76
77
78
79
80
81
 
# File 'lib/expressionparser.rb', line 76

def self.number?(quantity)
  return true if quantity.kind_of?(Float)
  return true if quantity.kind_of?(Fixnum)
  return true if quantity.kind_of?(Bignum)
  false
end

.operand?(token) ⇒ Boolean

Returns:

  • (Boolean) 


368
369
370
371
372
373
 
# File 'lib/expressionparser.rb', line 368

def self.operand?(token)
  token.kind_of?(Array) or
    SimpleExpression.number?(token) or
    (SimpleExpression.legal_variable_name?(token) and
     not SimpleExpression.function?(token))
end

.operator?(string) ⇒ Boolean

Returns:

  • (Boolean) 


83
84
85
 
# File 'lib/expressionparser.rb', line 83

def self.operator?(string)
  (string =~ OPERATOR_REGEXP) ? true : false
end

.parse_tree_reverse(tokens, oplist) ⇒ Object 



352
353
354
355
356
 
# File 'lib/expressionparser.rb', line 352

def self.parse_tree_reverse(tokens, oplist)
  grouping_iter(tokens) do |list|
    operator?(list[0]) ? [ list[0] ] + list[1..-1].reverse : list.reverse()
  end
end

.parsed?(tokens) ⇒ Boolean

Returns:

  • (Boolean) 


394
395
396
397
398
399
400
 
# File 'lib/expressionparser.rb', line 394

def self.parsed?(tokens)
  return true if tokens.nil? or tokens.empty?
  return true if tokens.length == 1
  return true if tokens.kind_of?(EPNode)

  false
end

.token_iter(tokens) ⇒ Object

Iterate over every token, changing nothing and returning nil.



209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/expressionparser.rb', line 209

def self.token_iter(tokens)
  return if tokens.nil? or tokens.empty?

  grouping_iter(tokens) do |tokens|
    tokens.each do |token|
	yield(token)
    end
  end

  nil
end

.tokenize(expression) ⇒ Object 



135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'lib/expressionparser.rb', line 135

def self.tokenize(expression)
  tokenlist = []
  current = ""

  raise "Not a string!" unless expression.kind_of?(String)

  if not expression or expression == ""
    return []
  end

  while expression != ""
    # Cut out whitespace
    if /\s/.match(expression[0..0])
	expression.sub!(/^\s+/, "")
	next
    end

    # Grab a variable name
    if expression[0..0] =~ /[A-Za-z]/
	matchobj = /^([A-Za-z][-_A-Za-z0-9]*)(.*)$/.match(expression)

	raise "Can't parse variable name in expression!" unless matchobj
	unless SimpleExpression.legal_variable_name?(matchobj[1])
 raise "Illegal var name"
	end

	tokenlist += [ matchobj[1] ]
	expression = matchobj[2]
	next
    end

    # Grab an operator symbol
    if expression[0..0] =~ OPERATOR_REGEXP
	tokenlist += [ expression[0..0] ]
	expression = expression [1, expression.size]
	next
    end

    # Grab a number
    if expression[0..0] =~ /[-+0-9.]/
	matchobj = NUMBER_REGEXP.match(expression)
	unless matchobj
 raise "Can't parse number in expression!"
	end
	num = matchobj[1].to_f()
	tokenlist += [ num ]
	expression = matchobj[3]
	next
    end

    raise "Untokenizable expression '#{expression}'!\n"
  end

  tokenlist
end

.unwrap_parens(tokens, paren_list) ⇒ Object 



298
299
300
301
302
303
304
305
306
 
# File 'lib/expressionparser.rb', line 298

def self.unwrap_parens(tokens, paren_list)
  grouping_iter(tokens) do |tokens|
    if tokens.length > 1 and paren_list.include?(tokens[0])
	[ tokens[0] ] + tokens[1]
    else
	tokens
    end
  end
end

.vars_from_parse_tree(tree) ⇒ Object 



91
92
93
94
95
96
97
98
99
100
 
# File 'lib/expressionparser.rb', line 91

def self.vars_from_parse_tree(tree)
  var_table = {}

  token_iter(tree) do |item|
    var_table[item] = 1 if SimpleExpression.legal_variable_name?(item) and
      not SimpleExpression.function?(item)
  end

  return var_table.keys
end

Instance Method Details

#constant? ⇒ Boolean

Returns:

  • (Boolean) 


71
72
73
 
# File 'lib/simpleexpression.rb', line 71

def constant?()
  return @constant
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/simpleexpression.rb', line 63

def empty?()
  not @parse_tree
end

#evaluate(vars = {}) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/simpleexpression.rb', line 31

def evaluate(vars={})
  if (vars == nil or vars == {}) and not @constant
    raise "Must pass variables to evaluate non-constant expression!"
  end
  vars = {} if vars.nil?

  vars_keys = vars.keys
  @variables.each do |key|
    raise "No value for var #{key}!" unless vars.include?(key)
  end

  return @parse_tree if SimpleExpression.number?(@parse_tree)

  raise "Not a parse tree!" unless @parse_tree.kind_of?(EPNode)

  @parse_tree.eval(vars)
end

#expression_from_string(string) ⇒ Object 



102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/expressionparser.rb', line 102

def expression_from_string(string)
  raise "Not a string!" unless string.kind_of?(String)

  tokens = SimpleExpression.tokenize(string)

  tokens = SimpleExpression.group_parens(tokens, "(", ")")
  tokens = SimpleExpression.group_parens(tokens, "[", "]")
  tokens = SimpleExpression.group_parens(tokens, "{", "}")

  tokens = SimpleExpression.group_functions(tokens, FUNCLIST,
			      PAREN_LIST)
  tokens = SimpleExpression.group_right_left(tokens, ["^"])
  tokens = SimpleExpression.group_unary(tokens, ["-", "+"])
  tokens = SimpleExpression.group_operands(tokens)
  tokens = SimpleExpression.group_left_right(tokens, ["*", "/"])
  tokens = SimpleExpression.group_left_right(tokens, ["+", "-"])
  tokens = SimpleExpression.unwrap_parens(tokens, PAREN_LIST)

  # If the outer layer is a single element array around an array,
  # upwrap it.
  if tokens.kind_of?(Array) and tokens.length == 1 and
	tokens[0].kind_of?(Array)
    tokens = tokens[0]
  end

  #print "+++ Parsed: #{pretty_print_parse_tree(tokens)}\n"

  raise "Can't completely parse expression '#{string}'!" unless
    SimpleExpression.fully_parsed?(tokens)

  tokens
end

#get_parse_tree ⇒ Object 



54
55
56
 
# File 'lib/simpleexpression.rb', line 54

def get_parse_tree()
  return @parse_tree.dup  # copy parse tree so it can't be changed
end

#optimize(vars = {}) ⇒ Object 



49
50
51
52
 
# File 'lib/simpleexpression.rb', line 49

def optimize(vars={})
  opt_tree = @parse_tree.optimize(vars)
  SimpleExpression.new(opt_tree)
end

#variables ⇒ Object 



67
68
69
 
# File 'lib/simpleexpression.rb', line 67

def variables()
  return @variables
end