<p>Given a string <code>expression</code> representing an expression of fraction addition and subtraction, return the calculation result in string format.</p>

<p>The final result should be an <a href="https://en.wikipedia.org/wiki/Irreducible_fraction" target="_blank">irreducible fraction</a>. If your final result is an integer, change it to the format of a fraction that has a denominator <code>1</code>. So in this case, <code>2</code> should be converted to <code>2/1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;-1/2+1/2&quot;
<strong>Output:</strong> &quot;0/1&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;-1/2+1/2+1/3&quot;
<strong>Output:</strong> &quot;1/3&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;1/3-1/2&quot;
<strong>Output:</strong> &quot;-1/6&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The input string only contains <code>&#39;0&#39;</code> to <code>&#39;9&#39;</code>, <code>&#39;/&#39;</code>, <code>&#39;+&#39;</code> and <code>&#39;-&#39;</code>. So does the output.</li>
	<li>Each fraction (input and output) has the format <code>&plusmn;numerator/denominator</code>. If the first input fraction or the output is positive, then <code>&#39;+&#39;</code> will be omitted.</li>
	<li>The input only contains valid <strong>irreducible fractions</strong>, where the <strong>numerator</strong> and <strong>denominator</strong> of each fraction will always be in the range <code>[1, 10]</code>. If the denominator is <code>1</code>, it means this fraction is actually an integer in a fraction format defined above.</li>
	<li>The number of given fractions will be in the range <code>[1, 10]</code>.</li>
	<li>The numerator and denominator of the <strong>final result</strong> are guaranteed to be valid and in the range of <strong>32-bit</strong> int.</li>
</ul>

class Solution {
public:
    int gcd( int a, int b ){
        if( a == 0 ){
            return b;
        }
        if( b == 0 ){
            return a;
        }
        if( a == b ){
            return a;
        }
        if( a > b ){
            return gcd( a-b,b);
        } else {
           return gcd( a,b-a ); 
        }
    }
    int getDigit( string& str, int pos){
        int num = 0;
        while( isdigit( str[pos] ) ){
            num = num * 10 + str[pos]-'0';
            ++pos;
        }
        return num;

    }
    vector<string> parseString( string& expression ){
        vector<string> strs; 
        for( int i = 0; i<expression.size(); i++ ){

            string str = "";
            bool updated = false;
            if( expression[i] == '-' || expression[i] == '+' ){
                str  = expression[i]  + str;
                ++i;
                updated = true;
            } 
            while( isdigit( expression[i] ) ){
                //cout<< " digit " << expression[i] << endl;
                str += expression[i];
                ++i;
                updated = true;
            }
            str += expression[i];
            ++i;
            while( isdigit( expression[i] ) ){
                str += expression[i];
                ++i;
                updated = true;
                //cout<< " digit " << expression[i] << endl;
            }
            if( updated ) --i;
            //cout<< " parsed: " << str << endl;
            strs.push_back( str);
        }
        return strs;   
    }

    string fractionAddition(string expression) {
        vector<string> strs = parseString( expression );
        int num = 0;
        int deno = 1;
        for( int i =0; i<strs.size(); i++ ){
             cout<< " str " << strs[i] << endl;
            int sign = 1;
            int pos = 0;
            if( strs[i][0] =='-'){
                sign = -1;
                ++pos;
            }
            if( strs[i][0] =='+'){
                ++pos;
            }
            int currNum = 0;
            while( isdigit( strs[i][pos] ) ){
                currNum = currNum * 10 + strs[i][pos]-'0';
                cout<< " currNum " << currNum << endl;
                ++pos;
            }
            ++pos;
            int currDeno=0;
            while( isdigit( strs[i][pos] ) ){
                currDeno = currDeno * 10 + strs[i][pos]-'0';
                ++pos;
            }
            currNum = currNum * sign;
            cout<< " currNum/currDeno " << currNum << "/" << currDeno<< endl;
            num = currNum * deno + currDeno * num;
            deno = deno * currDeno;
            int mult = gcd( abs(num),deno); 
            cout << " bf " << num << "/" << deno << endl;
            cout << " gcd " << mult << endl; 
            num = num / mult;
            deno = deno / mult;
            cout << " af "<< num << "/" << deno << endl;
        }
        string sr = "";
        sr += to_string( num ) + "/" + to_string( deno );
        return sr;
    }
};
8100