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

Revision 2452, 5.4 KB checked in by mggr, 14 years ago (diff)

initial version of PML methods (will need testing) - mggr checking in for mhen

• 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 re
12
13# Functions:
14#
15#   'args':    The number of arguments accepted by the function
16#   'def':     Function definition. Function must accept a list containing the
17#              arguments to the function
18#
19# Additionaly, if function represents an infix operator, then the following must
20# be defined:
21#
22#   'prec':    The operator precedence. Must be an integer.
23#   'assoc':   'yes' if the infix operator is associative. 'left' or right' if
24#              the operator is left or right non-associative.
25#
26# Constants can be defined as a function that takes no arguments.
27
28func = {
29   # Operators:
30   '*': {'args':2, 'prec':5, 'assoc':'yes',  'def':lambda arg:arg[0]*arg[1] },
31   '-': {'args':2, 'prec':0, 'assoc':'left', 'def':lambda arg:arg[0]-arg[1] },
32   '/': {'args':2, 'prec':5, 'assoc':'left', 'def':lambda arg:arg[0]/arg[1] },
33   '+': {'args':2, 'prec':0, 'assoc':'yes',  'def':lambda arg:arg[0]+arg[1] },
34   '^': {'args':2, 'prec':9, 'assoc':'right','def':lambda arg:arg[0]**arg[1]},
35   '%': {'args':2, 'prec':5, 'assoc':'left', 'def':lambda arg:arg[0]%arg[1] },
36   # Functions:
37   'log':  {'args':2, 'def':lambda arg: log(arg[1],arg[0]) },
38   'sin':  {'args':1, 'def':lambda arg: sin(arg[0]) },
39   'cos':  {'args':1, 'def':lambda arg: cos(arg[0]) },
40   'tan':  {'args':1, 'def':lambda arg: tan(arg[0]) },
41   'asin': {'args':1, 'def':lambda arg: asin(arg[0]) },
42   'acos': {'args':1, 'def':lambda arg: acos(arg[0]) },
43   'atan': {'args':1, 'def':lambda arg: atan(arg[0]) },
44   'sqrt': {'args':1, 'def':lambda arg: sqrt(arg[0]) },
45   'floor':{'args':1, 'def':lambda arg: floor(arg[0]) },
46   'ceil': {'args':1, 'def':lambda arg: ceil(arg[0]) },
47   'abs':  {'args':1, 'def':lambda arg: fabs(arg[0]) },
48   # Constants:
49   'pi':   {'args':0, 'def':lambda arg: pi },
50   'e':    {'args':0, 'def':lambda arg: e }
51}
52
53#
54# Implementation of Dijkstra's Shunting Yard Algorithm to compile infix
55# notation into postfix (reverse polish) notation.
56#
57# TODO: This implementation is rather opaque. Possibly rewrite at some point.
58def dijkstraShuntingYard(tokens):
59   s = [] # The stack
60   q = [] # Output queue
61   for t in tokens:
62      if(isNumericString(t) or not (t in func or t in ['(',',',')'])):
63         q.append(t) # Float literal or unknown symbolic token (assume var)
64      elif(t == '(' or (t in func and 'prec' not in func[t])):
65         s.append(t) # Function, constant or left parenthesis token.
66      elif(t == ')' or t == ','):
67         while(len(s)>0 and s[len(s)-1] != '('):
68            q.append(s.pop())
69         if(len(s) == 0): raise SyntaxError("Could not parse expression.")
70         if(t == ')'):
71            s.pop()
72            if(len(s)>0 and s[len(s)-1] in func and 'prec' not in func[s[len(s)-1]]):
73               q.append(s.pop())
74      else: # Infix operator token.
75         modifier = 1
76         if(func[t]['assoc'] == 'right'): modifier = 0
77         while(len(s)>0 and s[len(s)-1] in func and 'prec' in func[s[len(s)-1]]
78               and func[t]['prec'] < func[s[len(s)-1]]['prec'] + modifier):
79            q.append(s.pop())
80         s.append(t)
81   while(len(s)>0):
82      t = s.pop()
83      if(t not in func): raise SyntaxError("Could not parse expression.")
84      q.append(t)
85   return q
86
87# Return true if the string represents a floating point value.
88def isNumericString(candidate):
89   try: float(candidate)
90   except: return False
91   return True
92
93# Parse and evaluate postfix expressions
94class postfixExpression:
95   def __init__(self, expression):
96      self.tokens = expression.split()
97
98   # Solve the tokenised postfix expression stored in self.tokens list and
99   # return the solution (or None if no solution could be found)
100   def solve(self, **variables):
101      self.stack = []
102      for token in self.tokens:
103         if(isNumericString(token)):       # Token is a numeric literal
104            self.stack.append(float(token))
105         elif(token in variables):           # Token is in variables dictionary
106            self.stack.append(float(variables[token]))
107         elif(token in func):                # Token is a builtin function.
108            fargs = self.pop(func[token]['args'])
109            self.stack.append( func[token]['def'](fargs) )
110         else:
111            raise NameError("Could not resolve symbol '"+token+"'.")
112      if(len(self.stack) == 1):
113         return self.stack[0]
114
115   # Method to pop multiple values of the stack. Returns a list
116   def pop(self, num):
117      popped = []
118      for n in range(num):
119         popped.insert(0, self.stack.pop())
120      return popped
121
122# Parse and evaluate infix expressions:
123class infixExpression(postfixExpression):
124   def __init__(self, expression):
125      infixTokens = re.findall("\s*([-0-9.]+|\w+|.)\s*", expression)
126      self.tokens = dijkstraShuntingYard(infixTokens)
127
128
129# Test:
130if __name__ == "__main__":
131   expression_str = " (10* (sqrt(16) + 3) - 20)*x/10^2+-0.42  "
132   print "Expression:", expression_str
133   expression = infixExpression(expression_str)
134   print "Tokenised and compiled to RPN:", expression.tokens
135   print "Solving for x=2, (Answer should be 0.58): ", expression.solve( x=2 )
136   print "Solving for x=3, (Answer should be 1.08): ", expression.solve( x=3 )
Note: See TracBrowser for help on using the repository browser.