After reading a portion of the book "The C# Programming Language: Third Edition," I found a section in the introduction that introduced abstract classes and methods that involved an example that included the concept of expression trees. The code was easy to implement since it just had to be copied out of the book. After playing around with the program a little and extending it, I thought that it would be fun to write a program in C# that could (interactively) evaluate expressions and display the results. Not knowing C# quite as well as Python led to the following program written and tested in Python 3.0 (not sure about previous languages).
The first section of the code includes port of the program from the aforementioned book along with extra code that allows for further features not originally included in the C# version. Those sections are clearly marked as being new code written by yours truly. The second area of the program has six functions that are profusely documented so as to explain how they go about parsing and processing expressions entered for evaluation. For those wishing to use the code, the "run" function should be all that you need. The final part of the module contains a test program that can be used to check the validity of the how well the program works.
The parser is not very complicated and will except expressions that are both normal to Python and completely illegal in Python. The main features are its ability to (1) identify simple assignment and mathematical operations, (2) identify constant floating point numbers, and (3) identify variables that would otherwise have no other meaning to the program. A limited number of error messages are given when appropriate but may leave one guessing what the problem really is. Mathematical operations are evaluated from left to right without regards to precedence, and assignment statements are evaluated from right to left.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 | class Expression:
def __init__(self):
raise NotImplementedError()
def Evaluate(self, dictionary):
raise NotImplementedError()
# NEW code
def __repr__(self):
klass = self.__class__.__name__
private = '_{0}__'.format(klass)
args = []
for name in self.__dict__:
if name.startswith(private):
value = self.__dict__[name]
name = name[len(private):]
args.append('{0}={1}'.format(name, repr(value)))
return '{0}({1})'.format(klass, ', '.join(args))
# END code
class Constant(Expression):
def __init__(self, value):
self.__value = value
def Evaluate(self, dictionary):
return self.__value
class Variable(Expression):
def __init__(self, name):
self.__name = name
def Evaluate(self, dictionary):
if self.__name not in dictionary:
raise Exception('Unknown variable: ' + self.__name)
return dictionary[self.__name]
class Operation(Expression):
def __init__(self, left, op, right):
self.__left = left
self.__op = op
self.__right = right
def Evaluate(self, dictionary):
# NEW code
if self.__op == '=':
assert isinstance(self.__left, Variable), 'Must Assign to Variable'
name = self.__left._Variable__name
value = self.__right.Evaluate(dictionary)
dictionary[name] = value
return value
# END code
x = self.__left.Evaluate(dictionary)
y = self.__right.Evaluate(dictionary)
if self.__op == '+':
return x + y
if self.__op == '-':
return x - y
if self.__op == '*':
return x * y
if self.__op == '/':
return x / y
# NEW code
if self.__op == '//':
return x // y
if self.__op == '\\':
return y / x
if self.__op == '%':
return x % y
if self.__op in ('**', '^'):
return x ** y
if self.__op in ('and', '&&', '&'):
return x and y
if self.__op in ('or', '||', '|'):
return x or y
if self.__op == '==':
return float(x == y)
if self.__op == '!=':
return float(x != y)
if self.__op == '>':
return float(x > y)
if self.__op == '<':
return float(x < y)
if self.__op in ('>=', '=>'):
return float(x >= y)
if self.__op in ('<=', '=<'):
return float(x <= y)
# END code
raise Exception('Unknown operator: ' + self.__op)
# NEW code
class Print(Expression):
def __init__(self, expression):
self.__expression = expression
def Evaluate(self, dictionary):
value = self.__expression.Evaluate(dictionary)
print(value)
return value
# END code
################################################################################
def run(string, local):
# fix string for compatibility on all computer platforms
string = string.replace('\r\n', '\n').replace('\r', '\n')
lines = tokenize(string)
build_operations(lines)
evaluate(lines, local)
def tokenize(string):
lines = []
# replace ';' with line separators
string = string.replace(';', '\n')
# the string will be evaluate line-by-line
for line in string.split('\n'):
tokens = []
# ignore empty lines and comments
if not line or line[0] == '#':
continue
# tokens are separated by white-space
for token in line.split():
# operations are processed later
if token in ('=', '+', '-', '*', '/', '//', '\\', '%',
'**', '^', 'and', '&&', '&', 'or', '||', '|',
'==', '!=', '>', '<', '>=', '=>', '<=', '=<'):
tokens.append(token)
else:
try:
# the token is a constant if it can be converted to a float
tokens.append(Constant(float(token)))
except:
# ... otherwise we assume that it is a variable
tokens.append(Variable(token))
lines.append(tokens)
return lines
def build_operations(lines):
# now we work on sorting through operations
for line_index, line in enumerate(lines):
# assignment is optional on a line
if '=' in line:
# split on '=' so each section can be processed
tokens = split(line)
# single variables must be on the left of '='
for section in tokens[:-1]:
assert len(section) == 1, 'Must Have Single Token'
assert isinstance(section[0], Variable), 'Must Assign to Variable'
# construct an operation from the last tokens
tokens[-1] = flatten(tokens[-1])
# create as many assignment operations as needed
op = Operation(tokens[-2][0], '=', tokens[-1])
for token_index in range(len(tokens) - 3, -1, -1):
op = Operation(tokens[token_index][0], '=', op)
# replace the line with the final operation
lines[line_index] = op
else:
# no assignment? assume evaluation and printing
op = flatten(line)
lines[line_index] = Print(op)
def split(line):
# split the tokens in the line on '='
tokens = []
while '=' in line:
index = line.index('=')
tokens.append(line[:index])
line = line[index+1:]
return tokens + [line]
def flatten(tokens):
# check for odd number of tokens
assert len(tokens) % 2 == 1, 'Must Have Odd Number of Tokens'
toggle = True
# check the token construction sequence
for token in tokens:
if toggle:
assert isinstance(token, (Constant, Variable)), 'Must Have Constant or Variable'
else:
assert isinstance(token, str), 'Must Have Operation'
toggle = not toggle
# if there is only one token, it does not need to be flattened
if len(tokens) == 1:
return tokens[0]
# construct the needed operations starting from the beginning
op = Operation(*tokens[:3])
for index in range(3, len(tokens), 2):
op = Operation(op, tokens[index], tokens[index+1])
return op
def evaluate(lines, local):
# evaluate the lines in order with the local dictionary
for line in lines:
local['_'] = line.Evaluate(local)
################################################################################
def test():
import sys
local = {}
while True:
try:
run(input('>>> '), local)
except EOFError:
return
except Exception as err:
sys.stderr.write(err.args[0] + '\n')
if __name__ == '__main__':
test()
|
The following is an example exchange with the program: