diff options
author | Jack Sangdahl <[email protected]> | 2024-08-22 19:42:58 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-22 19:42:58 -0600 |
commit | 9ec4c81450f3fb9429db5bac26d8400e4b8264d6 (patch) | |
tree | f031efbe76400f9d40d84f29164512d251bfdce4 /fraction_addition_subtraction.c | |
parent | 515d837f3d923eb5c360386e0ae03a31ddcea9b0 (diff) | |
download | leetcode-9ec4c81450f3fb9429db5bac26d8400e4b8264d6.tar.gz leetcode-9ec4c81450f3fb9429db5bac26d8400e4b8264d6.zip |
592. fraction addition and subtraction
Diffstat (limited to 'fraction_addition_subtraction.c')
-rw-r--r-- | fraction_addition_subtraction.c | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/fraction_addition_subtraction.c b/fraction_addition_subtraction.c new file mode 100644 index 0000000..eec45a2 --- /dev/null +++ b/fraction_addition_subtraction.c @@ -0,0 +1,88 @@ +// 592. Fraction Addition and Subtraction +#include "leetcode.h" + +/* + * given a string 'expression' representing an expression of fraction addition + * and subtraction, return the calculation result in string format. the final + * result should an irreducible fraction. if your final result is an integer, + * change it to the format of a fraction has a denominator 1. so in this case, 2 + * should be converted to "2/1" + */ + +int gcd(int a, int b) { + if (!(a % b)) + return b; + return gcd(b, a % b); +} + +int numerator(int i, char *exp) { + char *tmp = ""; + while (exp[i] != '/') { + tmp += exp[i]; + i++; + } + return atoi(tmp); +} + +int denominator(int i, char *exp) { + char *tmp = ""; + while (exp[i] != '/') { + tmp += exp[i]; + i++; + } + return atoi(tmp); +} + +char *fractionAddition(char *expression) { + int s1 = 1, i = 0; + if (expression[0] == '-') { + s1 = -1; + i++; + } + int n1 = numerator(i, expression); + i++; + int d1 = denominator(i, expression); + while (i < strlen(expression)) { + int s2 = expression[i] == '-' ? -1 : 1; + i++; + int n2 = numerator(i, expression); + i++; + int d2 = denominator(i, expression); + int lcm = (d2 * d1) / gcd(d1, d2); + n1 = (s1 * n1 * (lcm / d1) + s2 * n2 * (lcm / d2)); + d1 = lcm; + if (n1 < 0) { + s1 = -1; + n1 *= -1; + } else + s1 = 1; + } + int g = gcd(n1, d1); + if (g > 1) { + n1 /= g; + d1 /= g; + } + int len = 0; + len += (s1 == -1) ? 1 : 0; + len += snprintf(NULL, 0, "%d", n1); + len += 1; + len += snprintf(NULL, 0, "%d", d1); + char *res = (char *)malloc(len + 1); + res[0] = '\0'; + if (s1 == -1) + strcat(res, "-"); + char buffer[50]; + sprintf(buffer, "%d", n1); + strcat(res, buffer); + strcat(res, "/"); + sprintf(buffer, "%d", d1); + strcat(res, buffer); + return res; +} + +int main() { + char *e1 = "-1/2+1/2", *e2 = "-1/2+1/2+1/3", *e3 = "1/3-1/2"; + printf("%s\n", fractionAddition(e1)); // expect: 0/1 + printf("%s\n", fractionAddition(e2)); // expect: 1/3 + printf("%s\n", fractionAddition(e3)); // expect: -1/6 +} |