aboutsummaryrefslogtreecommitdiff
path: root/fraction_addition_subtraction.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-22 19:42:58 -0600
committerJack Sangdahl <[email protected]>2024-08-22 19:42:58 -0600
commit9ec4c81450f3fb9429db5bac26d8400e4b8264d6 (patch)
treef031efbe76400f9d40d84f29164512d251bfdce4 /fraction_addition_subtraction.c
parent515d837f3d923eb5c360386e0ae03a31ddcea9b0 (diff)
downloadleetcode-9ec4c81450f3fb9429db5bac26d8400e4b8264d6.tar.gz
leetcode-9ec4c81450f3fb9429db5bac26d8400e4b8264d6.zip
592. fraction addition and subtraction
Diffstat (limited to 'fraction_addition_subtraction.c')
-rw-r--r--fraction_addition_subtraction.c88
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
+}