Anonymous user
Arithmetic evaluation: Difference between revisions
→{{header|Prolog}}: Python added
(Undo revision 17565 by 87.117.229.252 (Talk): The task explicitly demands construction of an AST!) |
(→{{header|Prolog}}: Python added) |
||
Line 1,176:
% Example use
% calculator("(3+50)*7-9", X).
=={{header|Python}}==
There are python modules, such as Ply, which facilitate the implementation of parsers. This example, however, uses only standard Python with the parser having
two stacks, one for operators, one for operands.
<Python>import operator
class AstNode(object):
def __init__( self, opr, left, right ):
self.opr = opr
self.l = left
self.r = right
def eval(self):
return self.opr(self.l.eval(), self.r.eval())
class EP(object):
def __init__( self, valStrg ):
self.v = int(valStrg)
def eval(self):
return self.v
class Yaccer(object):
def __init__(self):
self.operstak = []
self.nodestak =[]
self.__dict__.update(self.state1)
def v1( self, valStrg ):
# Value String
self.nodestak.append( EP(valStrg))
self.__dict__.update(self.state2)
# print 'push', valStrg
def o1( self, operchar ):
# Operator character
print 'parse error: near operator %s' % operchar
def po1( self, operchar ):
# Open Parenthesis
def openParen(a,b):
return 0 # function should not be called
# hide precidence level of previous operator
self.operstak.append( (openParen, 0) )
self.__dict__.update(self.state1)
def pc1( self,operchar ):
# Close Parenthesis
print 'parse error - near operator ")"'
def v2( self, valStrg ):
# Value String
print 'parse error - near %s ' % valStrg
self.topValue = EP(valStrg)
def o2( self, operchar ):
# Operator character
opDict= { '+': ( operator.add, 1 ),
'-': (operator.sub, 1 ),
'*': (operator.mul, 2 ),
'/': (operator.div, 2 ),
}
operPrec = opDict[operchar][1]
while len(self.operstak)>0:
tailOper = self.operstak[len(self.operstak)-1]
if tailOper[1] < operPrec: break
self.redeuce()
self.operstak.append(opDict[operchar])
self.__dict__.update(self.state1)
# print 'pushop', operchar
def po2(self, char ):
# Open Parenthesis
print 'parse error - near operator "("'
def pc2( self,operchar ):
# Close Parenthesis
# reduce node until matching open paren found
while len(self.operstak)>0:
tailOper = self.operstak[len(self.operstak)-1]
if tailOper[1] == 0: break
self.redeuce()
if len(self.operstak)>0:
self.operstak.pop() # pop off open parenthesis
else:
print 'Error - no open parenthesis matches close parens.'
self.__dict__.update(self.state2)
def end(self):
while len(self.operstak)>0:
self.redeuce()
return self.nodestak.pop()
def redeuce(self):
tailOper = self.operstak.pop()
vrgt = self.nodestak.pop()
vlft= self.nodestak.pop()
self.nodestak.append( AstNode(tailOper[0], vlft, vrgt))
# print 'reduce'
state1 = { 'v': v1, 'o':o1, 'po':po1, 'pc':pc1 }
state2 = { 'v': v2, 'o':o2, 'po':po2, 'pc':pc2 }
def Lex( exprssn, p ):
bgn = None
cp = -1
for c in exprssn:
cp += 1
if c in '+-/*()':
if bgn is not None:
p.v(p, exprssn[bgn:cp])
bgn = None
if c=='(': p.po(p, c)
elif c==')':p.pc(p, c)
else: p.o(p, c)
elif c in ' \t':
if bgn is not None:
p.v(p, exprssn[bgn:cp])
bgn = None
elif c in '0123456789':
if bgn is None:
bgn = cp
else:
print 'Invalid character in expression'
if bgn is not None:
p.v(p, exprssn[bgn:cp])
bgn = None
if bgn is not None:
p.v(p, exprssn[bgn:cp+1])
bgn = None
return p.end()
expr = raw_input("Expression:")
astTree = Lex( expr, Yaccer())
print expr, '=',astTree.eval()</Python>
| |||