[数据结构与算法]【leetcode】【2022/7/27】592. 分数加减运算

问题描述：

• 字符串中只包含分数和加减运算，返回字符串的计算结果。
  • 输入和输出分数格式均为 ±分子/分母。
  • 第一个分数的正号会被省略。
  • 输入中只包含合法的最简分数。

解题思路：

• 字符串解析求公式，一般都是直接做模拟。
  • 利用变量 num 来保存当前数值。
  • 利用变量 neg 来保存当前数的正负（注意分母均是正数）。
  • 把分数用分母和分子两个数值来表示。
• 模拟思路如下：【可以用状态机的状态转移思想来理解整个模拟过程】
  1. 遇到 + 或 - ，说明前一个分数的分母结束保存【把当前保存数值 num 存入分母中，并将 num 置为 0】，接着根据符号将 neg 置位；
     • 与此同时还需要将前两个分数相加。【两分数计算后求得分子和分母的 gcd 结果（即最大公约数），根据结果进行约分】
  2. 遇到 / ，说明当前分数的分子结束保存【把当前保存数值 num 存入分子中，并将 num 置为 0】
  3. 遇到数值就更新 num 即可。
• 本题稍微巧妙一点的方法在于如何处理边界。
  • 如在处理 -1/2 +1/2 的时候，可以认为是 0/1 -1/2 +1/2 的计算结果，如此便不用特别处理第一个分数。
  • 如处理 1/3 -1/2 的时候，可以认为是 +1/3 -1/2 ，即往前面补多一个正号，保证第一个分数的处理和后面的处理是一致的。【即使 -1/2 +1/2 也可以视为 + -1/2 +1/2】【同理可以在最后加上正号。逻辑上就是为了方便处理字符串中最后一个分母】

代码实现：

class Solution
{
private:
    // lu：left up，第一个分数的分子
    // ld：left down，第一个分数的分母
    // ru：right up，第二个分数的分子
    // rd：right down，第二个分数的分母
    int lu = 0, ld = 1, ru = 0, rd = 1;
    int gcd(int a, int b)
    {
        return b>0 ? gcd(b,a%b):a;
    }
    void count()
    {
        int u = lu * rd + ru * ld;
        int d = ld * rd;
        lu = u;
        ld = d;
        int tmp = gcd(abs(lu), ld);
        if(tmp == 0) return;
        lu /= tmp;
        ld /= tmp;
    }
public:
    string fractionAddition(string expression)
    {
        int m = expression.size();
        int neg = 1;
        int num = 0;
        for(int i = -1; i <= m; ++i)
        {
            char ch = i == -1 or i == m? '+' : expression[i];
            if(ch == '-' or ch == '+')
            {
                if(i != -1 and i != 0) rd = num;
                count();
                neg = ch == '-' ? -1 : 1;
                num = 0;
            }
            else if(ch == '/')
            {
                ru = num * neg;
                num = 0;
            }
            else if(ch >= '0' and ch <= '9')
                num = num * 10 + (int)(ch - '0');
        }
        string ans = lu < 0 ? "-" : "";
        ans += to_string(abs(lu)) + "/" + to_string(ld);
        return ans;
    }
};