关于后端:592-分数加减运算-表达式计算入门题

题目形容

这是 LeetCode 上的 592. 分数加减运算 ，难度为 中等。

Tag :「表达式计算」、「模仿」

给定一个示意分数加减运算的字符串 expression，你须要返回一个字符串模式的计算结果。

这个后果应该是不可约分的分数，即最简分数。如果最终后果是一个整数，例如 $2$，你须要将它转换成分数模式，其分母为 $1$。所以在上述例子中, $2$ 应该被转换为 2/1。

示例 1:

输出: expression = "-1/2+1/2"

输入: "0/1"

示例 2:

输出: expression = "-1/2+1/2+1/3"

输入: "1/3"

示例 3:

输出: expression = "1/3-1/2"

输入: "-1/6"

提醒:

• 输出和输入字符串只蕴含 '0' 到 '9' 的数字，以及 '/', '+' 和 '-'。
• 输出和输入分数格局均为 ±分子 / 分母。如果输出的第一个分数或者输入的分数是负数，则 '+' 会被省略掉。
• 输出只蕴含非法的最简分数，每个分数的分子与分母的范畴是  $[1,10]$。如果分母是 $1$，意味着这个分数实际上是一个整数。
• 输出的分数个数范畴是 $[1,10]$。
• 最终后果的分子与分母保障是 $32$ 位整数范畴内的无效整数。

表达式计算

为了不便，令 expression 为 s。

因为给定的表达式中只有 + 和 -，因而毋庸思考优先级问题，间接从前往后计算即可。

应用变量 ans 代指计算过程中的后果，从前往后解决表达式 s，每次以 ±分子 / 分母 的模式取出以后操作数（若为表达式的首个操作数，且为负数时，须要手动补一个 +）。

假如以后取出的操作数为 num，依据 ans 的状况进行运算：

• 若 ans 为空串，阐明 num 是首个操作数，间接将 num 赋值给 ans 即可
• 若 ans 不为空串，此时计算 num 和 ans 的计算结果赋值给 ans

思考实现一个计算函数 String calc(String a, String b) 计算两个操作 a 和 b 的后果，其中入参 a 和 b 以及返回值均满足 ±分子 / 分母 模式。

首先通过读取 a 和 b 的首个字符，失去两操作数的正负状况。若为一正一负，通过替换的模式，确保 a 为负数，b 为正数。

而后通过 parse 办法拆解出字符串操作数的分子和分母，parse 应用指针扫描的形式实现即可，以数组模式将后果返回（第 $0$ 位为分子数值，第 $1$ 位分母数值）。

假如操作数 a 对应的值为 $\frac{p[0]}{p[1]}$，操作数的值为 $\frac{q[0]}{q[1]}$，先将其转换为 $\frac{p[0] \times q[1]}{p[1] \times q[1]}$ 和 $\frac{q[0] \times p[1]}{q[1] \times p[1]}$，进行运算后，再通过求最大公约数 gcd 的形式进行化简。

Java 代码：

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 代码：

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)
}

• 工夫复杂度：$O(n)$
• 空间复杂度：$O(1)$

加餐 & 加练

加餐一道更贴合口试面试的「表达式计算」问题 : 双栈 : 表达式计算问题的通用解法 🎉🎉

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.592 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布