[leetcode] 592. Fraction addition and subtraction

subject

592. Fractional addition and subtraction

Given a string representing the addition and subtraction of fractions expression , You need to return a string calculation .

This result should be an irreducible score , namely Simplest fraction . If the final result is an integer , for example 2, You need to convert it into fractions , Its denominator is 1. So in the above example , 2 Should be converted to 2/1.

Example 1:

 Input : expression = "-1/2+1/2"
 Output : "0/1"

Example 2:

 Input : expression = "-1/2+1/2+1/3"
 Output : "1/3"

Example 3:

 Input : expression = "1/3-1/2"
 Output : "-1/6"

Tips :

• Input and output strings contain only '0' To '9' The number of , as well as '/', '+' and '-'.
• The input and output fractional formats are ± molecular / The denominator . If the first score entered or the score output is a positive number , be '+' Will be omitted .
• The input only contains legal Simplest fraction , Of each score molecular And The denominator The range is [1,10]. If the denominator is 1, Which means that the score is actually an integer .
• The range of scores entered is [1,10].
• final result The numerator and denominator of are guaranteed to be 32 Valid integers in the range of bit integers .

Ideas

• Traversal string , adopt =- The symbol separates the string into multiple fractional operations
• The method of fractional operation is ：
  • Divide fractions into numerators and denominators , And convert it to an integer
  • The product of two denominators
  • Carry out operations
  • Apposition ： Divide the numerator and denominator by their greatest common factor

Code

class Solution:
    def fractionAddition(self, expression: str) -> str:
        def calc(a: str, b: str, operator: str):
            operands = a.split("/")
            a1 = int(operands[0])
            a2 = int(operands[1])

            operands = b.split("/")
            b1 = int(operands[0])
            b2 = int(operands[1])

            b3 = a2*b2
            a3 = a1 * b2 + a2*b1 if operator == "+" else a1 * b2 - a2*b1
            mod = math.gcd(a3,b3)
            a3 //= mod
            b3 //= mod
            return F"{
      a3}/{
      b3}"
        if expression[0] == "-": expression = "0/1"+expression
        
        if len(expression) <3: return expression
        i = 0
        while i < len(expression) and expression[i] not in "+-": i += 1
        ret = expression[:i]

        while i < len(expression):
            start = i
            i+=1
            while i < len(expression) and expression[i] not in "+-": i += 1
            ret = calc(ret, expression[start+1:i], expression[start])
        return ret

Complexity

• Time complexity ：$O(n+\log C)$
• Spatial complexity ：$O(1)$