LeetCode中等题之分数加减运算

题目

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

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

示例 1:

输入: expression = “-1/2+1/2”
输出: “0/1”
示例 2:

输入: expression = “-1/2+1/2+1/3”
输出: “1/3”
示例 3:

输入: expression = “1/3-1/2”
输出: “-1/6”

提示:

输入和输出字符串只包含 ‘0’ 到 ‘9’ 的数字，以及 ‘/’, ‘+’ 和 ‘-’。
输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数，则 ‘+’ 会被省略掉。
输入只包含合法的最简分数，每个分数的分子与分母的范围是 [1,10]。 如果分母是1，意味着这个分数实际上是一个整数。
输入的分数个数范围是 [1,10]。
最终结果的分子与分母保证是 32 位整数范围内的有效整数。

来源：力扣（LeetCode）

解题思路

  利用一个简单的栈进行模拟，由于题目中要求的计算只有加减法，所以我们默认加法然后每个数字自带符号用python自带的eval进行计算，每次两个数字进行求和之后再放入栈中直到栈中的元素剩下一个为止。

class Solution:
    def fractionAddition(self, expression: str) -> str:
        if expression[0].isdigit():
            expression='+'+expression
        expression+='+'
        temp=expression[0]
        stack=[]
        for i in expression[1:]:
            if i=='-' or i=='+':
                stack.append(temp)
                temp=i
                continue
            temp+=i
        while len(stack)!=1:
            left=stack.pop()
            right=stack.pop()
            lnumerator,ldenominator=left[1:].split('/')
            rnumerator,rdenominator=right[1:].split('/')
            denominator=eval(ldenominator+'*'+rdenominator)
            numerator=eval(rdenominator+'*'+left[0]+lnumerator+'+'+ldenominator+'*'+right[0]+rnumerator)
            divisor=math.gcd(denominator,numerator)
            denominator//=divisor
            numerator//=divisor
            if numerator>=0:
                stack.append('+'+str(numerator)+'/'+str(denominator))
            else:
                stack.append(str(numerator)+'/'+str(denominator))
        ans=stack.pop()
        return ans[1:] if ans[0]=='+' else ans

            

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