#include "stdlib.h" #include "strings.h" typedef struct { char * n, *d; } SFrac; #define false 0 #define true 1 //String uteis char* newString(char * s, int tamanho); void delete(char* s, int pos, int qtde); void leftConcat(char *a, char *b); void charLeftConcat(char c, char * b); void Copy(char * destino, char *s, int partir, int qtde); char * copy(char *s, int partir, int qtde); int pos(char sub, char * s); void ZeroLTrim(char *s); char* Valida(char* s); char* FracValida(char* s); //as funçoes abaixo já partem de q as strings sao válidas char* Soma(char* y, char *z); char* Subtrai(char* y, char *z); char* Multiplica(char* a, char *b); void Divide(char * alinha, char * blinha, char * q, char *r); char* Potencia(char* a, char *b); char* mdc(char * x, char * y); char* SNumAbs(char* a); short SNumCompare(char* a, char *b); char* SNumOposto(char *s); //fraçoes SFrac Str2Frac(char *x); void FracReduz(char *x); char* FracAdd(char *x, char *y); char* FracSub(char *x, char *y); char* FracMul(char *x, char *y); char* FracDiv(char *x, char *y); char* FracOposto(char *s); short FracCompare(char *x, char *y); char* FracAbs(char *a); //IMPLEMENTATION char* newString(char * s, int tamanho) { char * Result = malloc(tamanho + 1); strcpy(Result, s); return Result; } void delete(char* s, int pos, int qtde) { int i; for(i = pos - 1; s[i]; i++) s[i] = s[i + qtde]; } void leftConcat(char *a, char *b) { int i = strlen(b); int j = strlen(a); for (; i >= 0; i--) b[i + j] = b[i]; for(i = 0; i < j; i++) b[i] = a[i]; } void charLeftConcat(char c, char * b) { char letra[2]; letra[0] = c; letra[1] = 0; leftConcat(letra, b); } void Copy(char * destino, char *s, int partir, int qtde) { int i; for (i = 0; i <= qtde - 1; i++) destino[i] = s[partir - 1 + i]; destino[qtde] = 0; } char * copy(char *s, int partir, int qtde) { char * Result = newString("", qtde); Copy(Result, s, partir, qtde); return Result; } int pos(char sub, char * s) { int i = 0; while (s[i] && (s[i] != sub)) i++; if (s[i] == sub) return i; else return 0; } void ZeroLTrim(char *s) { while ((s[0] == '0') && (s[1] != '/')) delete(s, 1, 1); } char* Soma(char* y, char *z) { if (y[0] == '0') return newString(z, strlen(z)); if (z[0] == '0') return newString(y, strlen(y)); int i, x; char carry, minus, *Result; i = strlen(y); x = strlen(z); if (x > i) i = x; char * a = newString(y, i); char * b = newString(z, i); minus = false; if (a[0] == '-') { delete(a, 1, 1); if (b[0] == '-') { delete(b, 1, 1); // -a + (-b) == -(a + b) minus = true; } else { // -a + b == b - a Result = Subtrai(b, a); free(a); free(b); return Result; } } else if (b[0] == '-') { delete(b, 1, 1); // a + (-b) == a - b Result = Subtrai(a, b); free(a); free(b); return Result; } if (strlen(a) > strlen(b)) { Result = a; a = b; b = Result; } x = strlen(b); while (strlen(a) < x) leftConcat("0", a); //008765 //123400 i = x; while ((i > 1) && (b[i-1] == '0')) i--; Result = malloc(x + 3); Copy(Result, a, i + 1, x - i); delete(a, i + 1, x - i); delete(b, i + 1, x - i); carry = 0; for (; i >= 1; i--) { x = a[i-1] - 48 + b[i-1] - 48 + carry; if (x >= 10) { carry = 1; x -= 10; } else carry = 0; charLeftConcat(x + 48, Result); } if (carry != 0) leftConcat("1", Result); if (minus) leftConcat("-", Result); free(a); free(b); return Result; } char* Subtrai(char* y, char *z) { if (y[0] == '0') return SNumOposto(z); if (z[0] == '0') return newString(y, strlen(y)); if (! strcmp(y, z)) return newString("0", 1); int i, x; char carry, *Result; i = strlen(y); x = strlen(z); if (x > i) i = x; char * a = newString(y, i); char * b = newString(z, i); if (a[0] == '-') { delete(a, 1, 1); if (b[0] == '-') { delete(b, 1, 1); // -a - (-b) == b - a Result = Subtrai(b, a); free(a); free(b); return Result; } else { // -a - b == -(a + b) char * c = Soma(a, b); Result = newString(c, strlen(c) + 1); leftConcat("-", Result); free(a); free(b); free(c); return Result; } } else if (b[0] == '-') { delete(b, 1, 1); // a - (-b) == a + b Result = Soma(a, b); free(a); free(b); return Result; } else if (SNumCompare(a, b) < 0) { // a < b ==> a - b == -(b - a) char * c = Subtrai(b, a); Result = newString(c, strlen(c) + 1); leftConcat("-", Result); free(a); free(b); free(c); return Result; } // 923 // 199 x = strlen(a); while (strlen(b) < x) leftConcat("0", b); Result = newString("", x); carry = 0; for (i = strlen(a); i >= 1; i--) { x = a[i-1] - 48 - b[i-1] + 48 - carry; if (x < 0) { carry = 1; x += 10; } else carry = 0; charLeftConcat(x + 48, Result); } ZeroLTrim(Result); free(a); free(b); return Result; } char* Multiplica(char* y, char *z) { if ((y[0] == '0') || (z[0] == '0')) return newString("0", 1); if (! strcmp(y, "1")) return newString(z, strlen(z)); if (! strcmp(z, "1")) return newString(y, strlen(y)); if (! strcmp(y, "-1")) return SNumOposto(z); if (! strcmp(z, "-1")) return SNumOposto(y); int i, j; char x, carry, minus, * subtotal, * Result; char ** multAlgarismo = malloc(10 * sizeof(char*)); char * a = newString(y, strlen(y)); char * b = newString(z, strlen(z)); minus = (a[0] == '-'); if (minus) delete(a, 1, 1); if (b[0] == '-') { delete(b, 1, 1); minus = ! minus; } for (i = 2; i <= 9; i++) { multAlgarismo[i] = newString("", strlen(a) + 1); carry = 0; // multiplicar i por cada algarismo de a for (j = strlen(a); j >= 1; j--) { x = (a[j-1] - 48) * i + carry; carry = x / 10; x = x % 10; charLeftConcat(x + 48, multAlgarismo[i]); } if (carry != 0) charLeftConcat(carry + 48, multAlgarismo[i]); } subtotal = newString("", strlen(a) + strlen(b)); Result = newString("0", 1); for (i = strlen(b); i >= 1; i--) if (b[i-1] != '0') { subtotal[0] = 0; // zeros aa direita if (i < strlen(b)) for (j = 1; j <= strlen(b) - i; j++) leftConcat("0", subtotal); if (b[i-1] == '1') leftConcat(a, subtotal); else leftConcat(multAlgarismo[b[i-1] - 48], subtotal); // o Resultado é a soma dos subtotais char * sigma = Soma(Result, subtotal); free(Result); Result = sigma; } ZeroLTrim(Result); free(subtotal); if (minus && (strcmp(Result, "0") != 0)) { subtotal = newString(Result, strlen(Result) + 1); free(Result); Result = subtotal; leftConcat("-", Result); } free(a); free(b); for (i = 2; i <= 9; i++) free(multAlgarismo[i]); free(multAlgarismo); return Result; } // alocar para q: strlen(a) + 1 // para r: strlen(b) + 2 void Divide(char * alinha, char * blinha, char * q, char *r) { if (! strcmp(blinha, "0")) { strcpy(q, "0"); strcpy(r, "0"); return; } if (alinha[0] == '0') { strcpy(q, "0"); strcpy(r, "0"); return; } if (! strcmp(blinha, "1")) { strcpy(q, alinha); strcpy(r, "0"); return; } if (! strcmp(alinha, blinha)) { strcpy(q, "1"); strcpy(r, "0"); return; } char * a = SNumOposto(alinha); if (! strcmp(a, blinha)) { strcpy(q, "-1"); strcpy(r, "0"); free(a); return; } if (! strcmp(blinha, "-1")) { strcpy(q, a); strcpy(r, "0"); free(a); return; } char minusa, minusb, x; int index; free(a); a = newString(alinha, strlen(alinha)); char * b = newString(blinha, strlen(blinha)); minusa = (a[0] == '-'); minusb = (b[0] == '-'); if (minusa) delete(a, 1, 1); if (minusb) delete(b, 1, 1); q[0] = 0; index = strlen(b); Copy(r, a, 1, index); do { x = 0; while (SNumCompare(r, b) >= 0) { x++; char * rr = Subtrai(r, b); strcpy(r, rr); free(rr); } q[strlen(q) + 1] = 0; q[strlen(q)] = x + 48; if (index >= strlen(a)) break; // "baixar" o próximo index++; if (! strcmp(r, "0")) r[0] = 0; // zero de resto nao vai virar zero aa esq r[strlen(r) + 1] = 0; r[strlen(r)] = a[index-1]; } while (true); ZeroLTrim(q); // 7 / 4 == ( 1, 3) a < 0, r > 0: incrementar o módulo do quociente // -7 / 4 == (-2, 1) complementar o resto // 7 / -4 == (-1, 3) exatamente um negativo: sinal '-' no quociente // -7 / -4 == ( 2, 1) if (minusa && (strcmp(r, "0") != 0)) { char * qq = Soma(q, "1"); char * rr = Subtrai(b, r); strcpy(q, qq); strcpy(r, rr); free(qq); free(rr); } if ((minusa && (! minusb)) || ((! minusa) && minusb)) leftConcat("-", q); free(a); free(b); } char * SNumOposto(char *s) { char * Result; if (s[0] == '0') { Result = newString("0", 1); } else if (s[0] == '-') { Result = newString(s, strlen(s)); delete(Result, 1, 1); } else { Result = newString(s, strlen(s) + 1); leftConcat("-", Result); } return Result; } char* SNumAbs(char * a) { if (a[0] != '-') return newString(a, strlen(a)); else return SNumOposto(a); } char* FracAbs(char* a) { if (a[0] != '-') return newString(a, strlen(a)); else return FracOposto(a); } char * Potencia(char * a, char * b) { char * Result, * n; n = newString(b, strlen(b)); if ((n[0] == '0') || (n[0] == '-')) Result = newString("1", 1); else { Result = newString(a, strlen(a)); while (strcmp(n, "1")) { char * rr = Multiplica(Result, a); char * nn = Subtrai(n, "1"); free(Result); free(n); Result = rr; n = nn; } } free(n); return Result; } char * FracAdd(char * x, char * y) { if (x[0] == '0') return newString(y, strlen(y)); if (y[0] == '0') return newString(x, strlen(x)); if ((! pos('/', x)) && (! pos('/', y))) return Soma(x, y); SFrac a, b; char* Result; a = Str2Frac(x); b = Str2Frac(y); char * anbd = Multiplica(a.n, b.d); char * adbn = Multiplica(a.d, b.n); char * adbd = Multiplica(a.d, b.d); char * s = Soma(anbd, adbn); Result = newString(s, strlen(s) + 1 + strlen(adbd)); Result[strlen(Result) + 1] = 0; Result[strlen(Result)] = '/'; strcat(Result, adbd); FracReduz(Result); free(anbd); free(adbn); free(adbd); free(s); free(a.n); free(a.d); free(b.n); free(b.d); return Result; } char * FracSub(char * x, char * y) { if (x[0] == '0') return FracOposto(y); if (y[0] == '0') return newString(x, strlen(x)); if (! strcmp(x, y)) return newString("0", 1); if ((! pos('/', x)) && (! pos('/', y))) return Subtrai(x, y); SFrac a, b; char* Result; a = Str2Frac(x); b = Str2Frac(y); char * bn = SNumOposto(b.n); free(b.n); b.n = bn; char * anbd = Multiplica(a.n, b.d); char * adbn = Multiplica(a.d, b.n); char * adbd = Multiplica(a.d, b.d); char * s = Soma(anbd, adbn); Result = newString(s, strlen(s) + 1 + strlen(adbd)); Result[strlen(Result) + 1] = 0; Result[strlen(Result)] = '/'; strcat(Result, adbd); FracReduz(Result); free(anbd); free(adbn); free(adbd); free(s); free(a.n); free(a.d); free(b.n); free(b.d); return Result; } char * FracMul(char * x, char * y) { if ((x[0] == '0') || (y[0] == '0')) return newString("0", 1); if (! strcmp(x, "1")) return newString(y, strlen(y)); if (! strcmp(y, "1")) return newString(x, strlen(x)); if (! strcmp(x, "-1")) return FracOposto(y); if (! strcmp(y, "-1")) return FracOposto(x); if ((! pos('/', x)) && (! pos('/', y))) return Multiplica(x, y); SFrac a, b; char* Result; a = Str2Frac(x); b = Str2Frac(y); char * anbn = Multiplica(a.n, b.n); char * adbd = Multiplica(a.d, b.d); Result = newString(anbn, strlen(anbn) + 1 + strlen(adbd)); Result[strlen(Result) + 1] = 0; Result[strlen(Result)] = '/'; strcat(Result, adbd); FracReduz(Result); free(anbn); free(adbd); free(a.n); free(a.d); free(b.n); free(b.d); return Result; } char * FracDiv(char * x, char * y) { if (! strcmp(y, "1")) return newString(x, strlen(x)); if (! strcmp(y, "-1")) return FracOposto(x); if ((x[0] == '0') || (y[0] == '0')) return newString("0", 1); if (! strcmp(x, y)) return newString("1", 1); SFrac a, b; char* Result; a = Str2Frac(x); b = Str2Frac(y); char * aux = b.n; b.n = b.d; b.d = aux; if (b.d[0] == '-') { char * bn = SNumOposto(b.n); char * bd = SNumOposto(b.d); free(b.n); free(b.d); b.n = bn; b.d = bd; } char * anbn = Multiplica(a.n, b.n); char * adbd = Multiplica(a.d, b.d); Result = newString(anbn, strlen(anbn) + 1 + strlen(adbd)); Result[strlen(Result) + 1] = 0; Result[strlen(Result)] = '/'; strcat(Result, adbd); FracReduz(Result); free(anbn); free(adbd); free(a.n); free(a.d); free(b.n); free(b.d); return Result; } void FracReduz(char * x) { if (! pos('/', x)) return; SFrac a, b; char *m, *r; a = Str2Frac(x); m = mdc(a.n, a.d); if (strcmp(m, "1")) { b.n = newString("", strlen(a.n)); b.d = newString("", strlen(a.d)); r = newString("", strlen(m) + 1); Divide(a.n, m, b.n, r); Divide(a.d, m, b.d, r); free(r); strcpy(x, b.n); if (strcmp(b.d, "1")) { x[strlen(x) + 1] = 0; x[strlen(x)] = '/'; strcat(x, b.d); } free(b.n); free(b.d); } else if (! strcmp(a.d, "1")) strcpy(x, a.n); free(m); free(a.n); free(a.d); } char * Valida(char * s) { char * Result; int i = 1; if (s[0] == 0) return newString("0", 1); Result = newString(s, strlen(s)); if (Result[0] == '-') i++; while (i <= strlen(Result)) { if ((Result[i-1] >= '0') && (Result[i-1] <= '9')) i++; else delete(Result, i, 1); } ZeroLTrim(Result); if (strcmp(Result, "-0") == 0) strcpy(Result, "0"); return Result; } char * FracValida(char *s) { char * Result; int i = 1; if (s[0] == '0') return newString("0", 1); Result = newString(s, strlen(s)); if (Result[0] == '-') i++; while (i <= strlen(Result)) { if ((Result[i-1] >= '0') && (Result[i-1] <= '9') || (Result[i-1] == '/')) i++; else delete(Result, i, 1); } if ((Result[0] == '-') && (Result[1] == '0')) delete(Result, 1, 1); i = pos('/', Result); if (i > 0) Result[i] = 32; i = 1; if (Result[0] == '-') i++; while (i <= strlen(Result)) { if ((Result[i-1] >= '0') && (Result[i-1] <= '9') || (Result[i-1] == 32)) i++; else delete(Result, i, 1); } i = pos(32, Result); if (i > 0) Result[i] = '/'; ZeroLTrim(Result); FracReduz(Result); return Result; } short SNumCompare(char* a, char *b) { char minus; short Result = 0; if (! strcmp(a, b)) return Result; minus = false; if (a[0] == '-') if (b[0] == '-') minus = true; else Result = -1; else if (b[0] == '-') Result = -1; if (Result) return Result; if (b[0] == '0') return 1; if (a[0] == '0') return -1; int tamanho1 = strlen(a); int tamanho2 = strlen(b); if (tamanho2 > tamanho1) tamanho1 = tamanho2; char * alinha = newString(a, tamanho1); char * blinha = newString(b, tamanho1); if (minus) { delete(alinha, 1, 1); delete(blinha, 1, 1); } while (strlen(blinha) < strlen(alinha)) leftConcat("0", blinha); while (strlen(alinha) < strlen(blinha)) leftConcat("0", alinha); // positivos if (strcmp(alinha, blinha) > 0) Result = 1; else Result = -1; // negativos inverte if (minus) Result = - Result; free(alinha); free(blinha); return Result; } SFrac Str2Frac(char * x) { SFrac Result; int i = pos('/', x); if (i > 0) { Result.n = copy(x, 1, i); Result.d = newString(x, strlen(x)); delete(Result.d, 1, i + 1); } else { Result.n = newString(x, strlen(x)); Result.d = newString("1", 1); } return Result; } char* mdc(char *x, char *y) { char * q, * r; if (x[0] == '0') return newString(y, strlen(y)); if (y[0] == '0') return newString(x, strlen(x)); char * xx, * yy; xx = SNumAbs(x); yy = SNumAbs(y); if (SNumCompare(yy, xx) > 0) { q = xx; xx = yy; yy = q; } do { q = newString("", strlen(xx)); r = newString("", strlen(yy) + 1); Divide(xx, yy, q, r); free(q); if ((! strcmp(r, "1")) || (! strcmp(r, "0"))) break; strcpy(xx, yy); strcpy(yy, r); free(r); } while (true); free(xx); if (! strcmp(r, "1")) { free(r); free(yy); return newString("1", 1); } else { free(r); char * z = newString(yy, strlen(yy)); free(yy); return z; } } char * FracOposto(char * s) { return SNumOposto(s); // apelei /* char * Result; SFrac a = Str2Frac(s); char * an = SNumOposto(a.n); free(a.n); a.n = an; if (strcmp(a.d, "1") == 0) Result = newString(a.n, strlen(a.n)); else { Result = newString(a.n, strlen(a.n) + 1 + strlen(a.d)); Result[strlen(Result) + 1] = 0; Result[strlen(Result)] = '/'; strcat(Result, a.d); } free(a.n); free(a.d); return Result; */ } short FracCompare(char *x, char *y) { if (y[0] == '0') { if (x[0] == '0') return 0; else if (x[0] == '-') return -1; else return 1; } if ((! pos('/', x)) && (! pos('/', y))) return SNumCompare(x, y); char * dif = FracSub(x, y); SFrac s = Str2Frac(dif); short Result = SNumCompare(s.n, "0"); free(s.n); free(s.d); free(dif); return Result; }