# Global token values
addop = 0
subop = 1
multop = 2
divop = 3
power = 4
l_par = 5
r_par = 6
assign = 7
ident = 8
number = 9
fname = 10
uminus = 11
eol = 12
space = 14
other = 15
''' This block defines a Stack class
Each instance is initialized with an
empty list. The class provides 5 methods:
push, pop, peek, clear, and display.
Daniel D. Warner
October 4, 2011
'''
class Stack:
def __init__(self):
self._s = []
def push(self,x):
self._s.append(x)
def pop(self):
if 0 < len(self._s):
return self._s.pop()
else:
return None
def peek(self):
if 0 < len(self._s):
return self._s[-1]
else:
return None
def depth(self):
return len(self._s)
def clear(self):
self._s = []
def display(self):
print self._s
import re
# Global regular expression pattern matchers
line_finder = re.compile(r'\S.*$',re.MULTILINE)
self_function = {}
self_function_parameter = {}
tok_finder = re.compile(r"""(?P<addop> [+] ) |
(?P<subop> [-] ) |
(?P<multop>[*] ) |
(?P<divop> [/] ) |
(?P<power> \^ ) |
(?P<l_par> \( ) |
(?P<r_par> \) ) |
(?P<assign>[=] ) |
(?P<ident>[a-zA-Z_]\w*) |
(?P<number>((\.\d+)|(\d+\.?\d*))([Ee][+-]?\d+)?) |
(?P<space> \s+ ) |
(?P<other> . )
""",re.VERBOSE)
# The numeric field for this incarnation of the Algebraic Calculator
MyFloat = RealField(53)
functions = {'abs':0, 'sqrt':1, 'exp':2, 'ln':3, 'cos':4, 'sin':5, 'tan':6, 'acos':7, 'asin':8, 'atan':9}
symbol_table = {}
# Global Operator Precedence Function based on the 13 tokens addop through eol
# addop multop power r_par ident fname eol
# subop divop l_par assign number uminus
OP_f = (('R', 'R', 'P', 'P', 'P', 'P', 'R', 'E', 'S', 'S', 'P', 'P', 'R'), # addop \
('R', 'R', 'P', 'P', 'P', 'P', 'R', 'E', 'S', 'S', 'P', 'P', 'R'), # subop \
('R', 'R', 'R', 'R', 'P', 'P', 'R', 'E', 'S', 'S', 'P', 'P', 'R'), # multop \
('R', 'R', 'R', 'R', 'P', 'P', 'R', 'E', 'S', 'S', 'P', 'P', 'R'), # divop \
('R', 'R', 'R', 'R', 'P', 'P', 'R', 'E', 'S', 'S', 'P', 'P', 'R'), # power \
('P', 'P', 'P', 'P', 'P', 'P', 'D', 'E', 'S', 'S', 'P', 'P', 'E'), # l_par \
('E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E'), # r_par \
('P', 'P', 'P', 'P', 'P', 'P', 'E', 'P', 'S', 'S', 'P', 'P', 'R'), # assign \
('E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E'), # ident \
('E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E'), # number \
('R', 'R', 'R', 'R', 'R', 'P', 'R', 'E', 'E', 'E', 'E', 'E', 'R'), # fname \
('R', 'R', 'R', 'R', 'R', 'P', 'R', 'E', 'S', 'S', 'P', 'P', 'R'), # uminus \
('P', 'P', 'P', 'P', 'P', 'P', 'E', 'P', 'S', 'S', 'P', 'P', 'F')) # eol
header = ''' addop multop power r_par ident fname eol
subop divop l_par assign number uminus'''
def get_tok(s):
pos = tok = 0
while 0<len(s):
m = tok_finder.match(s)
if m:
categories = m.groups()
# print categories
for k in range(other+1):
if categories[k]:
tok = k
break
start,pos = m.span()
val = s[start:pos]
s = s[pos:]
return (tok,val,s)
else:
print '***',s
return (None,None,'')
def lex(input):
statement_list = []
pos = 0
while pos<len(input):
m = line_finder.search(input,pos)
if m:
start,n = m.span()
s = input[start:n]
lex_list = []
while 0<len(s):
tok,val,s = get_tok(s)
if tok == space:
pass
elif tok == other:
print "*** Illegal character:",val," ignored ***"
elif tok == number:
# val = RDF(val) # Hardware double precision
val = MyFloat(val)
lex_list.append((tok,val))
elif tok == ident:
if val in functions.keys():
tok = fname
val = functions[val]
elif val in self_function.keys():
tok=fname
else:
if val not in symbol_table.keys():
symbol_table[val] = None
lex_list.append((tok,val))
elif tok == addop: # Check for unary addops and delete
if len(lex_list)==0:
pass
else:
ptok = lex_list[-1][0]
if (ptok!=r_par) and (ptok!=ident) and (ptok!=number):
pass
else:
lex_list.append((tok,val))
elif tok == subop: # Check for unary minus and convert to uminus
if len(lex_list)==0:
tok = uminus
else:
ptok = lex_list[-1][0]
if (ptok!=r_par) and (ptok!=ident) and (ptok!=number):
tok = uminus
lex_list.append((tok,val))
elif (tok == l_par) and (0<len(lex_list)):
ptok,pval = lex_list[-1]
if (ptok==r_par) or (ptok==ident) or (ptok==number):
print "*** Illegal syntax:",pval,val," ***"
lex_list.append((tok,val))
else:
lex_list.append((tok,val))
statement_list.append(lex_list)
pos = n
else:
#statement_list.append([])
break
return statement_list
# This block defines a Parser for standard algebraic formulas written with infix notation.
# It converts the infix formula to an algebraic formula containing variables, numbers,
# binary operators and unary operators written in Reverse Polish notation.
# The binary operators include: '+', '-', '*', '/', '^', and '='.
# The unary operators include the unary minus and the 10 elementary functions.
def RPN_Parser(input_list):
S = Stack()
input_list.append((12,'\n'))
S.push((12,'\n'))
output_list = []
while 0 < len(input_list):
keyi, itoken = input_list.pop(0)
keys, stoken = S.pop()
action = OP_f[keys][keyi]
if action == 'P': # Push
S.push((keys,stoken))
S.push((keyi,itoken))
elif action == 'R': # Reduce
output_list.append((keys,stoken))
input_list.insert(0,(keyi,itoken))
elif action == 'S': # Keep the stack the same
output_list.append((keyi,itoken))
S.push((keys,stoken))
elif action == 'D': # Discard the pair of parentheses
pass
elif action == 'F': # Finished
#print "bingo\n"
return output_list
else:
break # Error
# Error exit
return ['*** Error *** ',itoken, input_list]