C++ Solution


  • 0
    class Solution {
    public:
        string fractionAddition(string expr) {
            vector<pair<int, int>> nums = split(expr);
            pair<int, int> res(0, 1);
            for (int i = 0; i < nums.size(); i++) {
                res = add(res, nums[i]);
            }
            res = reduce(res);
            return serialize(res);
        }
    
    private:
        vector<pair<int, int>> split(string s) {
            vector<pair<int, int>> nums;
            int start = 0;
            for (int i = 1; i < s.length() + 1; i++) {
                if (i == s.length() || s[i] == '+' || s[i] == '-') {
                    string tok = s.substr(start, i);
                    if (i != s.length()) {
                        start = s[i] == '-' ? i : i + 1;
                    }
                    pair<int, int> num = parse(tok);
                    nums.push_back(num);
                }
            }
            return nums;
        }
        
        pair<int, int> parse(string& frac) {
            int div = frac.find('/');
            string a = frac.substr(0, div);
            string b = frac.substr(div + 1);
            return pair<int, int>(stoi(a), stoi(b));
        }
    
        pair<int, int> reduce(pair<int, int> a) {
            pair<int, int> r = a;
            for (int i = 2; i <= abs(r.first) && i <= abs(r.second); i++) {
                if (r.first % i == 0 && r.second % i == 0) {
                    r.first /= i;
                    r.second /= i;
                    i--;
                }
            }
            if (r.first == 0) {
                r.second = 1;
            }
            return r;
        }
    
        pair<int, int> add(pair<int, int> a, pair<int, int> b) {
            return a.second == b.second ? pair<int, int>(a.first + b.first, a.second)
                : pair<int, int>(a.first * b.second + b.first * a.second, a.second * b.second);
        }
        
        string serialize(pair<int, int> a) {
            return to_string(a.first) + "/" + to_string(a.second);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.