lisper learning python, ... could you please comment my first python program?

[neptundancer at gmail.com]

Hi,
  to extend my skills, I am learning python. I have written small
program which computes math expression like "1+2*sin(y^10)/cos(x*y)"
and similar, so far only + - * / ^ sin con tan sqrt are supported. But
my program is quite inextensible, I have to change the code to add new
functions... Could some fellow experienced pythonista give me some
tips how to make my program shorter, and more extensible?

to use it, try something like compute("1+x+sin(x)", {"x" : 10}), the
second param is environment so variables like x or y are looked for
value here...

below is the code.... thanks for any tips!

----- code here ----


import sys
import string
import math

def normalize(string):
    tmp = "".join([c for c in string if c != " "])
    return "(" + tmp + ")"

def most_nested_expression(string):
    start = index = 0
    end = len(string) - 1
    level = max_level = 0
    most_nested = False
    for c in string:
        if c == "(":
            level += 1
            if level > max_level:
                most_nested = True
                max_level = level
                start = index
        elif c == ")":
            level -= 1
            if most_nested == True:
                most_nested = False
                end = index
        index += 1
    if level != 0:
        raise IOError("mismatched parens")
    if max_level == 0:
        return (0, len(string), string)
    else:
        return (start + 1, end - start - 1, string[start + 1:end])

def is_reduced_expression(string):
    for c in string:
        if c == "^" or c == "*" or c == "/" or c == "+" or c == "-":
            return False
    return True

def find_first(string, operators):
    positions = []
    for op in operators:
        pos = string.find(op)
        if pos != -1:
            positions += [pos]
    if positions == []:
        return None
    else:
        return min(positions)

def find_operator(string):
    for ops in [["^"], ["*", "/"], ["+", "-"]]:
        pos = find_first(string, ops)
        if pos != None:
            if string[pos + 1] == "+" or string[pos + 1] == "-":
                return pos + 1
            else:
                return pos
    return None

def left_operand(string, operator_pos):
    left = None
    operator = string[operator_pos]
    candidates = [pos for pos in [string.rfind(op, 0, operator_pos)
                                  for op in ["(", ")", "^", "*", "/",
"+", "-"]]
                  if pos != -1]
    if candidates != []:
        left = max(candidates)
    if left == None:
        if operator == "^" or operator == "*" or operator == "/":
            raise IOError("invalid expression %s" % string)
        else: # + or -
            return ("0", operator_pos)
    else:
        if left + 1 == operator_pos:
            if operator == "+" or operator == "-":
                return ("0", left)
            else:
                raise IOError("invalid expression %s" % string)
        else:
            return (string[left + 1:operator_pos], left)

def right_operand(string, operator_pos):
    right = None
    candidates = [pos for pos in [string.find(op, operator_pos + 1)
                                  for op in ["(", ")", "^", "*", "/",
"+", "-"]]
                  if pos != -1]
    if candidates == []:
        if operator_pos == len(string) - 1:
            raise IOError("invalid expression %s" % string)
        else:
            return (string[operator_pos + 1:], len(string))
    else:
        right = min(candidates)
        if operator_pos + 1 == right:
            raise IOError("invalid expression %s" % string)
        else:
            return (string[operator_pos + 1:right], right)

def function_name(string, left_paren_pos):
    candidates = [pos for pos in [string.rfind(op, 0, left_paren_pos)
                                  for op in ["(", "^", "*", "/", "+",
"-"]]
                  if pos != -1]
    if candidates == []:
        return (None, None)
    else:
        left = max(candidates)
        name = string[left + 1:left_paren_pos]
        fun_names = ["sin", "cos", "tan", "sqrt"]

        for f in fun_names:
            if f == name:
                return (left + 1, name)
        return (None, None)

def reduce_step(string, index):
    (left, exp_len, exp) = most_nested_expression(string)
    #print "most nested %s" % exp
    if is_reduced_expression(exp):
        (left1, name) = function_name(string, left - 1)
        if left1 != None:
            return ((name, string[left:left + exp_len], None),
                    string[0:left1] + "$%s" % index + string[left +
exp_len + 1:],
                    True)
        else:
            return ((None, None, None), string[0:left - 1] + exp +
string[left + exp_len + 1:], False)
    else:
        operator_pos = find_operator(exp) + left
        (left_op, left_mark) = left_operand(string, operator_pos)
        (right_op, right_mark) = right_operand(string, operator_pos)
        return ((string[operator_pos], left_op, right_op),
                string[0:left_mark + 1] + "$%s" % index +
string[right_mark:],
                True)

def reduce(string):
    chain = []
    index = 0
    while string[0] == "(":
        ((function, left_op, right_op), new_string, is_expr) =
reduce_step(string, index)
        if is_expr:
            chain += [(function, left_op, right_op)]
            index += 1
        string = new_string
    return chain

def add(a, b): return a + b
def sub(a, b): return a - b
def mul(a, b): return a * b
def div(a, b): return a / b

def translate_function(fn_str):
    if fn_str == "+": return add
    elif fn_str == "-": return sub
    elif fn_str == "*": return mul
    elif fn_str == "/": return div
    elif fn_str == "^": return math.pow
    elif fn_str == "sin": return math.sin
    elif fn_str == "cos": return math.cos
    elif fn_str == "tan": return math.tan
    elif fn_str == "sqrt": return math.sqrt
    else: raise IOError("unknown function %s" % fn_str)

def translate_operand(op_str):
    if op_str[0] == "$":
        result_idx = int(op_str[1:])
        return lambda results, env: results[result_idx]
    else:
        try:
            value = float(op_str)
            return lambda results, env: value
        except ValueError:
            return lambda results, env: env[op_str]

def translate(chain):
    res = []
    for (fn_str, left_op_str, right_op_str) in chain:
        fn = translate_function(fn_str)
        left_op = translate_operand(left_op_str)
        if right_op_str != None:
            res += [(fn, [left_op, translate_operand(right_op_str)])]
        else:
            res += [(fn, [left_op])]
    return res

def compute_value(chain, env, results):
    assert len(chain) == len(results)
    index = 0
    for (fn, operand_fns) in chain:
        operands = [op_fn(results, env) for op_fn in operand_fns]
        results[index] = apply(fn, operands)
        index += 1
    return results[index - 1]

def compute(string, env):
    print "input: %s" % string
    string = normalize(string)
    print "normalized: %s" % string
    string_chain = reduce(string)
    print "reduced: %s" % string_chain
    chain = translate(string_chain)
    print "translated: %s" % chain
    return compute_value(chain, env, range(len(chain)))