题干

给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。

这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为1。所以在上述例子中, 2 应该被转换为 2/1。

image-20220727212728977

思路

本题主要考量的是对字符串的操作和数学理解。

首先，对字符串的操作核心在于：

  • 判断单个字符串是符号还是数字
  • 对数字进行读取
  • 根据符号判断运算规则

而数学理解在于如何计算分式，实际上，直接对其进行操作(每过一个操作符进行一次算数操作)会导致一个问题，那就是最终得到的结果是一个整数或浮点数，将其转化为分式难免会产生数据丢失，而且较为困难。

我们可以记录分子numerator和分母denominator的量，通过约分得到最终的分式结果，就像中学题直接处理分数一般。

设两个数a,b的分子分母为：an,ad,bn,bda_n,a_d,b_n,b_d，分式相加公式如下：

new=an∗bd+bn∗adad∗bdnew=\frac{a_n*b_d+b_n*a_d}{a_d*b_d}

最后通过约分得到最终结果。

代码

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
class Solution:
    def fractionAddition(self, expression: str) -> str:

        # d1*d2*d3
        # (n1*d2+n2*d1)*d3+n3*(n1*d2+n2*d1)
        # gcd(n,d)

        numerator,denominator=0,1
        i=0

        while i<len(expression):

            # determine the sign
            sign=1 # maybe begin without "+"
            if expression[i] in ["+","-"]:
                if expression[i]=="-":
                    sign=-1
                i+=1

            # determine the numerator            
            nume_=0
            while i<len(expression) and expression[i].isdigit():
                nume_=nume_*10+int(expression[i])
                i+=1

            # determine the denominator
            i+=1
            deno_=0
            while i<len(expression) and expression[i].isdigit():
                deno_=deno_*10+int(expression[i])
                i+=1
            
            # calculate fraction1 and fraction2
            numerator=numerator*deno_+sign*nume_*denominator
            denominator*=deno_

            # next loop
        
        if denominator==0:
            return "0/1"

        g=gcd(numerator,denominator)
        return f"{numerator//g}/{denominator//g}"

注意点

  • 在做字符串操作时，一定要明确每一步到了哪个位置，该位置上要进行什么操作。
  • 注意意群的规律