[592. Fraction addition and subtraction]

source ： Power button （LeetCode）

describe ：

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 Division Count , 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 .

Method ： simulation

Code ：

class Solution {
    
public:
    string fractionAddition(string expression) {
    
        long long denominator = 0, numerator = 1; //  molecular , The denominator 
        int index = 0, n = expression.size();
        while (index < n) {
    
            //  Read molecules 
            long long denominator1 = 0, sign = 1;
            if (expression[index] == '-' || expression[index] == '+') {
    
                sign = expression[index] == '-' ? -1 : 1;
                index++;
            }
            while (index < n && isdigit(expression[index])) {
    
                denominator1 = denominator1 * 10 + expression[index] - '0';
                index++;
            }
            denominator1 = sign * denominator1;
            index++;

            //  Read denominator 
            long long numerator1 = 0;
            while (index < n && isdigit(expression[index])) {
    
                numerator1 = numerator1 * 10 + expression[index] - '0';
                index++;
            }

            denominator = denominator * numerator1 + denominator1 * numerator;
            numerator *= numerator1;
        }
        if (denominator == 0) {
    
            return "0/1";
        }
        long long g = gcd(abs(denominator), numerator); //  Get the greatest common divisor 
        return to_string(denominator / g) + "/" + to_string(numerator / g);
    }
};

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：5.8 MB, In all C++ Defeated in submission 90.06% Users of
Complexity analysis
Time complexity ： O(n + logC), among n Is string expression The length of , C Is the maximum value of the numerator denominator of the result before simplification . Finding the greatest common divisor requires O(logC).
Spatial complexity ： O(1).
author：LeetCode-Solution