Calculator for parsing user input

I have written this program after a lot of effort, and I was wondering about the efficiency of that solution and if it's neat.

How plain is this program and is there any better way to rewrite it?

import string

# Strength of operations:
#   -> [] (brackets)
# 6 -> ~ (negative)
# 5 -> @, $, & (average, maximum, minimum) # 4 -> %, ! (modulo, factorial) # 3 -> ^ (power) # 2 -> *, / (multiplication, division) # 1 -> +, - (addition, subtraction) def BinaryOperation(exp, idx): """ Gets an expression and an index of an operator and returns a tuple with (first_value, operator, second_value). """ first_value = 0 second_value = 0 #Get first value idx2 = idx -1 if idx2 == 0: first_value = exp[idx2:idx] else: while (idx2 > 0) and (exp[idx2] in string.digits): idx2 -=1 if (exp[idx2] in ("-")) or (exp[idx2] in string.digits):#-5*3 first_value = exp[idx2:idx] else:#%5*3 first_value = exp[idx2+1:idx] #Get second value idx2 = idx +1 if exp[idx+1] not in string.digits: #If there is something like 1*+5, second_sign will be +. idx2 += 1 #idx2 will begin from the char after the sign. while (idx2 < len(exp)) and (exp[idx2] in string.digits): idx2 += 1 second_value = exp[idx+1:idx2] return (first_value, exp[idx], second_value) def UnaryOperation(exp, idx): """ Gets an expression and an index of an operator and returns a tuple with (operator, value). """ #Get value idx2 = idx+1 if exp[idx+1] not in string.digits: #If there is something like ~-5, second_sign will be -. idx2 += 1 #idx2 will begin from the char after the sign. while (idx2 < len(exp)) and (exp[idx2] in string.digits): idx2 +=1 return (exp[idx], exp[idx+1:idx2]) def Brackets(exp): idx = 0 while idx < len(exp): if exp[idx] == "[": #Brackets close_bracket = exp.find("]") if close_bracket == -1: raise Exception("Missing closing bracket.") exp_brackets = exp[idx+1:close_bracket] value = str(solve(exp_brackets)) exp = exp.replace("[" + exp_brackets + "]", value) idx = 0 #The len has been changed, scan again. idx += 1 return Level6(exp) def Level6(exp): idx = 0 while idx < len(exp): if exp[idx] in ("~"): #Negative sub_exp = UnaryOperation(exp, idx) value = ~int(sub_exp) value = str(value) exp = exp.replace(''.join(sub_exp), value) idx = 0 #The len has been changed, scan again. idx += 1 return Level5(exp) def Level5(exp): idx = 0 while idx < len(exp): if exp[idx] in ("@", "$", "&"):
#Average, Maximum and Minimum
sub_exp = BinaryOperation(exp, idx)
first_value = int(sub_exp)
second_value = int(sub_exp)
if sub_exp == "@":
value = (first_value + second_value)/2
if sub_exp == "\$":
value = first_value if first_value > second_value else second_value
if sub_exp == "&":
value = first_value if first_value < second_value else second_value

value = str(value)

exp = exp.replace(''.join(sub_exp), value)
idx = 0 #The len has been changed, scan again.

idx += 1

return Level4(exp)

def Level4(exp):
idx = 0
while idx < len(exp):
if exp[idx] in ("%","!"):
#Modulo and Factorial
if exp[idx] == "%":
sub_exp = BinaryOperation(exp, idx)
value = int(sub_exp) % int(sub_exp)
if exp[idx] == "!":
sub_exp = UnaryOperation(exp, idx)
value = reduce(lambda x,y:x*y, range(1, int(sub_exp)+1))

value = str(value)

exp = exp.replace(''.join(sub_exp), value)
idx = 0 #The len has been changed, scan again.

idx += 1

return Level3(exp)

def Level3(exp):
idx = 0
while idx < len(exp):
if exp[idx] in ("^"):
#Power
sub_exp = BinaryOperation(exp, idx)
value = int(sub_exp) ** int(sub_exp)

value = str(value)

exp = exp.replace(''.join(sub_exp), value)
idx = 0 #The len has been changed, scan again.

idx += 1

return Level2(exp)

def Level2(exp):
idx = 0
while idx < len(exp):
if exp[idx] in ("*", "/"):
#Multiplication and Division
sub_exp = BinaryOperation(exp, idx)
if sub_exp == "*":
value = int(sub_exp) * int(sub_exp)
if sub_exp == "/":
value = int(sub_exp) / int(sub_exp)

value = str(value)

exp = exp.replace(''.join(sub_exp), value)
idx = 0 #The len has been changed, scan again.

idx += 1

return Level1(exp)

def Level1(exp):
idx = 0
while idx < len(exp):
if (exp[idx] in ("+", "-")) and (idx != 0):
sub_exp = BinaryOperation(exp, idx)
if sub_exp == "+":
value = int(sub_exp) + int(sub_exp)
if sub_exp == "-":
value = int(sub_exp) - int(sub_exp)

value = str(value)

exp = exp.replace(''.join(sub_exp), value)
idx = 0 #The len has been changed, scan again.

idx += 1

return exp

def solve(exp):
exp = Brackets(exp)
return float(exp) if "." in exp else int(exp)

def remove_whitespace(exp):
""" Gets a string and removes all whitespaces and tabs """
exp = exp.replace(" ", "")
exp = exp.replace("\t", "")
return exp

while True:
exp = raw_input("")
exp = remove_whitespace(exp)
print solve(exp)

The code would more straightforward if you used a lexer. A lexer does the very basic bits of parsing, transforming your incoming text into a list of tokens. So in this case, you might have

lexer("-5 + 4 * [7-3]^2") == [-5, '+', 4, '*', '[', 7, '-', 3, ']', '^', 2]

This way all string manipulation will happen in the lexer, and the rest of your parsing code will be simplified. It just has to operate on the list of tokens.

For parsing, I also like to have a Parser class. The Parser class will hold both the list of tokens and the current position. Then I have various utility functions on the Parser class. The process of parsing brackets should then look like:

parser.match( '[' )
number = level6(parser)
parser.match( ']' )
return number

parser.match will throw an exception if the expected element isn't there. Because the parser object takes care of the current location, you don't need to slice lists or anything.

It would also be useful to have tests. Have a list of expressions with known values and then write code to loop over that list and assert that they have the same values. Add new items as you add features. That way if you ever break anything, the tests will catch it.

• Thank you for your comment. The assignment was to use recursion and solve the "strongest" operations and then update the expression, until the weakest operation will be solved and then I can know that I finished solving the expression. Will I be able to solve the expressions with recursion if I split the expression to tokens?
– Lior
Dec 5 '12 at 17:13
• @Lior: Yes, but the lexing step will not (and should not) be recursive. At a high level, a recursive calculator Calculate(string) which receives as input "5 * (34+1)" will eventually call Calculate("34+1"). Winston's change just means you go from Calculate(string) to Calculate(tokens) (e.g., Calculate(['5','*','(','34','+','1',')']) calls Calculate(['34','+','1']) . Dec 5 '12 at 18:02
• @Lior, as Brian says the lexer won't change the recursion at all. My suggestion of a parsing class probably would. It would still use recursion, but whether it fits your requirements I don't know. Dec 5 '12 at 19:09

Every levelX functions looks roughly the same:

idx = 0
while idx < len(exp):
if exp[idx] in (...):
//...

value = str(value)

exp = exp.replace(''.join(sub_exp), value)
idx = 0 #The len has been changed, scan again.

idx += 1

I don't like the idea of having 6 functions named level#. If I ask the question, "where is exponentiation handled?", the answer is "check each Level function until you find it" or "search your code for the ^" character (I realize that you cheated and added a comment at the top to resolve this problem, but the ideal is for code to be mostly self-documenting). Both of these answers strikes me as less than ideal, though your code is short enough for it to be doable.

Every level seems to be split up into a calculation section and a parsing section, the latter of which is identical (other than the token list) between functions. You should refactor this, separating out these two pieces of functionality. Consider using the strategy design pattern.

• Thank you for your comment. I will check the strategy pattern out.
– Lior
Dec 4 '12 at 18:57