Score addition and subtraction of force deduction and brushing questions (one question per day 7/27)

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 , The 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.

source ： Power button （LeetCode）
link

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 .
Input contains only the legal minimum score , The range of the numerator and denominator of each fraction 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].
The molecular and denominator guarantees of the final result are 32 Valid integers in the range of bit integers .

The input string is a numeric character , And there are operation symbols in the middle , And it is given in the form of fractions .
The range of numerator and denominator should be noted [1,10].
The output requirements are the simplest , And if it is a negative number, give the symbol , Otherwise, do not give .

Some details need to be paid attention to .

Today's problem-solving method , The idea is to calculate the numerator and denominator of each fraction separately . We can initialize the numerator and denominator , That is, the molecule is 0, The denominator is 1. Later we will get the numerator and denominator of the input string , Then use the formula to calculate .

Every time you get the next score , We just try to add it to our natural score , once . Of course, there are still many details . We analyze it at different levels .
below numerator molecular ,denominator The denominator , Let's initialize a fraction , In fact, that is 0, In this way, an initialization value is constructed as 0 The scores of

First of all , We need to traverse this string . This is a whole for loop , After that, all the processing logic is here for In the cycle . We need symbols to record scores , It mainly records the symbols in front of molecules , And set a variable to record symbols ., Then when we finish recording , move backward . Is the following paragraph .

long numerator = 0, denominator = 1;
        int length = expression.length();
        //  Traverse each character 
        for (int i = 0; i < length;) {
    
            //  First, record the positive and negative symbols 
            int sign = expression.charAt(i) == '-' ? -1 : 1;

            //  Encountered operator pointer backward 
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+') {
    
                i++;
            }

The following part is to calculate the numerator and denominator of traversal
Follow the previous order , The molecule must be ‘/’ In front of the symbol . So we have to judge like this .
It's important to note that here
num = num*10+expression.charAt(i++) - ‘0’;
chartAt() The function represents the character of the current index , This character, ah, we need to convert it into numbers , So subtract the characters ‘0’. But why is there a definition here num And then multiplied by the 10 Well ？
Because if the molecule is 10, It's already said , The range of our molecules can be taken as 10, Then take this molecule 10 You must extend the number of digits , If your molecule is smaller than 10 There is no need to use num Handle .

If you encounter 10, Our first acquisition is 1, Then we convert it into numbers 1, If you don't multiply 10, So now it's 1, The next one we move behind is 0, Then what you will receive here is 0, In this way, you cannot receive molecules correctly . If multiplied by 10, So from the beginning 1, here num by 1 so what , Because there's one in the back 0, When this cycle is carried out again, it will 1*10 add 0 So we can get the right molecule . The principle of the denominator below is the same .

   //  Calculate the current molecule 
            long num = 0;
            while (i < length && expression.charAt(i) != '/'){
    
                num = num*10+expression.charAt(i++) - '0';
            }
            i++;

            //  Calculate the current denominator 
            long den = 0;
            while (i < length && expression.charAt(i) != '+' && expression.charAt(i) != '-'){
    
                den = den*10+ expression.charAt(i++) - '0';
            }

            //  The denominator cannot be 0, If it does 0, The description is an integer , Here the denominator is set to 1 Just go 
            if (den == 0) {
    
                den++;
            }

The following is to add the numerator and denominator obtained each time . Then calculate a current score added to the next score .

            //  Calculate the least common multiple of the denominator 
          long lcm = denominator * den / gcd(denominator, den);
            //  Calculate new molecules 
            numerator = numerator * lcm / denominator + sign * num * lcm / den;
// //  Calculate the new denominator 
            denominator = lcm;

        }

Here we use a method to calculate the least common multiple , It calls a gcd（） Method , Look at this method

     // greatest common divisor 
    public long gcd(long a, long b) {
    
        return b == 0 ? a : gcd(b, a % b);
    }

In fact, it's the division of twists and turns .
This is a method of calculating the greatest common divisor , Also known as the greatest common factor . The principle is here .
division .
Multiply the two denominators , Then divide by the greatest common divisor, then it is the least common multiple . We finally ask for the simplest , Then the least common multiple of the two denominators here can naturally be used as a new denominator .
The new numerator is calculated by multiplying the two numerators by the least common multiple of the denominator , Then divide by their respective denominators and add the values , You can make a mathematical formula and figure it out .

Then the value thus obtained is used as the current numerator and denominator , Continue to traverse and add . The same thing .
Finally get the final value .

Finally , We need to make a simplest score .
This time is to find the greatest common divisor of denominator and numerator , Here we should pay attention to the symbols of molecules , We don't need symbols here , At the end of the symbol, we mark the variable with the previous symbol .

  long g = gcd(denominator, Math.abs(numerator));

And then construct , And return a string .
After finding the greatest common divisor, simplify the numerator and denominator , Then convert to a string , Then make a final splicing .

Complete code

 return Long.toString(numerator / g) + "/" + Long.toString(denominator / g);

Complete code

class Solution {
    
    public String fractionAddition(String expression) {
    
        //  Numerator and denominator 
        long numerator = 0, denominator = 1;
        int length = expression.length();
        //  Traverse each character 
        for (int i = 0; i < length;) {
    
            //  First, record the positive and negative symbols 
            int sign = expression.charAt(i) == '-' ? -1 : 1;

            //  Encountered operator pointer backward 
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+') {
    
                i++;
            }

            //  Calculate the current molecule 
            long num = 0;
            while (i < length && expression.charAt(i) != '/'){
    
                num = 10*num + expression.charAt(i++) - '0';
            }
            i++;

            //  Calculate the current denominator 
             long den = 0;
            while (i < length && expression.charAt(i) != '+' && expression.charAt(i) != '-'){
    
                den =  10*num + expression.charAt(i++) - '0';
            }

            //  The denominator cannot be 0, If it does 0, The description is an integer , Here the denominator is set to 1 Just go 
            if (den == 0) {
    
                den++;
            }

            //  Calculate the least common multiple of the denominator 
            long lcm = denominator * den / gcd(denominator, den);
            //  Calculate new molecules 
            numerator = numerator * lcm / denominator + sign * num * lcm / den;
            //  Calculate the new denominator 
            denominator = lcm;

        }
        //  Simplify the final result 
        long g = gcd(denominator, Math.abs(numerator));
        return Long.toString(numerator / g) + "/" + Long.toString(denominator / g);

    }

    //  greatest common divisor 
    public long gcd(long a, long b) {
    
        return b == 0 ? a : gcd(b, a % b);
    }
}

Looking at the boss' problem-solving ideas , To sum up , In addition, there is the direct regular matching of hanging hairs ,