LeetCode 592. 分数加减运算（字符串+最大公约数）

示例 1:
输入:"-1/2+1/2"
输出: "0/1"

 示例 2:
输入:"-1/2+1/2+1/3"
输出: "1/3"

示例 3:
输入:"1/3-1/2"
输出: "-1/6"

示例 4:
输入:"5/3+1/3"
输出: "2/1"

说明:
输入和输出字符串只包含 '0' 到 '9' 的数字，以及 '/', '+' 和 '-'。 
输入和输出分数格式均为 ±分子/分母。
如果输入的第一个分数或者输出的分数是正数，则 '+' 会被省略掉。
输入只包含合法的最简分数，每个分数的分子与分母的范围是  [1,10]。 
如果分母是1，意味着这个分数实际上是一个整数。
输入的分数个数范围是 [1,10]。
最终结果的分子与分母保证是 32 位整数范围内的有效整数。

class Solution {
public:
    string fractionAddition(string expression) {
    	bool positive = true, founddown = false;
    	int up = 0, down = 0, a = 0, b = 0;
    	for(int i = 0; i < expression.size(); ++i)
    	{
    		if(expression[i] == '+')
    		{
    			add(up,down,a,b,positive);
                positive = true;
    			founddown = false;//找到分母
    			a=b=0;
    		}
    		else if(expression[i] == '-')
    		{
    			add(up,down,a,b,positive);
                positive = false;
    			founddown = false;
    			a=b=0;
    		}
    		else if(expression[i] == '/')
    			founddown = true;
    		else
    		{
    			if(founddown)
    				b = b*10+expression[i]-'0';
    			else
    				a = a*10+expression[i]-'0';
    		}
    	}
    	add(up,down,a,b,positive);
    	return to_string(up)+"/"+to_string(down);
    }

    void add(int &up, int &down, int a, int b, bool positive)
    {
    	if(down == 0 && b == 0)
    		return;
    	if(down == 0 && b != 0)
    	{
    		up = positive?a:-a, down = b;
    		return;
    	}
    	int t_up = 0, t_down = down*b;
    	t_up += up*b + (positive?a:-a)*down;//交叉相乘
    	int g = gcd(abs(t_up), t_down);//最大正公约数
    	up = t_up/g;
    	down = t_down/g;
    }

    int gcd(int a, int b)
    {
    	int r;
    	while(b)
    	{
    		r = a%b;
    		a = b;
    		b = r;
    	}
    	return a;
    }
};