Illustration leetcode - 592. Fraction addition and subtraction (difficulty: medium)

One 、 subject

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.

Two 、 Example

2.1> Example 1：

【 Input 】expression = "-1/2+1/2"
【 Output 】"0/1"

2.2> Example 2：

【 Input 】expression = "-1/2+1/2+1/3"
【 Output 】"1/3"

2.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 this score is actually a Integers .
• The range of scores entered is  [1,10].
• final result The numerator and denominator of are guaranteed to be  32 position   Valid integers in the range of integers .

3、 ... and 、 Their thinking

First , Through the theme , We can get a String of fractional addition and subtraction , Because only Add and Subtraction , So we can split the whole string through these two symbols , Split the score first . If it is split by a symbol , We can use it conveniently split(...) Method to split the string , But because this problem should be divided according to addition or subtraction , Then we need to adopt indexOf(...) Method to determine the specific position of the addition or subtraction symbol , Then according to the return value, the minimum （ namely ： Which one is in front ） To determine whether to add or subtract . Here is another detail , If the first score is negative , We will judge the minus sign as a minus sign , therefore , To avoid that , We from index=1 The position begins Judge . namely ： call indexOf("+", 1) and indexOf("-", 1) These two methods . The specific operation of the first symbol determination is shown in the figure below ：

Because the calculation rule of two scores is ：A/B + C/D = (AD + BC)/BD  perhaps  A/B - C/D = (AD - BC)/BD, So no matter how many fractions are added , namely ：N individual , We can all go through ((N(1) * N(2)) * N(3)) * N(4).... And so on . So when we find the first plus sign / When the minus sign , You can do that. A and B Assign a value , Then through the while Loop through the next plus sign / minus sign , After traversing , Assigned to it again C and D. here , adopt (AD + BC)/BD perhaps (AD - BC)/BD After calculating the result of two scores , Then assign the numerator of the result to A, Assign the denominator to B. And then through while Go on to the next cycle , The latest value obtained is still assigned C and D, Then calculate the two molecules . And so on . The following is the specific operation of the second round of symbol determination, as shown in the following figure ：

Then when you cycle to the last plus sign 、 When the minus sign , Attention , After this symbol , also “ Residual ” With the last score . When all the scores are calculated , We take the numerator and denominator of the final result as input , call gcd(int A, int B) Method , The purpose of this method is to seek A and B Of these two numbers greatest common divisor . Because suppose we calculate the result is 4/12, We need to cycle 4 and 12 Maximum common divisor of —— namely ：4, Then divide by the numerator and denominator respectively 4, To get the final result , namely ：1/3. The following is the specific operation of the last round of symbol determination, as shown in the following figure ：

To obtain the greatest common divisor, we can Adopt rolling division . namely ： Take the largest of the two numbers as the divisor , The smaller number is the divisor , Divide the largest number by the smaller number , If the remainder is 0, Then the lower decimal is the greatest common divisor of the two numbers , If the remainder is not 0, Divide the remainder calculated in the previous step by the smaller fraction , Until the remainder is 0, Then the greatest common divisor of these two numbers is the remainder of the previous step . Please see the following example ：

• seek 100 And 32 What is the greatest common divisor of ？
  100 ÷ 32 = 3 ... 4
  32 ÷ 4 = 8 ... 0
  therefore ： The greatest common divisor is equal to 4.
• seek 96 And 78 What is the greatest common divisor of ？
  96 ÷ 78 = 1 ... 18
  78 ÷ 18 = 4 ... 6
  18 ÷ 6 = 3 ... 0
  therefore ： The greatest common divisor is equal to 6.

Through the introduction above , We can figure out division Template code for , As shown below ：

Four 、 Code implementation

public class Solution {
    public String fractionAddition(String expression) {
        int end = 0;
        int minusIndex = expression.indexOf("-", 1); //  Prevent the first number from being negative , Think of it as a minus sign 
        int plusIndex = expression.indexOf("+", 1);
        Integer A = null, B = null, C, D;
        boolean isPlus = true; //  Is it an addition operation , Default addition 
        while (true) {
            minusIndex = minusIndex == -1 ? expression.length() : minusIndex;
            plusIndex = plusIndex == -1 ? expression.length() : plusIndex;
            String numStr = expression.substring(0, (end = Math.min(minusIndex, plusIndex)));
            if (A == null && B == null) {
                A = Integer.valueOf(numStr.split("/")[0]); //  molecular 
                B = Integer.valueOf(numStr.split("/")[1]); //  The denominator 
            } else {
                C = Integer.valueOf(numStr.split("/")[0]);
                D = Integer.valueOf(numStr.split("/")[1]);
                A = isPlus ? (A * D + B * C) : (A * D - B * C);
                B = B * D;
            }
            if (expression.length() == end) {
                break;
            }
            isPlus = plusIndex <= minusIndex;
            expression = expression.substring(end + 1);
            minusIndex = expression.indexOf("-");
            plusIndex = expression.indexOf("+");
        }

        //  Get the greatest common divisor 
        int gcd = gcd(A, B);
        return A/gcd + "/" + B/gcd;
    }

    /**  Get the greatest common divisor  */
    public int gcd(int A, int B) {
        int remainder = Math.abs(A) % Math.abs(B);
        while (remainder != 0) {
            A = B;
            B = remainder;
            remainder = A % B;
        }
        return B;
    }
}

That's all for today's article ：

Writing is not easy to , An article completed by the author in hours or even days , I only want to exchange you for a few seconds give the thumbs-up & Share .

More technical dry goods , Welcome everyone to follow the official account “ Java Muse ” ~ \(^o^)/ ~ 「 Dry cargo sharing , Update daily 」

Title source ： Power button （LeetCode）