Calculator for parsing user input

Question

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[1])

            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[0])
            second_value = int(sub_exp[2])
            if sub_exp[1] == "@":
                value = (first_value + second_value)/2
            if sub_exp[1] == "$":
                value = first_value if first_value > second_value else second_value
            if sub_exp[1] == "&":
                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[0]) % int(sub_exp[2])
            if exp[idx] == "!":
                sub_exp = UnaryOperation(exp, idx)
                value = reduce(lambda x,y:x*y, range(1, int(sub_exp[1])+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[0]) ** int(sub_exp[2])

            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[1] == "*":
                value = int(sub_exp[0]) * int(sub_exp[2])
            if sub_exp[1] == "/":
                value = int(sub_exp[0]) / int(sub_exp[2])

            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):
            #Addition and Subtraction
            sub_exp = BinaryOperation(exp, idx)
            if sub_exp[1] == "+":
                value = int(sub_exp[0]) + int(sub_exp[2])
            if sub_exp[1] == "-":
                value = int(sub_exp[0]) - int(sub_exp[2])

            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)

Answer 1

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.

Answer 2

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.