Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 214 lines
  1
  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()

1 comment

Stephen Chappell (author) 12 years, 6 months ago  # | flag

The following is an example exchange with the program:

>>> a = 1
>>> b = 2
>>> c = 3
>>> a + b
3.0
>>> _ + c
6.0
>>> _ / 2 - c
0.0
>>> 2
2.0
>>> _ * _
4.0
>>> _ * _
16.0
>>> _ * _
256.0