Force deduction solution summary 592 fraction addition and subtraction

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ：

Power button

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

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/fraction-addition-and-subtraction
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  Split the string into nodes one by one , Each node contains molecules , The denominator , And the operator .
*  If the first node starts with a negative number, the operator is negative , Otherwise, it is positive .
*  Calculate these nodes one by one from scratch , If the denominators are equal, calculate directly , Otherwise, multiply the denominator . The final result is the value of the node obtained at the end of the division process .

Code ：

public class Solution592 {

    public String fractionAddition(String expression) {

        int lastIndex = 0;
        List<Node> list = new ArrayList<>();
        char[] chars = expression.toCharArray();
        for (int i = 0; i <= chars.length; i++) {
            if (i == expression.length()) {
                Node paser = paser(expression.substring(lastIndex, i));
                list.add(paser);
                continue;
            }
            int value = chars[i];
            if (value == '-' || value == '+') {
                Node paser = paser(expression.substring(lastIndex, i));
                if (paser != null) {
                    list.add(paser);
                }
                lastIndex = i;
                continue;
            }
        }

        Node lastNode = new Node();
        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            lastNode = calculation(lastNode, node);
        }
        if (lastNode.current == 0) {
            lastNode.current2 = 1;
        } else {
            // Fractional calculation 
            int i = 2;
            while (i <= Math.abs(lastNode.current)) {
                if (lastNode.current % i == 0 && lastNode.current2 % i == 0) {
                    lastNode.current /= i;
                    lastNode.current2 /= i;
                    i = 2;
                    continue;
                }
                i++;
            }


        }

        return lastNode.current + "/" + lastNode.current2;
    }

    private Node paser(String str) {
        Node node = new Node();
        if (str.length() == 0) {
            return null;
        }
        int index = 0;
        int lastIndex = 0;
        char[] chars = str.toCharArray();
        while (index <= str.length()) {
            if (index == str.length()) {
                node.current = Integer.parseInt(str.substring(lastIndex));
                break;
            }
            int value = chars[index++];
            if (value == '-') {
                node.isAdd = false;
                lastIndex++;
                continue;
            }
            if (value == '/') {
                node.current = Integer.parseInt(str.substring(lastIndex, index - 1));
                node.current2 = Integer.parseInt(str.substring(index));
                break;
            }
        }
        return node;
    }


    private Node calculation(Node node1, Node node2) {
        Node node = new Node();
        if (node1.current2 == node2.current2) {
            node.current = node2.isAdd ? node1.current + node2.current : node1.current - node2.current;
            node.current2 = node1.current2;
            return node;
        }
        int i1 = node1.current * node2.current2;
        int i2 = node2.current * node1.current2;

        node.current = node2.isAdd ? i1 + i2 : i1 - i2;
        node.current2 = node1.current2 * node2.current2;
        return node;
    }

    public static class Node {
        boolean isAdd = true;
        int current = 0;// molecular 
        int current2 = 1;// The denominator 

    }

}