# Calculator that parses S-expressions

This is my first program I can call 'something'. I would be glad to hear what you think of it, so I wouldn't pick up bad habits further on.

It catches errors, but requires numbers to be separated from operators. It ignores a lot of characters, therefore (+ 2 2) is as valid as (+ 2 blargh 2)

100 lines of code + comments that should make everything clear:

# This program evaluates an arithmetic problem written as an S-expression.
# Thus 3 + (7 * 4 * 2) + 1 + (6 / 5) + 8 becomes (+ 3 (* 7 4 2) 1 (/ 6 5) 8).
# IMPORTANT NOTE: every number must be separated from an arithmetic operator by
# white space to avoid confusion between arithmetic operation and indicator of
# positiveness or negativeness of the number.(+3 7) is INVALID and evaluates to
# 7 because '(+3' bit is simplified to '+'. Instead use (+ 3 7) or (+ +3 +7)!

# The program loop.
def mainLoop():
while True:
expression = getExpression()
if (expression.upper() == "EXIT"):
break
expression = formatExpression(expression)
result = evaluate(expression, 0)[0]
print (result)

# Asks user to enter an expresion and returns the input.
def getExpression():
print("Enter \"EXIT\" to exit. Numbers must be separated from operators.")
expression = input("Enter expression: ")
return expression

# Formats an expression so it would be easy to be manipulated further on.
def formatExpression(expression):
exp = []
expression = leaveCertainChars(expression, ")0123456789.+-*/ eE")
expression = detachBrackets(expression)
expression = expression.split()
for item in expression:
if isNumber(item):
exp.append(item)
else:
for character in item:
if isOperator(character) or character == ')':
exp.append(character)
return exp

# Leaves only the characters that really matter.
def leaveCertainChars(string, chars):
new_string = ""
for character in string:
if character in chars:
new_string += character
return new_string

# Converts each ')' to ' )'
def detachBrackets(string):
new_string = ""
for character in string:
if character == ')':
new_string += " )"
else:
new_string += character
return new_string

# THE ALGORITHM:
# There are 3 types of data: operators, operands and the END symbol ')'. Each
# expression starts with an operator, has any number of operands and ends with
# ')'. There are two possible errors to occur: division by zero and missing ')'.
# Thus, for each operator, collect operands until ')' and calculate the result.
# If an operator instead of an operand is encountered in the process of operand
# collection simply put the result of evaluation of THAT expression in the place
# of missing operand and continue forward from the end of THAT expression.

# Evaluate an expression. Return result AND the index of ending bracket
def evaluate(exp, i):
operator = exp[i]
(operands, indexOfBracket) = findOperands(exp, i+1)
result = compute(operator, operands)
return (result, indexOfBracket)

# Search for operands until ')'. Skip ')'s of other expressions. Put the result
# of nested expression as just another operand and continue forward from the end
# of that nested expression.
def findOperands(exp, i):
operands = []
index = i
while exp[index] != ')':
if isNumber(exp[index]):
operands.append(exp[index])
else:
(new_value, new_index) = evaluate(exp, index)
operands.append(new_value)
index = new_index
# The key part. Incrementing index to avoid starting at ')' next time.
index += 1
# Each expression must have ')' at the end. Otherwise it's an error!
if index >= len(exp):
operands.append('YOU MISSED A BRACKET SOMEWHERE!')
break
return (operands, index)

# Returns True if string is an operator otherwise returns False.
def isOperator(string):
if string == '+' or string == '-' or string == '*' or string == '/':
return True
else:
return False

# Returns True if string can be converted into number otherwise returns False
def isNumber(string):
try:
float(string)
return True
except ValueError:
return False

# Computes a value or reports an error
def compute(operator, operands):
# If any error was encountered before it will be passed forward immediately
for operand in operands:
if not isNumber(operand):
return operand

# The default value of zero operands is zero.
if len(operands) == 0:
return '0'
# The default value of one operand is that operand
elif len(operands) == 1:
return operands[0]
# Amount of possible operators is infinite (though amount of ASCII symbols
# is limited). Extensions could include root, power, etc...
else:
result = float(operands[0])
if operator == '+':
for operand in operands[1::]:
result += float(operand)
elif operator == '-':
for operand in operands[1::]:
result -= float(operand)
elif operator == '*':
for operand in operands[1::]:
result *= float(operand)
elif operator == '/':
for operand in operands[1::]:
# Division by zero error
if float(operand) == 0:
return "DIVISION BY ZERO"
else:
result /= float(operand)
# What comes as a string, leaves as a string
return str(result)

# Don't forget to run the program!
mainLoop()


## Following PEP-8

• High level descriptions of functions should be docstrings
• The name should be snake_case
def is_operator(string):
""" Returns True if string is an operator otherwise returns False."""
if string == '+' or string == '-' or string == '*' or string == '/':
return True
else:
return False


## Using a constant to simplify

Also the function above can be simplified and made more readable by defining a constant at the start of your file:

OPERATORS = "+*/:"


the function can then become:

 # By the way, usually string is multiline so token may be better
def is_operator(token):
""" Returns True if string is an operator otherwise returns False."""


## Be exact

def leave_certain_chars(string, chars):
"""Leaves only the characters that really matter."""
new_string = ""
for character in string:
if character in chars:
new_string += character
return new_string


Code must be precise: that really matter tells nothing to me, certain gives a feeling of uncertainty that should not be present when reading code...

Also it is a very verbose way to accomplish such a simple task. My rewrite is as follows:

def also_in_second(main_string, second_string):
"""
Given two strings, returns all the chars of the first
string that are also present in the second one.

>>> also_in_second("hello world", "hde")
'hed'
"""
return ''.join([i for i in main_string if i in second_string])


## Go built-in whenever possible

# Converts each ')' to ' )'
def detachBrackets(string):
new_string = ""
for character in string:
if character == ')':
new_string += " )"
else:
new_string += character
return new_string


What you want to do above is called replacing and you should use the standard library function:

def detach_brackets(expression):
"""Adds a space before closing brackets"""
return expression.replace(')',' )')


## Make the habit of doctesting

In math code, correctness of complex algorithms must be achieved, automatic tests help us a long way in doing that, for example:

import doctest # Start of your script

doctest.testmod() # End


setup done, the tests will run each time we execute the module, now:

def formatExpression(expression):
"""
>>> formatExpression("(+ 9 (* 3 2))")
['+', '9', '*', '3', '2', ')', ')']
>>> formatExpression("(+ 5 (- 3 (* 2 11)) 9)")
['+', '5', '-', '3', '*', '2', '11', ')', ')', '9', ')']
"""
exp = []
expression = leaveCertainChars(expression, ")0123456789.+-*/ eE")
expression = detachBrackets(expression)
expression = expression.split()
for item in expression:
if isNumber(item):
exp.append(item)
else:
for character in item:
if isOperator(character) or character == ')':
exp.append(character)
return exp


It looks like this function makes a list and removes starting brackets and spaces, let me implement it again:

def formatExpression(expression):
"""
>>> formatExpression("(+ 9 (* 3 2))")
['+', '9', '*', '3', '2', ')', ')']
>>> formatExpression("(+ 5 (- 3 (* 2 11)) 9)")
['+', '5', '-', '3', '*', '2', '11', ')', ')', '9', ')']
"""
expression = expression.replace('(','( ').replace(')',' )')
return [i for i in expression.split() if i not in ('(',' ')]


Automated testing allows for simpler, faster and more secure simplification of existing code.

## Avoid all caps

WRITING ALL CAPS is considered very uneducated and is almost the same as shouting, now imagine you asked a friend to calculate a wrong expression and he replied shouting "THIS IS NOT VALID!". You would fell offended right?

## Reduce clutter

You repeat the same messages over and over again, the user can remember them in my opinion. Your user interface should look like:

Welcome to the S-expression calculator.
Enter your expression at the '>' prompt to get the result and
enter "Exit" to exit.

> (+ 2 9)
11

> 2 + 2
Error: Bracket missing.

>

• Thank You sir! I will fix it right away. One question though: should I use docstrings too when explaining (documenting) a big subject like the program itself or an algorithm? – user63132 Apr 6 '15 at 19:53
• @MariusMacijauskas Yes, in fact the big comment at the start of your script should be a docstring, a 'module level docstring' so a docstring of the most important kind, that will tell the user the purpose of the whole script. (By the way remember that you cannot edit the question, after you have implemented all the changes you can post a follow-up) – Caridorc Apr 6 '15 at 19:58

# THE FIX (PARTIAL)

The fix is far from perfect for multiple reasons that don't really matter. Consider this a far better version of original code, thanks to Caridorc!

• Some unexpected bugs fixed (encountered in the process of fixing, used dirty unplanned fixes)

• invalid operator bug (number instead of operator at the start of expression)
• operator(s) without number bug
• sometimes result returned as an int instead of float bug
• Docstrings and doctests added (not often enough)

• Renamed functions and variables to match snake_case
• Friendlier UI (no more upper-case shouting and annoying dialog repetition)
• Some functions simplified
• if name == "main": block added
• magic strings eradicated and now constants are used instead

Other stuff I noticed:

• The style of strings is very inconsistent (sometimes "string", othertimes 'string'). This will be fixed in the next project.
• Because of some unexpected bugs and post-production extensions the code is not that well structured. This also should be less of a problem in my next project.

Here's the code:

""" This program evaluates an arithmetic problem written as an S-expression.
Thus 3 + (7 * 4 * 2) + 1 + (6 / 5) + 8 becomes (+ 3 (* 7 4 2) 1 (/ 6 5) 8)

>>> evaluate( format_expression ( "(+ 3 (* 7 4 2) 1 (/ 6 5) 8)" ), 0 )[0]
'69.2'

Important note: every number must be separated from an arithmetic operator by
white space to avoid confusion between arithmetic operation and indicator of
positiveness or negativeness of the number. (+3 7) is wrong.Use (+ 3 7) instead!

>>> evaluate( format_expression ( "(+3 7)"  ), 0 )[0]
'Invalid operator.'
>>> evaluate( format_expression ( "(+ 3 7)" ), 0 )[0]
'10.0'
"""

OPERATORS  = "+-*/"
VALID_CHRS = "+-*/)0123456789. eE"

def main_loop():
""" The program loop. """
print ("Welcome to the S-expression calculator.")
print ("Enter your expression at the '>' prompt to get the result or...")
print ("...enter \"Exit\" to exit.")
while True:
expression = input("> ")
if expression.upper() == "EXIT":
break
expression = format_expression(expression)
result = evaluate(expression, 0)[0]
print (result)
print ("") # UI design element. I am an artist ;)

def format_expression(expression):
""" Turns an expression string into an easy to manipulate list.

>>> format_expression("(+ 3 blargh 2)")
['+', '3', '2', ')']
"""
exp = []
# Leaving only the chars used to represent operators, operands and END sign
expression = filter_string(expression, VALID_CHRS)
# Detaching END signs that might be stuct to operands and operators
expression = detach_brackets(expression)
# Finally, splitting the expression into seperate pieces of data
expression = expression.split()
# Separating possible clumps of operators
for item in expression:
if is_number(item):
exp.append(item)
else:
for character in item:
if is_operator(character) or character == ')':
exp.append(character)
return exp

def filter_string(main_string, second_string):
""" Given two strings, returns the first one without the characters
unpresent in the second.

>>> filter_string("Hello, World!", "helo")
'ellool'
"""
return ''.join([i for i in main_string if i in second_string])

def detach_brackets(expression):
""" Adds a space before closing brackets

>>> detach_brackets("Make)My)Day))")
'Make )My )Day ) )'
"""
return expression.replace(')',' )')

""" THE ALGORITHM:
There are 3 types of data: operators, operands and the END symbol ')'. Each
expression starts with an operator, has any number of operands and ends with
')'. There are two possible errors to occur: division by zero and missing ')'.
Thus, for each operator, collect operands until ')' and calculate the result.
If an operator instead of an operand is encountered in the process of operand
collection simply put the result of evaluation of THAT expression in the place
of missing operand and continue forward from the end of THAT expression.
"""

def evaluate(exp, i):
""" Evaluate an expression. Return result & the index of ending bracket.
Returns error if exp[i] is not an operator or exp is not long enough.
>>> evaluate (['2', '1', '2', ')'], 0)
('Invalid operator.', 0)
"""
if len(exp) == 0:
return ('Expression is empty.', i)
operator = exp[i]
if not is_operator(operator):
return ('Invalid operator.', i)
(operands, index_of_bracket) = find_operands(exp, i+1)
result = compute(operator, operands)
return (result, index_of_bracket)

def find_operands(exp, i):
""" Search for operands until ')'. Skip ')'s of other expressions. Put the
result of nested expression as just another operand and continue forward
from the end of that nested expression.

>>> find_operands( ['3', '1', ')'], 0)
(['3', '1'], 2)
"""
operands = []
index = i

while index < len(exp) and exp[index] != ')':
if is_number(exp[index]):
operands.append(exp[index])
else:
(new_value, new_index) = evaluate(exp, index)
operands.append(new_value)
index = new_index
# The key part. Incrementing index to avoid starting at ')' next time.
index += 1

# Each expression must have ')' at the end. Otherwise it's an error!
if index >= len(exp):
operands.append('Error: bracket missing.')
return (operands, index)

def is_operator(token):
""" Returns True if string is an operator otherwise returns False """

def is_number(argument):
""" Returns whether an argument can be turned into a number.

>>> is_number("3.14")
True
>>> is_number("hello")
False
"""
try:
float(argument)
return True
except ValueError:
return False

def compute(operator, operands):
""" Computes a value or reports an error

>>> compute('+', ['2', '3', '7'])
'12.0'
>>> compute('*', ['1', 'SOME_ERROR'])
'SOME_ERROR'
>>> compute('/', ['1', '0'])
'Error: division by zero.'
"""
# If any error was encountered before it will be passed forward immediately
for operand in operands:
if not is_number(operand):
return operand

# The default value of zero operands is zero.
if len(operands) == 0:
return '0.0'
# The default value of one operand is that operand
elif len(operands) == 1:
return str (float(operands[0]))
# Amount of possible operators is infinite (though amount of ASCII symbols
# is limited). Extensions could include root, power, etc...
else:
result = float(operands[0])
if operator == '+':
for operand in operands[1::]:
result += float(operand)
elif operator == '-':
for operand in operands[1::]:
result -= float(operand)
elif operator == '*':
for operand in operands[1::]:
result *= float(operand)
elif operator == '/':
for operand in operands[1::]:
# Division by zero error
if float(operand) == 0:
return "Error: division by zero."
else:
result /= float(operand)
# What comes as a string, leaves as a string
return str(result)

# Don't forget to run the program!
if __name__ == "__main__":
import doctest
doctest.testmod()
main_loop()