592. Fraction addition and subtraction: introduction to expression calculation

Title Description

This is a LeetCode Upper 592. Fractional addition and subtraction , The difficulty is secondary .

Tag : 「 Expression evaluation 」、「 simulation 」

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  , You need to convert it into fractions , Its denominator is  . So in the above example ,   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    .  If the denominator is , Which means that the score is actually an integer .
• The range of scores entered is .
• The molecular and denominator guarantees of the final result are Valid integers in the range of bit integers .

Expression evaluation

For convenience , Make expression by s.

Because only + and -, Therefore, there is no need to consider the priority problem , Calculate directly from front to back .

Using variables ans Refers to the result of the calculation process , Process expressions from front to back s, Each time ± molecular / The denominator Get the current operand in the form of （ If it is the first operand of the expression , And positive , Need to manually fill one +）.

Assume that the operand currently fetched is num, according to ans To calculate ：

• if ans For the empty string , explain num Is the first operand , Direct will num Assign a value to ans that will do
• if ans It's not empty string , Now calculate num and ans The result of the calculation is assigned to ans

Consider implementing a calculation function String calc(String a, String b) Calculate two operations a and b Result , One of them is ginseng a and b And the return value meet ± molecular / The denominator form .

First, by reading a and b The first character of , Get the positive and negative conditions of the two operands . If it is one positive and one negative , In the form of exchange , Make sure a Is a positive number ,b It's a negative number .

And then through parse Method to disassemble the numerator and denominator of string operands ,parse It can be realized by pointer scanning , Return the result as an array （ The first Bit is a molecular value , The first Digit denominator value ）.

Suppose the operands a The corresponding value is , The value of the operands is , Convert it to and , After operation , Then by finding the greatest common divisor gcd To simplify .

Java Code ：

class Solution {
    public String fractionAddition(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        String ans = "";
        for (int i = 0; i < n; ) {
            int j = i + 1;
            while (j < n && cs[j] != '+' && cs[j] != '-') j++;
            String num = s.substring(i, j);
            if (cs[i] != '+' && cs[i] != '-') num = "+" + num;
            if (!ans.equals("")) ans = calc(num, ans);
            else ans = num;
            i = j;
        }
        return ans.charAt(0) == '+' ? ans.substring(1) : ans;
    }
    String calc(String a, String b) {
        boolean fa = a.charAt(0) == '+', fb = b.charAt(0) == '+';
        if (!fa && fb) return calc(b, a);
        long[] p = parse(a), q = parse(b);
        long p1 = p[0] * q[1], q1 = q[0] * p[1];
        if (fa && fb) {
            long r1 = p1 + q1, r2 = p[1] * q[1], c = gcd(r1, r2);
            return "+" + (r1 / c) + "/" + (r2 / c);
        } else if (!fa && !fb) {
            long r1 = p1 + q1, r2 = p[1] * q[1], c = gcd(r1, r2);
            return "-" + (r1 / c) + "/" + (r2 / c);
        } else {
            long r1 = p1 - q1, r2 = p[1] * q[1], c = gcd(Math.abs(r1), r2);
            String ans = (r1 / c) + "/" + (r2 / c);
            if (p1 >= q1) ans = "+" + ans;
            return ans;
        }
    }
    long[] parse(String s) {
        int n = s.length(), idx = 1;
        while (idx < n && s.charAt(idx) != '/') idx++;
        long a = Long.parseLong(s.substring(1, idx)), b = Long.parseLong(s.substring(idx + 1));
        return new long[]{a, b};
    }
    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

TypeScript Code ：

function fractionAddition(s: string): string {
    const n = s.length
    let ans = ""
    for (let i = 0; i < n; ) {
        let j = i + 1
        while (j < n && s[j] != '+' && s[j] != '-') j++
        let num = s.substring(i, j)
        if (s[i] != '+' && s[i] != '-') num = "+" + num
        if (ans != "") ans = calc(num, ans)
        else ans = num
        i = j
    }
    return ans[0] == "+" ? ans.substring(1) : ans
};
function calc(a: string, b: string): string {
    const fa = a[0] == "+", fb = b[0] == "+"
    if (!fa && fb) return calc(b, a)
    const p = parse(a), q = parse(b)
    const p1 = p[0] * q[1], q1 = q[0] * p[1]
    if (fa && fb) {
        const r1 = p1 + q1, r2 = p[1] * q[1], c = gcd(r1, r2)
        return "+" + (r1 / c) + "/" + (r2 / c)
    } else if (!fa && !fb) {
        const r1 = p1 + q1, r2 = p[1] * q[1], c = gcd(r1, r2)
        return "-" + (r1 / c) + "/" + (r2 / c)
    } else {
        const r1 = p1 - q1, r2 = p[1] * q[1], c = gcd(Math.abs(r1), r2)
        let ans = (r1 / c) + "/" + (r2 / c)
        if (p1 > q1) ans = "+" + ans
        return ans
    }
}
function parse(s: string): number[] {
    let n = s.length, idx = 1
    while (idx < n && s[idx] != "/") idx++
    const a = Number(s.substring(1, idx)), b = Number(s.substring(idx + 1))
    return [a, b]
}
function gcd(a: number, b: number): number {
    return b == 0 ? a : gcd(b, a % b)
}

• Time complexity ：
• Spatial complexity ：

snacks & Extra practice

An extra meal is more suitable for the written examination interview 「 Expression evaluation 」 problem : Double stack : General solution of expression calculation problem

Last

This is us. 「 Brush through LeetCode」 The first of the series No.592 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases