python 代码实现四则运算 (前缀表达式) 递归 非递归

python 代码实现四则运算 (前缀表达式)

 

计算表达式如下：

(+ 1 2 )

(+ 1 (+ 2 3))

(* (+ 1 2) (*3 4))

 

第一个函数cal_1 是使用递归的形式；

第二个函数cal_2 是使用非递归的形式--堆栈, 且第二个支持多个参数（2个或以上）

 

 

#calculator expression

def cal_1 (s):
    s = s.strip().replace('(','',1)[::-1].replace(')','',1)[::-1].strip()
    if ' ' not in s :
        return float(s)  #just a number
    else:
        tmp = s.split(' ',1)
        opt = tmp[0].strip()
        temp = tmp[1].strip()
        left = 0       
        right = 0
        for i in range(len(temp)):
            if temp[i] == '(':
                left += 1
            if temp[i] == ')':
                right += 1
            if temp[i] == ' ' and left==right :
                break
        
        data1 = temp[:i]
        data2 = temp[i:]

        v1 = cal_1(data1)
        v2 = cal_1(data2)
        if opt == '+':
            return v1 + v2
        elif opt == '-':
            return v1 - v2
        elif opt == '*':
            return v1 * v2
        elif opt == '/':
            return v1 / v2
        elif opt == '%':
            return v1 % v2
        else:
            return 0


def cal_2 (s):
    def cal_exp (exp):
        def cal_exp_two (opt,a,b):
            a = float(a)
            b = float(b)
            if opt == '+':
                return a+b
            elif opt == '-':
                return a-b
            elif opt == '*':
                return a*b
            elif opt == '/':
                return a/b
            elif opt == '%':
                return a%b
            else:
                return 0
        result = exp[1]
        for i in range(2,len(exp)):
            result = cal_exp_two (exp[0],result,exp[i])
        return result
    s = s.replace('(',' ( ').replace(')',' ) ')
    left = s.split()
    right = []
    temp  = []
    while left:
        tmp_left = left.pop().strip()
        if tmp_left == '(':
            tmp_right = right.pop()
            while tmp_right != ')':
                temp.append (tmp_right)
                tmp_right = right.pop()
            right.append (cal_exp(temp))
            temp = []
        else:
            right.append (tmp_left)
    return right[-1]




print cal_1 ( '(- (+ 23 1) (* 3 4))')     #12.0
print cal_1 ( '(- (+ 1 2) (* 3 4))')      #-9
print cal_1 ( '(- 1 1)')                  #0
print cal_1 ( '(- 1 (* 12 12))' )         #-143.0
print cal_1 ( '(- (* 23 2) 12))' )        #34.0
print '----------------------'
#
print cal_2 ( '(- (+ 23 1) (* 3 4))')     #12.0
print cal_2 ( '(- (+ 1 2) (* 3 4))')      #-9
print cal_2 ( '(- 1 1)')                  #0
print cal_2 ( '(- 1 (* 12 12))' )         #-143.0
print cal_2 ( '(- (* 23 2) 12))' )        #34.0
print cal_2 ( '(- (* 23 2 2) 12 ))' )     #80.0