source: TI02-CSML/branches/csml-pml/csmllibs/NumericTransform.py @ 2460

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/branches/csml-pml/csmllibs/NumericTransform.py@2460
Revision 2460, 5.5 KB checked in by mggr, 13 years ago (diff)

(mggr committing for mhen): ongoing development

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