python实现字符串算式计算

发表于 | 分类于 |
字数统计: 2.5k | 阅读时长 ≈ 10

题目

计算输入的字符串算式的结果，输入为一个字符串的算式，包含小括号、+、-、*、/以及小数点，0-9的整数，若输入的字符串是规范的算式（中缀式），则输出算式的计算结果，否则报错

示例

input: 1+((32.34+3)*4)-5
output:137.36

解决思路

表达式有前缀式、后缀式、中缀式，而我们一般提到的算式均为中缀式，中缀式表达式对于我们来说是很容易计算的，但是对于计算机来说，使用前缀式或者后缀式来计算是更加方便的，所以我们解决的完整思路如下：

  1. 判断算式是否符合规范的中缀式表达式
  2. 将中缀式转为前缀式或者后缀式
  3. 根据前缀式或者后缀式计算最终结果

    判断算式

    括号匹配

    字符串算式中包含括号，所以需要判断括号是否匹配，判断括号匹配的步骤如下：
    1. 初始化一个栈S，从左到右开始遍历字符串strs；
    2. 遇到左括号直接入栈S；
    3. 遇到右括号时：
      1. 若栈为空，则括号不匹配，则停止遍历；
      1. 若栈顶元素是左括号，则栈顶元素出栈，继续扫描下一个；
      1. 若栈顶元素为右括号，则括号不匹配，则停止遍历；
    7. 遇到数字或者运算符以及小数点时，不入栈
    8. 反复执行2-4，直到扫描完整个字符串
    9. 判断栈S是否为空，若栈为空，则表示括号匹配，否则括号不匹配

python代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isFormula(self, str):
    temp = []
    # 去除字符串中的空格
    strs = str.replace(' ', '')
    for i in strs:
        if i is '(':
            temp.append(i)
        elif i is ')':
            if len(temp) == 0:
                return False
            elif temp[-1] is '(':
                temp.pop()
            else:
                temp.append(i)
    res = re.match(pattern, strs)
    if len(temp) == 0 :
        return True
    return False

算式的匹配

目前想到最快的方式是利用正则表达式，简单分析下所有算式的共性：

  1. 以括号或者数字开头
  2. 以括号或者数字结尾
  3. 中间有1个运算符或者n个（运算符+数字）的表达式组成
  4. 每个数字前均有一个或者n个括号
  5. 每个数字中可能有一个（小数点+数字）组成分数

根据以上规则，得到的正则表达式如下：

1
pattern = r'^\(*\d+(\.\d+)?((\+|\*|/|-)\(*\d+(\.\d+)?\)*)*(\+|\*|/|-)\d+(\.\d+)?\)*$'

PS：当然，括号匹配也应该可以加到正则表达式中，但是我并没有找到，如果有读者想到的话，可以留言交流
所以判断算式是否匹配的代码如下：

1
2
3
4
5
pattern = r'^\(*\d+(\.\d+)?((\+|\*|/|-)\(*\d+(\.\d+)?\)*)*(\+|\*|/|-)\d+(\.\d+)?\)*$'
res = re.match(pattern, strs)
# match是从头开始匹配，这里需要完全匹配，所以如果匹配成功的话，应该是endpos等于字符串长度
if res.endpos == len(strs): 
    return True

再结合括号匹配的结果，则可以得到算式是否符合规范

中缀式转前缀式

简介

前缀式又称为逆波兰式，前缀式的表达式位于操作数之前，如下：

‘+’, 1, ‘-‘, ‘*’, ‘+’, 32.34, 3, 4, 5

前缀式表达式求值

前缀式求值过程如下：

  1. 从右至左扫描算式
  2. 遇到数字时，将数字压入堆栈，
  3. 遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素在前，次顶元素在后），并将计算结果入栈；
  4. 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

中缀式转前缀式

  1. 初始化两个栈:运算符栈s1，储存中间结果的栈s2，记录连续数个数的inflag=0，以及记录是否出现过小数的decimalflag=0
  2. 从右至左扫描中缀表达式
  3. 遇到操作数时，
    3.1.若intflag和decimalflag均为0时，则直接入栈，intflag++
    3.2.若intflag=0，decimalflag=1，则s2出栈后加上当前操作数后再入栈
    3.3.若intflag>0,则s2出栈后加上当前数字左移intflag位的值（即当前数乘以10的intflag次方）
  4. 遇到运算符时，比较其与s1栈顶运算符的优先级，intflag和decimalflag置为0
    4.1.如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
    4.2.否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
    4.3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
  5. 遇到括号时
    5.1.如果是右括号“)”，则直接压入s1
    5.2.如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
  6. 遇到小数点时，将decimalflag置为1，并将当前栈顶的数字右移intflag位后入栈
  7. 重复步骤2至5，直到表达式的最左边
  8. 将s1中剩余的运算符依次弹出并压入s2
  9. 依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式

中缀式转后缀式

后缀式求值

  1. 从左向右扫描算式
  2. 遇到数字时，将数字压入堆栈，
  3. 遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素在后，次顶元素在前），并将计算结果入栈；
  4. 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

中缀式转后缀式

  1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2，记录连续数个数的inflag=0，以及记录是否出现过小数的decimalflag=0
  2. 从左至右扫描中缀表达式；
  3. 遇到操作数时，
    3.1.若intflag和decimalflag均为0时，则直接入栈s2，intflag++
    3.2.若intflag=0，则将当前数入栈
    3.3.若intflag>0并且decimalflag=0，则将s2栈顶元素左移一位加上当前数后入栈
    3.4.若intflag>0并且decimalflag=1，则将s2栈顶元素出栈后加上当前数右移intflag位后入栈
  4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
    4.1如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
    4.2否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
    4.3否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
  5. 遇到括号时：
    5.1如果是左括号“(”，则直接压入s1；
    5.2如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
    5.3重复步骤2至5，直到表达式的最右边；
  6. 遇到小数点时，记录decimalflag=1；
  7. 将s1中剩余的运算符依次弹出并压入s2；
  8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

python实现

中缀式转前缀式

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
def Infix2Prefix(self, infixstrs):
    """
    :param strs: 中缀式算式
    :return: 转换后的前缀式
    """
    infixstrs = infixstrs.replace(' ','')
    stack1 = []
    stack2 = []
    if self.isFormula(infixstrs) is not True:
        raise Exception("请输入正确格式的算式！！！")
    infixstrs = infixstrs.replace(' ', '')
    intflag = 0
    decimalflag = 0
    strs = infixstrs[::-1]
    for i in strs:
        if i.isdigit() or self.Operator[i] == 0:
            if i.isdigit() is False and self.Operator[i] == 0:
                decpart = stack2.pop()
                for j in range(intflag):
                   decpart = decpart/10
                stack2.append(decpart)
                decimalflag = 1
                intflag = 0
            else:
                if intflag == 0 and decimalflag == 0:
                    stack2.append(int(i))
                elif intflag == 0 and decimalflag == 1:
                    stack2.append(stack2.pop() + int(i))
                elif intflag > 0 :
                    dec = 1
                    for j in range(intflag):
                        dec = 10 * dec
                    stack2.append(stack2.pop() + int(i) * dec)
                intflag = intflag + 1
        else:
            intflag = 0
            decimalflag = 0
            if len(stack1) == 0  or self.Operator[i] == 3:
                stack1.append(i)
            elif self.Operator[i] == 4:
                length = len(stack1)
                for j in range(length):
                    temp = stack1.pop()
                    if self.Operator[temp] == 3:
                        break
                    stack2.append(temp)
            elif self.Operator[i] == 1 or self.Operator[i] == 2:
                if self.Operator[stack1[-1]] == 3:
                    stack1.append(i)
                elif self.Operator[stack1[-1]] <= self.Operator[i] :
                    length = len(stack1)
                    for j in range(length):
                        if len(stack1) == 0 or self.Operator[stack1[-1]] > self.Operator[i]:
                            break
                        temp = stack1.pop()
                        stack2.append(temp)
                    stack1.append(i)
                else:
                    stack1.append(i)
    while len(stack1)>0:
        stack2.append(stack1.pop())
    result = stack2
    result.reverse()
    return result

中缀式转后缀式

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
def Infix2Suffix(self, infixstrs):
    """
    :param infixstrs: 中缀式算式
    :return: 转换后的后缀式
    """
    infixstrs = infixstrs.replace(' ', '')
    stack1 = []
    stack2 = []
    if self.isFormula(infixstrs) is False:
        raise Exception("请输入正确格式的算式！！！")
    # 用来标识是否是连续的数字或者小数点
    intflag = 0
    decimalflag = 0
    for i in infixstrs:
        if i.isdigit() or self.Operator[i] == 0:
            if i.isdigit() is False and self.Operator[i] == 0:
                intflag = 0
                decimalflag = 1
            elif intflag == 0:
                stack2.append(int(i))
            elif decimalflag == 0 and intflag > 0:
                stack2.append(stack2.pop()*10 + int(i))
            elif decimalflag == 1 and intflag > 0:
                prepart = stack2.pop()
                endpart = int(i)
                for j in range(intflag):
                    endpart = endpart/10
                stack2.append(prepart + endpart)
            intflag = intflag + 1

        else:
            intflag = 0
            decimalflag = 0
            if len(stack1) == 0 or self.Operator[i] == 4:
                stack1.append(i)
            elif self.Operator[i] == 3:
                length = len(stack1)
                for j in range(length):
                    temp = stack1.pop()
                    if self.Operator[temp] == 4:
                        break
                    stack2.append(temp)

            elif self.Operator[i] == 1 or self.Operator[i] == 2:
                if self.Operator[stack1[-1]] == 4:
                    stack1.append(i)
                elif self.Operator[stack1[-1]] >= self.Operator[i]:
                    length = len(stack1)
                    for j in range(length):
                        if len(stack1) == 0 or self.Operator[stack1[-1]] < self.Operator[i]:
                            break
                        temp = stack1.pop()
                        stack2.append(temp)
                    stack1.append(i)
                else:
                    stack1.append(i)
    while len(stack1)>0:
        stack2.append(stack1.pop())
    result = stack2
    return result

算式的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def calculate(self, strs, is_Prefix=True):
    """
        根据转换后的式子计算最终的结果
    :param strs:
    :param is_Suffix: 是否是后缀式
    :return:
    """
    result = []
    if is_Prefix:
        strs = strs[::-1]
    for i in strs :
        if i in self.Operator.keys():
            operandA = result.pop()
            operandB = result.pop()
            if is_Prefix:
                calres = self.operate(operandA, operandB, i)
            else:
                calres = self.operate(operandB, operandA, i)
            result.append(calres)
        else:
            result.append(i)
    return result[0]

源码

投食