source: TI02-CSML/branches/csml-cdms2/csmllibs/NumericTransform.py @ 3627

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/branches/csml-cdms2/csmllibs/NumericTransform.py@3627
Revision 3627, 5.7 KB checked in by spascoe, 12 years ago (diff)

This branch contains CSML converted to use cdat_lite-5.

  • convertcdms was run on the source
  • the MA.set_print_limit call was changed to the numpy equivilent
  • The tests were changed to account for the existence of numpy scalar types.

All tests, except the two known to fail, pass on i686 ubuntu.

  • Property svn:executable set to *
Line 
1#!/usr/bin/python
2# Adapted for numpy/ma/cdms2 by convertcdms.py
3# Author: Mark Henning <mhen@pml.ac.uk>
4#
5# A simple (and safe) floating point mathematical expression solver,
6# that can handle both infix and postfix (reverse polish) notation
7#
8# TODO: Currently quite intolerent of incorrect syntax.
9# TODO: Implementation of shunting yard too opaque. Possibly rewrite.
10#
11# Change History
12# 2007-05-04 mhen Modified to handle Numeric arrays
13
14from math import *
15import numpy.oldnumeric as Numeric
16import re
17
18# Symbol Table.
19# Functions:
20#   'args':    The number of arguments accepted by the function
21#   'def':     Function object. (*MUST* accept number of args specified in 'args')
22#
23# Additionaly, if function represents an infix operator, then the following must
24# be defined:
25#   'prec':    The operator precedence. Must be an integer.
26#   'assoc':   'yes' if the infix operator is associative. 'left' or right' if
27#              the operator is left or right non-associative.
28#
29# Constants can be defined as a function that takes no arguments.
30
31_symbols = {
32   # Operators:
33   '*': {'args':2, 'prec':5, 'assoc':'yes',  'def':lambda a,b: a*b },
34   '-': {'args':2, 'prec':0, 'assoc':'left', 'def':lambda a,b: a-b },
35   '/': {'args':2, 'prec':5, 'assoc':'left', 'def':lambda a,b: a/b },
36   '+': {'args':2, 'prec':0, 'assoc':'yes',  'def':lambda a,b: a+b },
37   '^': {'args':2, 'prec':9, 'assoc':'right','def':lambda a,b: a**b},
38   '%': {'args':2, 'prec':5, 'assoc':'left', 'def':lambda a,b: a%b },
39   # Functions:
40   'log':  {'args':2, 'def':lambda base,a: log(a,base) },
41   'sin':  {'args':1, 'def':lambda a: sin(a) },
42   'cos':  {'args':1, 'def':lambda a: cos(a) },
43   'tan':  {'args':1, 'def':lambda a: tan(a) },
44   'asin': {'args':1, 'def':lambda a: asin(a) },
45   'acos': {'args':1, 'def':lambda a: acos(a) },
46   'atan': {'args':1, 'def':lambda a: atan(a) },
47   'sqrt': {'args':1, 'def':lambda a: sqrt(a) },
48   'floor':{'args':1, 'def':lambda a: floor(a) },
49   'ceil': {'args':1, 'def':lambda a: ceil(a) },
50   'abs':  {'args':1, 'def':lambda a: fabs(a) },
51   # Constants:
52   'pi':   {'args':0, 'def':lambda: pi },
53   'e':    {'args':0, 'def':lambda: e }
54}
55
56#
57# Implementation of Dijkstra's Shunting Yard Algorithm to compile infix
58# notation into postfix (reverse polish) notation.
59#
60# TODO: This implementation is rather opaque. Possibly rewrite at some point.
61def dijkstraShuntingYard(tokens):
62   s = [] # The stack
63   q = [] # Output queue
64   for t in tokens:
65      if(isNumericString(t) or not (t in _symbols or t in ['(',',',')'])):
66         q.append(t) # Float literal or unknown symbolic token (assume var)
67      elif(t == '(' or (t in _symbols and 'prec' not in _symbols[t])):           
68         s.append(t) # Function, constant or left parenthesis token.
69      elif(t == ')' or t == ','): # right paren or func separator token.
70         while(len(s)>0 and s[len(s)-1] != '('):
71            q.append(s.pop())
72         if(len(s) == 0): raise SyntaxError("Could not parse expression.")
73         if(t == ')'):
74            s.pop()
75            if(len(s)>0 and s[len(s)-1] in _symbols and 'prec' not in _symbols[s[len(s)-1]]):
76               q.append(s.pop())
77      else: # Infix operator token.
78         modifier = 1
79         if(_symbols[t]['assoc'] == 'right'): modifier = 0
80         while(len(s)>0 and s[len(s)-1] in _symbols and 'prec' in _symbols[s[len(s)-1]] 
81               and _symbols[t]['prec'] < _symbols[s[len(s)-1]]['prec'] + modifier):
82            q.append(s.pop())
83         s.append(t)
84   while(len(s)>0):                   
85      t = s.pop()
86      if(t not in _symbols): raise SyntaxError("Could not parse expression.")
87      q.append(t)
88   return q
89
90# Return true if the string represents a floating point value.
91def isNumericString(candidate):
92   try: float(candidate)
93   except ValueError: return False
94   return True
95
96# Parse and evaluate postfix expressions
97class postfixExpression:
98   def __init__(self, expression):
99      self.tokens = expression.split()
100
101   # Solve the tokenised postfix expression stored in self.tokens and
102   # return the solution (or None if no solution could be found)
103   def solve(self, **variables):
104      self.stack = []
105      for token in self.tokens:
106         if token in variables:
107            self.stack.append(variables[token])
108         elif token in _symbols:
109            # Pop reqd. no. of args off stack and pass to function in symbol table,
110            # putting result back onto stack:
111            args = self.stack[-_symbols[token]['args']:]
112            self.stack = self.stack[0:-_symbols[token]['args']]
113            self.stack.append( _symbols[token]['def'](*args) )
114         else:
115            try: # Not in symbol tables, but it might be a numeric literal...
116               self.stack.append(float(token))
117            except ValueError: # Nope, not a literal.
118               raise NameError("Could not resolve symbol '"+token+"'.")
119      if(len(self.stack) == 1):
120         return self.stack[0]
121
122
123# Parse and evaluate infix expressions:
124class infixExpression(postfixExpression):
125   def __init__(self, expression):
126      infixTokens = re.findall("\s*([-0-9.]+|\w+|.)\s*", expression)
127      self.tokens = dijkstraShuntingYard(infixTokens)
128   
129
130# Regression Test:
131if __name__ == "__main__":
132   expression_str = " (10* (sqrt(16) + 3) - 20)*x/10^2+-0.42  "
133   print "Raw Expression:", expression_str
134   expression = infixExpression(expression_str)
135   print "Compiled (RPN) Expression:", expression.tokens
136   print "== Basic Tests: =="
137   print "  Solving for x=2, (Answer should be 0.58): ", expression.solve( x=2 )
138   print "  Solving for x=3, (Answer should be 1.08): ", expression.solve( x=3 )
139   print "== NumPy Tests: =="
140   print "  Solving for x=[2 3 4] (Answer should be [0.58 1.08 1.58]): ", expression.solve(x=Numeric.array((2,3,4)))
Note: See TracBrowser for help on using the repository browser.