算法70-解析算式并返回结果

题目：

给定一个字符串是一个数学的算式，包含加减乘除和括号，要求返回计算结果

分析：

1 遇到数字，就组成整数压入栈，入栈的时候判断上一个字符是否是乘除符号如果是，就先计算乘除的结果，将结果压入栈，保证栈内只有数字，（最后栈要做累加和，因此加号直接忽略，减号就与它后面跟的数组组成负数，方便最后直接累加栈中的数字）

2, 遇到乘除，先压入栈，在每个数字入栈的时候执行乘除运算

3 遇到左括号直接压入栈

4 遇到右括号，从栈弹出数字，直到遇到第一个左括号，将弹出的数计算出结果压入栈

5 最后得到一个只有正负数的数组，遍历累加得到和返回

代码：

# -*- coding:utf-8 -*-
# !/usr/bin/python

import time
import random
import types


# string="18+23*(35+420*(2000-15))+580/2+(-5)*12"
#todo:(-1),和div by 0
def process(string):
    num="" #仅用来组合数字
    parse=[] #解析好的list，其中只有数字和加减符号
    for i in range(0,len(string)):
        print str(num),string[i]
        #当前是数字，就拼成完整整数到num
        if ord(string[i]) in range(48,58):
            num=num+string[i]
        # 遇到加减乘除号就把num中拼好的整数取出来，先将整数放进parse，放的时候判断上一位是否是乘除号，调用append桶parse判断
        # 注意num为空的情况  比如*（）+ 这种两个符号链在一起时num为空
        if string[i] == "+" or string[i] =="-" or string[i] == "*" or string[i] == "/":
            if num != "":
                num=int(num)
                # parse.append(num)
                appendtoparse(parse,num)
                parse.append(string[i])
                # 一定要将num置空
                num = str(num)
                # print type(num)
                num = ""
        #如果遇到左括号，直接压入
        if string[i] == "(" :
            if num != "":#压入上一个数字
                num=int(num)
                parse.append(num)
                num = str(num)
                # print type(num)
                num = ""
            parse.append(string[i])#压入左括号
        ##遇到右括号，将parse中的数字依次取出，取到左括号为止，放到临时数组，计算出左括号到右括号中间的部分，按规则append到parse中
        if string[i] == ")" :
            temp = []
            if num != "":#右括号的前面必然是数字，先压入parse
                # temp.insert(0,int(num))
                appendtoparse(parse,num)
                print "parseeee   =%s", parse
                while len(parse)>1:
                    n=parse.pop()
                    if n != "(" :#右括号前面必然是数字，数字在压入时已经判断了它前面的符号，就是说parse也如数字，它前面就没有运算符号了，直接取出到temp计算
                        print "heeeeeeeeeeeeeeee" + str(n)
                        print type(n)

                        temp.insert(0,int(n))
                    else:
                        break
                # num = str(num)
                # # print type(num)
                # num = ""
            print "temppp   =%s" ,temp
            num=finalcount(temp)##只是算出括号结果，先不用加入parse，其他地方都会判断并加入
            print "nummmmmmmmmmmmm" +str(num)

        print parse
    appendtoparse(parse,num)
    print parse
    return parse

#parse的长度要大于2
#判断是乘除号，先将乘除号弹出，再将被乘数/被除数弹出，计算出乘积/商再append
#判断是加减号就直接append
#长度小于2页直接append
def appendtoparse(parse,n):
    if len(parse)>1:
        if parse[len(parse)-1] == "*" :
            parse.pop()
            parse.append(int(parse.pop()) * int(n))
        elif parse[len(parse)-1] == "/" :#todo div by 0 issue ！！！ 注意控制条件  if  elif  else才会控制条件唯一满足
            parse.pop()
            parse.append(int(parse.pop()) / int(n))
        elif parse[len(parse)-1] == "+"  :
            parse.pop()
            parse.append(int(n))
        elif parse[len(parse) - 1] == "-":
            parse.pop()
            parse.append(-int(n))
        else:
            parse.append(n)##上一位是加减号的情况！！！不要忽略

    else:
        parse.append(n)

def finalcount(parse):
    print "going to count %d" ,parse
    result=parse[0]
    for i in range(1,len(parse)):
        result+=parse[i]
    print result
    return result###!!!这里要返回给调用方结果

string="188+23*35+420*2000-15+580/((2+5*10)*12)-1*0+(-1)"

# string = "188+23*2+100/(2+3)/2+999+100/2+3*3-2"
# f0(string)
#[188, 805, 840000, -15, 290, 60]

parse=process(string)
finalcount(parse)

# print(f1(string,0))
# tmp=["*",3,"-"]
# Append(tmp,2)
# list1=[188, '+', 46, '+', 10, '+', 999, '+', 50, '+', 9,"-",2]
# print(lastcount(list1))
# f2(list1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

todo： （-1）括号里面是负数的情况还没有处理；div by 0 的问题还没有处理

总结：
1 ord（）可以求出str的ascii码
2 借用一个临时数组将一个个数字组成整数，直到下一个是符号，括号，将整数压入栈，入栈是判断它前面是否是乘除，是的话弹出先计算乘除，所以当遇到符号的时候，表示前面的数字结束了，此时压入栈
3 注意if elif else的使用

string=“188+2335+4202000-15+580/((2+5*10)12)-10+(-1)”
代码计算结果：

going to count %d [188, 805, 840000, -15, 0, 0]
840978


1
2
3
4

命令行计算结果：