Convert to fractions then do school Math||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThis question has 2 parts that must be done.\n1.  Convert the expression to a sequnece 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis question has 2 parts that must be done.\n1.  Convert the expression to a sequnece of fractions; in fact pairs of ints (hard way using many branches/ easy way using stringstream)\n2. Use school math to perform the fraction add/subtract  such as xp/xq+yp/yq=p/q, do not forget to find gcd to divide p & q to get the irreducible fraction.\n\nC++, Python codes are made.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on English subtitles if necessary]\n[https://youtu.be/Al-FZ4wPmyY?si=sDCIyhLsvFQTfbHa](https://youtu.be/Al-FZ4wPmyY?si=sDCIyhLsvFQTfbHa)\n1. The fractions are hold in the container `fraction` in an array over int pairs.\n2. Define the function `convert(expression)` to convert expression to fraction; in the implementation, one can use 1-pass transversal to deal \'+\', \'-\',\'/\' and digit characters \'0\'-\'9\'.\n3. Define the function `add(x, y)` whose task is to do the fraction addition as follows\n```\nauto [xp, xq]=x;\nauto [yp, yq]=y;\nlong long q=xq*yq;// current common denominator\nlong long p=xp*yq+xq*yp;\nlong long g=gcd(p, q);\nreturn {p/g, q/g};//Fraction reduction\n```\n4. In `fractionAddition`, 1st call `fraction=convert(expression);` then use a loop to proceed `ans=add(ans, f)` for `f` in ``fraction`, the initial value for `f` is `{0,1}` which is corresponding to `0/1`.\n5. Convert the int pair `ans` to the answering format string.\n6. The other version for `convert` is using std::stringstream which is a  good class dealing string & simplies the code.\n7. Python\'s convert is done with regex.\n# Why not compute LCM as the common denominator?\nFor 2 rationals `x=xp/xq, y=yp/yq`,\nIf taking `d=lcm(xq, yq)=xq*yq/gcd(xq, yq)`.\nThe result `p/q` for `x+y` (`x-y`) using `d` may be  reducible or irreducible depending whether `gcd(p,q)>1` or not.\nIf irreducible, you\'ve luck; otherwise it needs 2 more divisions; the fraction is represented by the int pair `(p/g, p/g)`.\nThis method needs 2x computations for gcd & more multiplications/divisions; it\'s more expensive than my method.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(sz+|add|\\times fz)$ where $sz=|expression|, fz=|fraction|$. Each `add` operation needs 3 multiplications 1 add/subtract & 1 gcd (system builtin gcd, it is supposed having several divisions due to Euclidean algorithm) & 2 divisions.  \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(fz)$\n# Code|| C++ 0ms beats 100%\n```C++ []\nclass Solution {\npublic:\n    using int2=pair<int, int>;\n    void print(auto& f){\n        for(auto& [x, y]: f) cout<<"("<<x<<","<<y<<")";\n        cout<<endl;\n    }\n\n    vector<int2> convert(string& expression){\n        vector<int2> fraction;\n        int sz=expression.size(), x=0, sgn=1;\n        char c=expression[0];\n        switch(c){\n            case \'+\':break;\n            case \'-\': sgn=-1; break;\n            default: x=c-\'0\';\n        }\n        int prev=0;\n        for(int i=1; i<sz; i++){\n            c=expression[i];\n            while(c>=\'0\'){\n                x=10*x+(c-\'0\');\n                if (i==sz-1) break;\n                c=expression[++i];\n            //    cout<<x<<", ";\n            }\n            switch(c){\n                case \'+\':\n                    fraction.emplace_back(prev, x);\n                    sgn=1; \n                    x=0;\n                    break;\n                case \'-\':\n                    fraction.emplace_back(prev, x); \n                    sgn=-1; \n                    x=0;\n                    break;\n                case \'/\':\n                    prev=x*sgn;\n                    x=0;\n            }  \n        }\n        // dealing with i=sz-1\n        fraction.emplace_back(prev, x);\n        return fraction;\n    }\n    int2 add(int2& x, int2& y){\n        auto [xp, xq]=x;\n        auto [yp, yq]=y;\n        long long q=xq*yq;\n        long long p=xp*yq+xq*yp;\n        long long g=gcd(p, q);\n        return {p/g, q/g};\n    }\n    \n    string fractionAddition(string& expression) {\n        auto fraction=convert(expression);\n    //    print(fraction);\n        int fz=fraction.size();\n        int2 ans={0, 1};\n        for(auto& f: fraction){\n            ans=add(ans, f);\n        }\n        string s=to_string(ans.first)+"/"+to_string(ans.second);\n        return s;\n    }\n};\n```\n```Python []\nclass Solution:\n    def fractionAddition(self, expression: str) -> str:\n        def convert(exp):\n            fraction=[]\n            x, sgn, prev=0, 1, 0\n            c=exp[0]\n            if c==\'-\': sgn=-1\n            elif c==\'+\': pass\n            else: x=ord(c)-ord(\'0\')\n\n            i, sz= 1, len(exp)\n            while i<sz:\n                c=exp[i]\n                while ord(c)>=ord(\'0\'):\n                    x=10*x+(ord(c)-ord(\'0\'))\n                    if i==sz-1: break\n                    i+=1\n                    c=exp[i]\n\n                if c==\'+\':\n                    fraction+=[(prev, x)]\n                    sgn=1\n                    x=0\n                elif c==\'-\':\n                    fraction+=[(prev, x)]\n                    sgn=-1\n                    x=0\n                elif c==\'/\':\n                    prev=x*sgn\n                    x=0\n                i+=1\n            fraction+=[(prev, x)]\n            return fraction\n\n        def add(x, y):\n            q=x[1]*y[1]\n            p=x[0]*y[1]+x[1]*y[0]\n            g=gcd(p, q)\n            return (p//g, q//g)\n\n        fraction=convert(expression)\n        ans=(0, 1)\n        for f in fraction:\n            ans=add(ans, f)\n        return str(ans[0])+\'/\'+str(ans[1])\n            \n\n        \n```\n# C++ convert using stringstream\n```\n    vector<int2> convert(string& expression) {\n        vector<int2> fraction;\n        stringstream ss(expression);\n        char op;\n        int num, denom;\n\n        while (ss>>num>>op>>denom) {\n            fraction.emplace_back(num, denom);\n        //    cout<<num<<","<<op<<denom<<endl;\n        }\n        return fraction;\n    }\n```\n# Python  convert using regex\n```\nimport re\ndef convert(expression):\n    regex=r"([+-]?\\d+)/(\\d+)"\n\n    matches=re.findall(regex, expression)\n\n    fraction = [(int(num), int(den)) for num, den in matches]\n    return fraction\n```
['Math', 'String', 'Simulation', 'C++', 'Python3']