# Evaluating arithmetic expressions

I have written some simple code for evaluating expressions. However, I am not sure how well I am following conventions (this is my first time trying to).

Specs for problem:

• All binary operators (+, -, *, /), no unary - or +
• Uses PEMDAS

My code is:

import re
import time
DIGITS = '0123456789'
OPS = '+-*/^'
OP_FUNCS = {
'+':lambda x, y:x + y,
'-':lambda x, y:x - y,
'*':lambda x, y:x * y,
'/':lambda x, y:x / y,
'^':lambda x, y:x ** y,
}
ORDER_OF_OPERATIONS = [
['^'],
['*', '/'],
['+', '-'],
]
VALID_PAIRS = [
('NUM', 'OP'),
('OP', 'NUM'),
('OP', 'OPAREN'),
('CPAREN', 'OP'),
('OPAREN', 'NUM'),
('NUM', 'CPAREN'),
('OPAREN', 'OPAREN'),
('CPAREN', 'CPAREN'),
]
NUM_MATCH = re.compile(
'(?:[1-9][0-9]*|0)'
'(?:[.][0-9]+)?'
)
class Token():  #This is not really useful but tuples could be less clear
def __init__(self, type_, info=None):
self.type = type_
self.info = info
#    def __str__(self):
#        return '{}:{}'.format(self.type, self.info)
PLACEHOLDER = Token('PLACEHOLDER')
def tokenize(expr):
tokens = []
index = 0
while index<len(expr):
curr_and_after = expr[index:]
is_num = NUM_MATCH.match(curr_and_after)
if expr[index] in OPS:
tokens.append(Token('OP', expr[index]))
elif is_num:
num = is_num.group(0)
tokens.append(Token('NUM', float(num)))
length = len(num)
index += length-1
elif expr[index] == '(':
tokens.append(Token('OPAREN'))
elif expr[index] == ')':
tokens.append(Token('CPAREN'))
elif expr[index] == ' ':
pass
else:
raise SyntaxError('Invalid character')
index += 1
return tokens
def is_valid(tokens):
if tokens == []:
return False

#This sections tests if parentheses are correctly nested
nesting = 0
for token in tokens:
if token.type == 'OPAREN':
nesting += 1
elif token.type == 'CPAREN':
nesting -= 1
if nesting<0:
return False
if nesting != 0:
return False

for index, _ in enumerate(tokens[:-1]):
#[:-1] because otherwise next wont exist on last token
curr, next_ = tokens[index], tokens[index+1]
curr_kind, next_kind = curr.type, next_.type
possible_valid_pairs = []
for valid_pair in VALID_PAIRS:
possible_valid_pairs.append((curr_kind, next_kind) == valid_pair)
#Test if it's equal to a valid pair
if not any(possible_valid_pairs):
return False

return True

def to_nested(tokens):
assert(is_valid(tokens))
out = []
index = 0
while index<len(tokens):
if tokens[index].type == 'OPAREN':
nesting = 1
in_parens = []
while nesting:
index += 1
if tokens[index].type == 'OPAREN':
nesting += 1
elif tokens[index].type == 'CPAREN':
nesting -= 1
in_parens.append(tokens[index])
in_parens=in_parens[:-1]  #Remove final closing paren
out.append(in_parens)
else:
out.append(tokens[index])
index += 1
return out
def has_op(tokens, op):
return any([token.type == 'OP' and token.info == op for token in tokens])
def eval_tokens(tokens):
newTokens = []
for item in tokens:
if type(item) == list:
#Parenthesised expressions are lists of tokens
newTokens.append(Token('NUM', eval_tokens(item)))
else:
newTokens.append(item)
tokens = newTokens
for ops_to_evaluate in ORDER_OF_OPERATIONS:
newTokens = []
while any([has_op(tokens, op) for op in ops_to_evaluate]):
#While any of the ops exists in the expression
for index, token in enumerate(tokens):
if token.type == 'OP' and token.info in ops_to_evaluate:
where = index
func = OP_FUNCS[token.info] #Get a function for the operation
break
fst, snd = tokens[where-1].info, tokens[where+1].info
before, after = tokens[:where-1], tokens[where+2:]
result = Token('NUM', func(fst, snd))
tokens = before+[result]+after  #Recombine everything
assert(len(tokens) == 1)  #Should always be true but for debugging it's useful
assert(tokens[0].type == 'NUM')
return tokens[0].info
def eval_expr(expr):
tokens = tokenize(expr)
nested = to_nested(tokens)
return eval_tokens(nested)
def main():
print(eval_expr(input('Enter an arithmetic expression: ')))
if __name__ == "__main__":
main()


## Spacing

I'd like to see some more blank lines. They help separate code into blocks. Without a blank line here and there, the code looks like a wall of text. As someone who answers questions on Stack Overflow, I can tell you a wall of text is hard to read; I usually just skip such questions. Of course, someone reading your source code may be forced not to skip it, but you want to make it easy.

## Documentation

Your code is well-organized and clear. With the comments in addition, I can almost forgive the lack of doc strings, yet doc strings are used for more than just the people who read the source code itself. Bots such as pydoc read it too for generating documentation. The comments are no replacement for that. Each function's purpose should be clear without the doc strings, but documentation takes out the guesswork.

## operator

I'm glad you're using a dictionary for OP_FUNCS, but you don't need to define your own functions. Python has a built-in module for that sort of thing: operator. You can use it like this:

import operator

OP_FUNCS = {
'+': operator.add,
'-': operator.sub,
'*': operator.mul,
'/': operator.truediv,
'^': operator.pow,
}


If you take a look through that module's documentation, maybe you'll be inspired to add more operators. It's very easy when the functions are already defined for you; you just need to figure out a symbol for it and its place in the order of operations.

## Generators

You should use generators more often. They are more memory-efficient than lists because each value is generated on the fly instead of needing to remember them all at once.

This is especially useful in has_op(), for example. All you need to do is remove the opening and closing brackets. That changes to using a generator expression instead of a list comprehension. Let's say the first item in tokens is a match. If you use a generator expression, any() will return True right away, and none of the other tokens is even checked. When you use a list comprehension, any() doesn't start to do anything until all tokens have been processed.

It is also useful in eval_tokens when you are using has_op. In short, it is rare indeed if a list comprehension is to be preferred over a generator expression when using any().

You have other functions that might work nicely as generator functions, except that the functions using them all require them to be lists, so that would mean that they would need to use the list function. It might still be a good idea, but it isn't a clear advantage.

## Miscellaneous

num = is_num.group(0)
...
length = len(num)
index += length-1


The match object has methods for finding the edges of a match. Since you're using .match(), the match is guaranteed to begin at the start of the string, so you can use simply .end():

index += num.end() - 1

if tokens == []:
return False


Instead of creating a blank list to compare to, use the list's boolean value:

if not tokens:
return False


This will now work even if tokens is a blank tuple, for example.

possible_valid_pairs = []
for valid_pair in VALID_PAIRS:
possible_valid_pairs.append((curr_kind, next_kind) == valid_pair)
if not any(possible_valid_pairs):
return False


Instead of creating a list of comparison booleans, use the built-in keyword:

if (curr_kind, next_kind) not in VALID_PAIRS:
return False

newTokens = []


This is the only place in your code that I see a variable using lowerCamelCase. I suppose you had a bad day and you were caught in a moment of weakness. I'll forgive you this time; just make sure it doesn't happen again.

## Conclusion

Despite these criticisms, this is still a very well-written script. It's logical, extendable, organized, and easy to read. There are comments in many places, and most of them are useful explanations that further enhance the readability. This, in short, is a script to be proud of.

### 1. Review

1. The error messages are not very helpful:

>>> eval_expr('2+')
Traceback (most recent call last):
...
fst, snd = tokens[where-1].info, tokens[where+1].info
IndexError: list index out of range


I would prefer to see something like "expected a term but found end of input".

2. It's usual to have blank lines between top-level declarations, to make the code easier to read (just as prose is usually broken up into paragraphs rather than being one big block).

3. DIGITS is not used — but if you need it, it is already built into Python as string.digits.

4. Defining OPS is unnecessary, since it's just the keys of the OP_FUNCS dictionary, and so instead of expr[index] in OPS you can write expr[index] in OP_FUNCS.

5. The function lambda x, y:x + y is built into Python as operator.add; similarly there are operator.sub, operator.mul, operator.truediv and operator.pow.

6. PLACEHOLDER is not used.

7. Instead of:

possible_valid_pairs = []
for valid_pair in VALID_PAIRS:
possible_valid_pairs.append((curr_kind, next_kind) == valid_pair)
#Test if it's equal to a valid pair
if not any(possible_valid_pairs):
return False


you could write:

if (curr_kind, next_kind) not in VALID_PAIRS:
return False


### 2. Improved data structures & algorithms

1. For the Token class you write "This is not really useful but tuples could be less clear". Python provides collections.namedtuple for this use case:

from collections import namedtuple

Token = namedtuple('Token', 'type value')

2. The type field of a Token is a string that must be OP, NUM, OPAREN, or CPAREN. Using strings to represent a fixed set of values is risky — if you wrote CPERAN by mistake then you wouldn't get an error but the program wouldn't work. It is better to use an enumeration:

from enum import Enum

class TokenType(Enum):
OP = 1                      # Operator
NUM = 2                     # Number
OPAREN = 3                  # Open parenthesis
CPAREN = 4                  # Close parenthesis
END = 5                     # End of input


(We'll need TokenType.END later when we come to the parsing step.)

Now if you write TokenType.CPERAN by mistake then you get AttributeError: CPERAN.

3. Tokenization is often easiest using a single regular expression. Here you can write:

_TOKEN_RE = re.compile(r'''
\s*(?:                      # Optional whitespace, followed by one of
([+*/^-])                   # Operator
|((?:[1-9]\d*|0)(?:\.\d+)?) # Number
|($$) # Open parenthesis |($$)                       # Close parenthesis
|(.))                       # Any other character is an error
''', re.VERBOSE)

def tokenize(expr):
"Generate the tokens in the string expr, followed by END."
for match in _TOKEN_RE.finditer(expr):
op, num, oparen, cparen, error = match.groups()
if op:
yield Token(TokenType.OP, op)
elif num:
yield Token(TokenType.NUM, float(num))
elif oparen:
yield Token(TokenType.OPAREN, oparen)
elif cparen:
yield Token(TokenType.CPAREN, cparen)
else:
raise SyntaxError("Unexpected character: {!r}".format(error))
yield Token(TokenType.END, "end of input")


Notice that the tokens are generated using the yield instruction, instead of returned as a list by repeatedly calling append. This is convenient because, as we'll see later, the parser needs to fetch tokens one at a time. If you have a use case where you do need a list of tokens, you can always call list(tokenize(expr)).

4. The next stage after tokenization should be parsing. The idea is to turn the stream of tokens into a parse tree (also known as an abstract syntax tree). For example, the input 1*2+3 would be transformed into a data structure looking something like this:

BinExpr(
left=BinExpr(
left=Number(value=1.0),
op=operator.mul,
right=Number(value=2.0)),
op=operator.add,
right=Number(value=3.0))


This kind of data structure is easy to define:

# Parse tree: either number or binary expression with left operand,
# operator function, and right operand.
Number = namedtuple('Number', 'value')
BinExpr = namedtuple('BinExpr', 'left op right')


and really easy to evaluate:

def eval_tree(tree):
"Evaluate a parse tree and return the result."
if isinstance(tree, Number):
return tree.value
elif isinstance(tree, BinExpr):
return tree.op(eval_tree(tree.left), eval_tree(tree.right))
else:
raise TypeError("Expected tree but found {}"
.format(type(tree).__name__))


(Compare this with the difficulty you have in eval_tokens.)

5. So how to turn a stream of tokens into a parse tree? Well, there are lots of techniques for parsing but a good one to start with is recursive descent:

def parse(tokens):
"Parse iterable of tokens and return a parse tree."
tokens = iter(tokens)       # Ensure we have an iterator.
token = next(tokens)        # The current token.

def error(expected):
# Current token failed to match, so raise syntax error.
raise SyntaxError("Expected {} but found {!r}"
.format(expected, token.value))

def match(type, values=None):
# If the current token matches type and (optionally) value,
# advance to the next token and return True. Otherwise leave
# the current token in place and return False.
nonlocal token
if token.type == type and (values is None or token.value in values):
token = next(tokens)
return True
else:
return False

def term():
# Parse a term starting at the current token.
t = token
if match(TokenType.NUM):
return Number(value=t.value)
elif match(TokenType.OPAREN):
tree = addition()
if match(TokenType.CPAREN):
return tree
else:
error("')'")
else:
error("term")

def exponentiation():
# Parse an exponentiation starting at the current token.
left = term()
t = token
if match(TokenType.OP, '^'):
right = exponentiation()
return BinExpr(left=left, op=OP_FUNCS[t.value], right=right)
else:
return left

def multiplication():
# Parse a multiplication or division starting at the current token.
left = exponentiation()
t = token
while match(TokenType.OP, '*/'):
right = exponentiation()
left = BinExpr(left=left, op=OP_FUNCS[t.value], right=right)
return left

def addition():
# Parse an addition or subtraction starting at the current token.
left = multiplication()
t = token
while match(TokenType.OP, '+-'):
right = multiplication()
left = BinExpr(left=left, op=OP_FUNCS[t.value], right=right)
return left

tree = addition()
if token.type != TokenType.END:
error("end of input")
return tree


Note:

1. The exponentiation parser is different from the other two expression parsers. That's because exponentiation is right-associative (we want 3^3^2 to evaluate to 19683, not 729) but multiplication/division and addition/subtraction are left-associative (we want 4/2/2 to evaluate to 1, not 4).

2. The multiplication and addition functions are very similar and it would be easy to eliminate the duplication. I've left them like this to make the recursive descent structure as clear as possible.

6. Now the top-level evaluation looks like this:

def eval_expr(expr):
"Evaluate an expression and return the result."
tokens = tokenize(expr)
tree = parse(tokens)
return eval_tree(tree)

• I have decided to accept the other answer, as it addresses my question a bit more, an is more upvoted. Apr 13 '17 at 12:09