Fraction Addition and Subtraction LeetCode solution in C++

1
class Solution {
2
 public:
3
  string fractionAddition(string expression) {
4
    int res_num = 0;   // keep track of numerator
5
    int res_denom = 1; // keep track of denominator
6
    char sign = '+';   // keep track of sign
7

8
    for (int i = 0; i < expression.size(); i++) { // parse the expression string
9
      int next_num = 0;
10
      int next_denom = 0;
11
      if (expression[i] == '+' || expression[i] == '-') // updating
12
        sign = expression[i];
13
      else {
14
        int j = i + 1;
15
        while (j < expression.size() && expression[j] != '/') j++;
16
        build next numerator next_num = stoi(expression.substr(i, j - i));
17
        int k = j + 1;
18
        while (k < expression.size() && expression[k] >= '0' && expression[k] <= '9')
19
          k++; // build next denominator
20
        next_denom = stoi(expression.substr(j + 1, k - (j + 1)));
21
        if (res_denom != next_denom) { // update result numerator and
22
                                       // denominator
23
          res_num *= next_denom;
24
          next_num *= res_denom;
25
          res_denom *= next_denom;
26
        }
27
        if (sign == '+')
28
          res_num += next_num;
29
        else
30
          res_num -= next_num;
31
        i = k - 1;
32
      }
33
    }
34
    return lowestFraction(res_num,
35
                          res_denom); // put the fraction into lowest terms and return as string
36
  }
37

38
 private:
39
  int findGCD(int a, int b) { // find Greatest Common Denominator
40
    if (b == 0) return a;
41
    return findGCD(b, a % b);
42
  }
43

44
  string lowestFraction(int num,
45
                        int denom) { // use GCD to put fraction into lowest
46
                                     // terms and return as string
47
    int gcd;
48
    gcd = findGCD(num, denom);
49
    num /= gcd;
50
    denom /= gcd;
51
    if (denom < 0) {
52
      denom *= -1;
53
      num *= -1;
54
    }
55
    return to_string(num) + '/' + to_string(denom);
56
  }
57
};