算数学表达式如-7 * (-5 * (2*-3))+ 5 * -(-1.1)
题目链接

参考：

1 [数据结构]表达式树——手动eval()
2 Python计算器（模拟eval）

思路：

编译原理本来就没学精还忘光了。。。只好网上找教程，

将各个元素提取出来（不知道术语怎么叫。。）, 写reader，lexer，参考第一个链接

如 21+ (2.1 * 2),含有的7个元素有：
21
+
(
2.1
*
2
)

递归去括号，最终得到一个没有括号的表达式，递归算括号里面的表达式，每次记录(的位置，匹配到一个)就递归算出括号里表达式的值，参考第二个链接

比如以下变化
2 * (1+(2*3))+1
2 * (1+6)+1
2 * 7+1

计算无括号的表达式，先算乘除法再算加减法，参考第二个链接

2*7+1
14+1
15

完整代码

class Reader:

    def __init__(self, str):
        self.str = str
        self.len = len(str)
        self.index = 0

    def next(self):
        self.index += 1
        return self.str[self.index-1]

    def crt_data(self):
        return self.str[self.index]

    def has_next(self):
        return self.index < self.len

    def peek(self):
        return self.str[self.index+1]

class Lexer:

    def __init__(self, expression):
        self.reader = Reader(expression)

    def parse(self):
        token_list = []
        reader = self.reader

        def last_token():
            return token_list[len(token_list) - 1]

        def readnum():
            num = ''
            while (reader.has_next() and reader.crt_data().isdigit()) or (reader.has_next() and reader.crt_data() == '.'):
                num += reader.next()
            return num

        i = 0
        while reader.has_next():
            c = reader.next()

            if c.isdigit():
                num = c + readnum()
                token_list.append(float(num))
            else:
                token_list.append(c)
            i+=1
        return token_list

def change(eq,count): #解决同时出现+-，--, -+， ++情况
    #插入一个0方便计算，如-4变成0-4
    if eq[0] == '+' or eq[0] == '-': eq.insert(0, 0)
    #deal with --, -+, ++,+- 
    if eq[count] == '-' and count + 1 < len(eq) and eq[count+1] == '-':
        eq[count] = '+'
        del eq[count+1]
    if eq[count] == '-' and count + 1 < len(eq) and eq[count+1] == '+':
        del eq[count+1]
    if eq[count] == '+' and count + 1 < len(eq) and eq[count+1] == '+':
        del eq[count+1]
    if eq[count] == '+' and count + 1 < len(eq) and eq[count+1] == '-':
        del eq[count]
    return eq

def deal_multiplication_division(eq): #处理所有的乘除的计算方程式
    '''
    :param eq:处理带有乘除符号的格式化列表
    :return: 去掉乘除好以后的格式化列表
    '''
    count = 0
    flag = True
    #用一个while循环，处理出现 +---(+1)情况，有很多个+-号，直到只有一个+-号
    while flag:
        index = 0
        flag = False
        for i in eq:
            if i == '-' or i == '+':
                eq = change(eq, index)
                if index + 1 < len(eq) and (eq[index+1] == '+' or eq[index+1] == '-'):
                    flag = True
            index+=1
    for i in eq:
        if i == '*':#如1*-2
            if eq[count+1] != '-' and eq[count+1] != '+':
                eq[count-1] = float(eq[count-1]) * float(eq[count+1])
                del(eq[count])
                del(eq[count])
            elif eq[count+1] == '-':
                eq[count] = float(eq[count-1]) * float(eq[count+2])
                eq[count - 1] = '-'
                del(eq[count+1])
                del(eq[count+1])
            elif eq[count+1] == '+':
                eq[count-1] = float(eq[count-1]) * float(eq[count+2])
                del(eq[count])
                del(eq[count])
                del(eq[count])
            eq = change(eq,count-1)
            return deal_multiplication_division(eq)
        elif i == '/':
            if eq[count+1] != '-' and eq[count+1] != '+':
                eq[count-1] = float(eq[count-1]) / float(eq[count+1])
                del(eq[count])
                del(eq[count])
            elif eq[count+1] == '-':
                eq[count] = float(eq[count-1]) / float(eq[count+2])
                eq[count-1] = '-'
                del(eq[count+1])
                del(eq[count+1])
            elif eq[count+1] == '+':
                eq[count-1] = float(eq[count-1]) / float(eq[count+2])
                del(eq[count])
                del(eq[count])
                del(eq[count])
            eq = change(eq,count-1)
            return deal_multiplication_division(eq)
        count = count + 1
    return eq

def deal_plus_minus(eq): #处理所有的加减方程式的计算
    '''
    :param eq:只带有加减号的格式化列表
    :return: 计算出整个列表的结果
    '''
    count, index = 0, 0
    flag = True
    #用一个while循环，处理出现 +---(+1)情况，有很多个+-号，直到只有一个+-号
    while flag:
        index = 0
        flag = False
        for i in eq:
            if i == '-' or i == '+':
                eq = change(eq, index)
                if index + 1 < len(eq) and (eq[index+1] == '+' or eq[index+1] == '-'):
                    flag = True
            index+=1

    if eq[0] != '-':
        sum = float(eq[0])
    else:
        sum = 0.0

    for i in eq:
        if i == '-':
            sum = sum - float(eq[count+1])
        elif i == '+':
            sum = sum + float(eq[count+1])
        count = count + 1
    if sum >= 0:
        eq = [str(sum)]
    else:
        eq = ['-',str(-sum)]
    return eq

def calculate(s_eq): 
    '''
    :param s_eq:不带括号的格式化列表
    :return: 返回最终的计算结果
    '''
    if '*' or '/' in s_eq:
        s_eq = deal_multiplication_division(s_eq)
    if '+' or '-' in s_eq:
        s_eq = deal_plus_minus(s_eq)
    return s_eq

def simplify(format_list):
    bracket = 0 #用于存放左括号在格式化列表中的索引
    count = 0
    for i in format_list:
        if i == '(':
            bracket = count
        elif i == ')':#已经找到了一个括号，用递归的方式算出括号内的内容，再放到原先的列表
            temp = format_list[bracket + 1 : count]
            new_temp = calculate(temp)

            format_list = format_list[:bracket] + new_temp + format_list[count+1:]
            format_list = change(format_list,bracket) #解决去括号后出现的'--','+-'问题
            return simplify(format_list) #递归去掉括号
        count = count + 1
    return format_list #当递归到最后一层层的时候，不在有括号，因此返回最后无括号的列表内容

def calc(e):
    expression = ''.join(e.split(' '))
    s = Lexer(expression)
    tokenlist = s.parse()
    simseq = simplify(tokenlist)
    ans = calculate(simseq)

    if len(ans) == 2: #判断最终结果的正负值并返回结果
        if ans[0] == '-':
            ans = -float(ans[1])
        else:
            ans = float(ans[1])
    else:
        ans = float(ans[0])

    return ans