expr.c (17963B)
1 /* expr.c - edicion de la expresion (ver expr.h) y su texto ASCII. */ 2 #include <string.h> 3 #include "expr.h" 4 #include "str.h" 5 6 const char VAR_NAMES[NVARS + 1] = "ABCDEFMXY"; 7 8 _Static_assert(T_VCTANS < T_VAR && T_VAR + NVARS <= T_FN && T_FN + FN_COUNT <= 256, "los rangos de tokens se pisan"); 9 10 const FnInfo FN_INFO[FN_COUNT] = { 11 [FN_SIN] = { "sin", "sin(", 1 }, [FN_COS] = { "cos", "cos(", 1 }, 12 [FN_TAN] = { "tan", "tan(", 1 }, [FN_ASIN] = { "asin", "sin\xe2\x81\xbb\xc2\xb9(", 1 }, 13 [FN_ACOS] = { "acos", "cos\xe2\x81\xbb\xc2\xb9(", 1 }, [FN_ATAN] = { "atan", "tan\xe2\x81\xbb\xc2\xb9(", 1 }, 14 [FN_SINH] = { "sinh", "sinh(", 1 }, [FN_COSH] = { "cosh", "cosh(", 1 }, 15 [FN_TANH] = { "tanh", "tanh(", 1 }, [FN_ASINH] = { "asinh", "sinh\xe2\x81\xbb\xc2\xb9(", 1 }, 16 [FN_ACOSH] = { "acosh", "cosh\xe2\x81\xbb\xc2\xb9(", 1 }, [FN_ATANH] = { "atanh", "tanh\xe2\x81\xbb\xc2\xb9(", 1 }, 17 [FN_LN] = { "ln", "ln(", 1 }, [FN_LOG] = { "log", "log(", 1 }, 18 [FN_INT] = { "int", "Int(", 1 }, [FN_INTG] = { "intg", "Intg(", 1 }, 19 [FN_RND] = { "rnd", "Rnd(", 1 }, [FN_GCD] = { "gcd", "GCD(", 2 }, 20 [FN_LCM] = { "lcm", "LCM(", 2 }, [FN_POL] = { "pol", "Pol(", 2 }, 21 [FN_REC] = { "rec", "Rec(", 2 }, [FN_NOT] = { "not", "Not(", 1 }, 22 [FN_NEG] = { "neg", "Neg(", 1 }, [FN_XHAT] = { "xhat", "x\xcc\x82(", 1 }, 23 [FN_YHAT] = { "yhat", "y\xcc\x82(", 1 }, 24 [FN_NPD] = { "normpd", "NormPD(", 3 }, [FN_NCD] = { "normcd", "NormCD(", 4 }, 25 [FN_INVN] = { "invnorm", "InvN(", 3 }, [FN_BPD] = { "binompd", "BinomPD(", 3 }, 26 [FN_BCD] = { "binomcd", "BinomCD(", 3 }, [FN_PPD] = { "poisspd", "PoissPD(", 2 }, 27 [FN_PCD] = { "poisscd", "PoissCD(", 2 }, 28 [FN_ARG] = { "arg", "arg(", 1 }, [FN_CONJ] = { "conjg", "Conjg(", 1 }, 29 [FN_RE] = { "real", "ReP(", 1 }, [FN_IM] = { "imag", "ImP(", 1 }, 30 [FN_DET] = { "det", "Det(", 1 }, [FN_TRN] = { "trn", "Trn(", 1 }, 31 [FN_IDEN] = { "identity", "Identity(", 1 }, [FN_DOT] = { "dot", "DotP(", 2 }, 32 [FN_CROSS] = { "cross", "CrossP(", 2 }, [FN_VANG] = { "angle", "Angle(", 2 }, 33 [FN_UNITV] = { "unitv", "UnitV(", 1 }, 34 }; 35 36 /* palabras que al tipear "(" se vuelven plantilla */ 37 static const struct { const char *name; int tpl; int idx; } WORD_TPL[] = { 38 { "sqrt", T_SQRT, 0 }, { "cbrt", T_ROOT, 3 }, { "root", T_ROOT, 0 }, { "abs", T_ABS, 0 }, 39 { "logb", T_LOGB, 0 }, { "frac", T_FRAC, 0 }, { "exp", T_POW, -1 }, 40 { "integ", T_INTEG, 0 }, { "deriv", T_DERIV, 0 }, { "sum", T_SUM, 0 }, { "prod", T_PROD, 0 }, 41 }; 42 43 int tpl_fields(int t) 44 { 45 switch (t) { 46 case T_FRAC: case T_FRACL: case T_ROOT: case T_LOGB: return 2; 47 case T_MIXED: case T_INTEG: case T_SUM: case T_PROD: return 3; 48 case T_DERIV: return 2; 49 default: return 1; 50 } 51 } 52 53 void ex_clear(Expr *e) { e->n = e->cur = 0; } 54 bool ex_empty(const Expr *e) { return e->n == 0; } 55 56 void ex_left(Expr *e) { e->cur = e->cur > 0 ? e->cur - 1 : e->n; } 57 void ex_right(Expr *e) { e->cur = e->cur < e->n ? e->cur + 1 : 0; } 58 void ex_home(Expr *e) { e->cur = 0; } 59 void ex_end(Expr *e) { e->cur = e->n; } 60 61 /* ------------------------------------------------------------ estructura */ 62 63 int ex_match_end(const Expr *e, int i) 64 { 65 int d = 0; 66 for (int k = i; k < e->n; k++) { 67 if (tok_is_tpl(e->t[k])) d++; 68 else if (e->t[k] == T_END && --d == 0) return k; 69 } 70 return e->n; 71 } 72 73 int ex_match_start(const Expr *e, int i) 74 { 75 int d = 0; 76 for (int k = i; k >= 0; k--) { 77 if (e->t[k] == T_END) d++; 78 else if (tok_is_tpl(e->t[k]) && --d == 0) return k; 79 } 80 return 0; 81 } 82 83 int ex_container(const Expr *e, int pos, int *field) 84 { 85 static int stk[EXPR_MAX / 2], fld[EXPR_MAX / 2]; /* static: la pila de la Pico es chica */ 86 int sp = 0; 87 for (int k = 0; k < pos && k < e->n; k++) { 88 int t = e->t[k]; 89 if (tok_is_tpl(t)) { stk[sp] = k; fld[sp] = 0; sp++; } 90 else if (t == T_SEP && sp) fld[sp - 1]++; 91 else if (t == T_END && sp) sp--; 92 } 93 if (field) *field = sp ? fld[sp - 1] : 0; 94 return sp ? stk[sp - 1] : -1; 95 } 96 97 static bool is_digit(int t) { return (t >= '0' && t <= '9') || t == '.'; } 98 static bool is_lower(int t) { return t >= 'a' && t <= 'z'; } 99 100 int ex_atom_start(const Expr *e, int pos) 101 { 102 if (pos <= 0) return pos; 103 int t = e->t[pos - 1]; 104 if (t == T_END) { 105 int s = ex_match_start(e, pos - 1); 106 if (tok_is_pow(e->t[s])) { 107 int b = ex_atom_start(e, s); 108 return b; /* base + potencia (o solo la potencia) */ 109 } 110 return s; 111 } 112 if (t == ')') { 113 int d = 0; 114 for (int k = pos - 1; k >= 0; k--) { 115 int c = e->t[k]; 116 if (c == T_END) { k = ex_match_start(e, k); continue; } 117 if (c == T_SEP || tok_is_tpl(c)) return pos; /* se salio del campo */ 118 if (c == ')') d++; 119 else if (c == '(' || c >= T_FN) { if (--d == 0) return k; } 120 } 121 return pos; 122 } 123 if (is_digit(t)) { 124 int k = pos - 1; 125 while (k > 0 && (is_digit(e->t[k - 1]) || e->t[k - 1] == T_E10 || 126 (e->t[k - 1] == '-' && k > 1 && e->t[k - 2] == T_E10))) k--; 127 return k; 128 } 129 if (t == T_PI || t == T_E || t == T_ANS || t == T_PREANS || t == T_RAN || (t >= T_MAT && t <= T_VCTANS) || 130 (t >= T_VAR && t < T_VAR + NVARS) || is_lower(t) || (t >= 'A' && t <= 'Z')) 131 return pos - 1; 132 if (t == T_INV || t == '!' || t == '%' || t == T_DEGS) { 133 int b = ex_atom_start(e, pos - 1); 134 return b == pos - 1 ? pos : b; 135 } 136 return pos; 137 } 138 139 /* ------------------------------------------------------------ edicion basica */ 140 141 static bool ins(Expr *e, int at, const uint8_t *tk, int k) 142 { 143 if (e->n + k > EXPR_MAX) return false; 144 memmove(e->t + at + k, e->t + at, (size_t)(e->n - at)); 145 memcpy(e->t + at, tk, (size_t)k); 146 e->n += k; 147 return true; 148 } 149 150 static void del(Expr *e, int at, int k) 151 { 152 memmove(e->t + at, e->t + at + k, (size_t)(e->n - at - k)); 153 e->n -= k; 154 } 155 156 bool ex_insert_raw(Expr *e, int tok) 157 { 158 uint8_t t = (uint8_t)tok; 159 if (!ins(e, e->cur, &t, 1)) return false; 160 e->cur++; 161 return true; 162 } 163 164 bool ex_template(Expr *e, int tpl) 165 { 166 uint8_t tk[4] = { (uint8_t)tpl }; 167 int k = 1, f = tpl_fields(tpl); 168 for (int i = 1; i < f; i++) tk[k++] = T_SEP; 169 tk[k++] = T_END; 170 if (!ins(e, e->cur, tk, k)) return false; 171 e->cur++; 172 return true; 173 } 174 175 bool ex_slash(Expr *e) 176 { 177 int a = ex_atom_start(e, e->cur); 178 if (a == e->cur) return ex_template(e, T_FRAC); 179 uint8_t f = T_FRACL, se[2] = { T_SEP, T_END }; 180 if (e->n + 3 > EXPR_MAX) return false; 181 ins(e, a, &f, 1); 182 ins(e, e->cur + 1, se, 2); 183 e->cur += 2; 184 ex_tidy(e); 185 return true; 186 } 187 188 bool ex_power(Expr *e) { return ex_template(e, T_POWL); } 189 190 bool ex_power_n(Expr *e, int n) 191 { 192 uint8_t tk[3] = { T_POW, (uint8_t)('0' + n), T_END }; 193 if (!ins(e, e->cur, tk, 3)) return false; 194 e->cur += 3; 195 return true; 196 } 197 198 bool ex_root_n(Expr *e, int n) 199 { 200 uint8_t tk[4] = { T_ROOT, (uint8_t)('0' + n), T_SEP, T_END }; 201 if (!ins(e, e->cur, tk, 4)) return false; 202 e->cur += 3; 203 return true; 204 } 205 206 /* hay un "(" sin cerrar entre el inicio del campo y pos */ 207 static bool open_paren(const Expr *e, int pos) 208 { 209 int d = 0; 210 for (int k = pos - 1; k >= 0; k--) { 211 int c = e->t[k]; 212 if (c == T_END) { k = ex_match_start(e, k); continue; } 213 if (c == T_SEP || tok_is_tpl(c)) break; 214 if (c == ')') d++; 215 else if (c == '(' || c >= T_FN) { if (d == 0) return true; d--; } 216 } 217 return false; 218 } 219 220 /* "(...)" que ocupa un campo entero de una fraccion o potencia tipeada: los 221 * parentesis sobran (la estructura ya agrupa), como en la Casio. */ 222 static bool strip_field(Expr *e, int from, int to) 223 { 224 if (to - from < 2 || e->t[from] != '(' || e->t[to - 1] != ')') return false; 225 int d = 0; 226 for (int k = from; k < to; k++) { 227 int c = e->t[k]; 228 if (tok_is_tpl(c)) { k = ex_match_end(e, k); continue; } 229 if (c == '(' || c >= T_FN) d++; 230 else if (c == ')' && --d == 0 && k != to - 1) return false; /* "(a)+(b)" */ 231 } 232 if (d) return false; 233 del(e, to - 1, 1); 234 del(e, from, 1); 235 if (e->cur > to - 1) e->cur--; 236 if (e->cur > from) e->cur--; 237 return true; 238 } 239 240 void ex_tidy(Expr *e) 241 { 242 bool again = true; 243 while (again) { 244 again = false; 245 for (int i = 0; i < e->n && !again; i++) { 246 int t = e->t[i]; 247 if (t != T_FRACL && t != T_POWL) continue; 248 int from = i + 1, d = 0; 249 for (int k = i + 1; k < e->n; k++) { 250 int c = e->t[k]; 251 if (tok_is_tpl(c)) d++; 252 else if ((c == T_SEP || c == T_END) && d == 0) { 253 /* no tocar el campo donde esta el cursor si todavia se esta escribiendo */ 254 if (!(e->cur > from && e->cur < k) && strip_field(e, from, k)) { again = true; break; } 255 if (c == T_END) break; 256 from = k + 1; 257 } else if (c == T_END) d--; 258 } 259 } 260 } 261 } 262 263 /* Al tipear un operador al final del denominador o exponente "tipeado", sale. */ 264 static void auto_exit(Expr *e, int tok) 265 { 266 bool op = tok == '+' || tok == '-' || tok == T_MUL || tok == T_DIV || tok == ',' || tok == '=' || tok == '/' || 267 tok == T_NPR || tok == T_NCR; 268 if (!op) return; 269 for (;;) { 270 if (e->cur >= e->n || e->t[e->cur] != T_END) return; /* no esta al final de un campo */ 271 int fld, c = ex_container(e, e->cur, &fld); 272 if (c < 0) return; 273 int ct = e->t[c]; 274 bool lin = (ct == T_FRACL && fld == 1) || ct == T_POWL; 275 if (!lin || e->t[e->cur - 1] == T_SEP || tok_is_tpl(e->t[e->cur - 1])) return; /* campo vacio */ 276 if (open_paren(e, e->cur)) return; 277 if (tok == '-' && ct == T_POWL && e->cur - 1 == c) return; 278 e->cur++; /* salta el END */ 279 ex_tidy(e); 280 } 281 } 282 283 /* ")" sin "(" abierto en el campo: sale de la plantilla */ 284 static bool close_paren(Expr *e) 285 { 286 for (;;) { 287 if (open_paren(e, e->cur)) return ex_insert_raw(e, ')'); 288 int fld, c = ex_container(e, e->cur, &fld); 289 if (c < 0) return ex_insert_raw(e, ')'); 290 int ct = e->t[c]; 291 e->cur = ex_match_end(e, c) + 1; 292 if (ct == T_SQRT || ct == T_ROOT || ct == T_ABS || ct == T_LOGB || ct == T_POW || 293 ct == T_INTEG || ct == T_DERIV || ct == T_SUM || ct == T_PROD) return true; /* era "sqrt(" */ 294 } 295 } 296 297 /* letras tipeadas justo antes del cursor (en el mismo campo) */ 298 static int letters_before(const Expr *e, int pos) 299 { 300 int k = pos; 301 while (k > 0 && is_lower(e->t[k - 1])) k--; 302 return k; 303 } 304 305 static bool word_eq(const Expr *e, int from, int to, const char *w) 306 { 307 int n = (int)strlen(w); 308 if (to - from != n) return false; 309 for (int i = 0; i < n; i++) if (e->t[from + i] != (uint8_t)w[i]) return false; 310 return true; 311 } 312 313 /* "(" despues de letras: busca el nombre mas largo al final de las letras */ 314 static bool word_paren(Expr *e) 315 { 316 int s = letters_before(e, e->cur); 317 for (int from = s; from < e->cur; from++) { 318 for (int f = 0; f < FN_COUNT; f++) 319 if (word_eq(e, from, e->cur, FN_INFO[f].name)) { 320 del(e, from, e->cur - from); 321 e->cur = from; 322 return ex_insert_raw(e, T_FN + f); 323 } 324 for (size_t w = 0; w < sizeof WORD_TPL / sizeof WORD_TPL[0]; w++) 325 if (word_eq(e, from, e->cur, WORD_TPL[w].name)) { 326 del(e, from, e->cur - from); 327 e->cur = from; 328 if (WORD_TPL[w].idx < 0) { /* exp( -> e^□ */ 329 ex_insert_raw(e, T_E); 330 return ex_template(e, T_POW); 331 } 332 if (WORD_TPL[w].idx) return ex_root_n(e, WORD_TPL[w].idx); 333 return ex_template(e, WORD_TPL[w].tpl); 334 } 335 } 336 return ex_insert_raw(e, '('); 337 } 338 339 /* "," dentro de integ( sum( deriv(...: pasa al campo siguiente */ 340 static bool next_field(Expr *e) 341 { 342 if (open_paren(e, e->cur)) return false; 343 int fld, c = ex_container(e, e->cur, &fld); 344 if (c < 0) return false; 345 int ct = e->t[c]; 346 if (!(ct == T_INTEG || ct == T_SUM || ct == T_PROD || ct == T_DERIV || ct == T_LOGB || ct == T_ROOT)) return false; 347 int d = 0; 348 for (int k = e->cur; k < e->n; k++) { 349 int t = e->t[k]; 350 if (tok_is_tpl(t)) d++; 351 else if (t == T_END) { if (!d) return false; d--; } 352 else if (t == T_SEP && !d) { e->cur = k + 1; return true; } 353 } 354 return false; 355 } 356 357 bool ex_insert(Expr *e, int tok) 358 { 359 if (tok == '(') return word_paren(e); 360 if (tok == ')') return close_paren(e); 361 if (tok == '/') { auto_exit(e, tok); return ex_slash(e); } 362 if (tok == '^') return ex_power(e); 363 auto_exit(e, tok); 364 if (tok == ',' && next_field(e)) return true; 365 if (tok == 'i' && e->cur > 0 && e->t[e->cur - 1] == 'p') { /* pi */ 366 e->t[e->cur - 1] = T_PI; 367 return true; 368 } 369 if (tok == 's' && e->cur > 1 && e->t[e->cur - 1] == 'n' && e->t[e->cur - 2] == 'a' && 370 letters_before(e, e->cur) == e->cur - 2) { /* ans */ 371 del(e, e->cur - 2, 2); 372 e->cur -= 2; 373 return ex_insert_raw(e, T_ANS); 374 } 375 if (tok >= 'A' && tok <= 'Z') { 376 const char *v = strchr(VAR_NAMES, tok); 377 if (v) return ex_insert_raw(e, T_VAR + (int)(v - VAR_NAMES)); 378 } 379 return ex_insert_raw(e, tok); 380 } 381 382 /* Quita la plantilla que empieza en i dejando su contenido. */ 383 static void dissolve(Expr *e, int i) 384 { 385 int end = ex_match_end(e, i), d = 0; 386 for (int k = end; k > i; k--) { 387 int c = e->t[k]; 388 if (c == T_END) { if (k == end) { del(e, k, 1); continue; } d++; } 389 else if (tok_is_tpl(c)) d--; 390 else if (c == T_SEP && d == 0) del(e, k, 1); 391 } 392 del(e, i, 1); 393 } 394 395 void ex_backspace(Expr *e) 396 { 397 if (e->cur == 0) return; 398 int t = e->t[e->cur - 1]; 399 if (t == T_SEP || t == T_END) { e->cur--; return; } 400 if (tok_is_tpl(t)) { dissolve(e, e->cur - 1); e->cur--; return; } 401 del(e, e->cur - 1, 1); 402 e->cur--; 403 } 404 405 void ex_delete(Expr *e) 406 { 407 if (e->cur >= e->n) return; 408 int t = e->t[e->cur]; 409 if (t == T_SEP || t == T_END) return; 410 if (tok_is_tpl(t)) { dissolve(e, e->cur); return; } 411 del(e, e->cur, 1); 412 } 413 414 bool ex_insert_expr(Expr *e, const Expr *src) 415 { 416 if (!ins(e, e->cur, src->t, src->n)) return false; 417 e->cur += src->n; 418 return true; 419 } 420 421 /* ------------------------------------------------------------ texto */ 422 423 static const struct { uint8_t tok; const char *txt; } TXT[] = { 424 { T_FRAC, "\\f{" }, { T_FRACL, "\\F{" }, { T_SQRT, "\\r{" }, { T_ROOT, "\\n{" }, 425 { T_POW, "\\x{" }, { T_POWL, "^{" }, { T_LOGB, "\\l{" }, { T_ABS, "\\a{" }, { T_MIXED, "\\m{" }, 426 { T_INTEG, "\\i{" }, { T_DERIV, "\\d{" }, { T_SUM, "\\s{" }, { T_PROD, "\\p{" }, 427 { T_SEP, "}{" }, { T_END, "}" }, { T_MUL, "*" }, { T_DIV, ":" }, { T_PI, "\\pi" }, { T_E, "\\e" }, 428 { T_ANS, "\\ans" }, { T_PREANS, "\\pans" }, { T_RAN, "\\ran" }, { T_E10, "\\E" }, { T_INV, "\\inv" }, 429 { T_DEGS, "\\deg" }, { T_ANGLE, "\\ang" }, 430 { T_MAT, "\\MA" }, { T_MAT + 1, "\\MB" }, { T_MAT + 2, "\\MC" }, { T_MAT + 3, "\\MD" }, { T_MATANS, "\\Mans" }, 431 { T_VCT, "\\VA" }, { T_VCT + 1, "\\VB" }, { T_VCT + 2, "\\VC" }, { T_VCT + 3, "\\VD" }, { T_VCTANS, "\\Vans" }, { T_NPR, "\\P" }, { T_NCR, "\\C" }, 432 }; 433 enum { NTXT = sizeof TXT / sizeof TXT[0] }; 434 435 int expr_to_text(const Expr *e, char *buf, int n) 436 { 437 int p = 0; 438 buf[0] = 0; 439 for (int i = 0; i < e->n && p >= 0; i++) { 440 int t = e->t[i]; 441 const char *s = 0; 442 for (int k = 0; k < NTXT; k++) if (TXT[k].tok == t) { s = TXT[k].txt; break; } 443 if (s) p = str_put(buf, n, p, s); 444 else if (t >= T_VAR && t < T_VAR + NVARS) { 445 char v[4] = { '\\', 'v', VAR_NAMES[t - T_VAR], 0 }; 446 p = str_put(buf, n, p, v); 447 } else if (t >= T_FN && t < T_FN + FN_COUNT) { 448 p = str_put(buf, n, p, FN_INFO[t - T_FN].name); 449 p = str_put(buf, n, p, "("); 450 } else { 451 char c[2] = { (char)t, 0 }; 452 p = str_put(buf, n, p, c); 453 } 454 } 455 return p; 456 } 457 458 /* Arma la expresion "tipeando" el texto: las plantillas se abren con \x{, "}{" pasa 459 * al campo siguiente y "}" sale. Las palabras con "(" se convierten como al tipear. */ 460 bool expr_from_text(Expr *e, const char *s) 461 { 462 ex_clear(e); 463 if (!ex_type_text(e, s)) return false; 464 e->cur = e->n; 465 return true; 466 } 467 468 bool ex_type_text(Expr *e, const char *s) 469 { 470 while (*s) { 471 bool done = false; 472 if (s[0] == '}') { 473 e->cur++; /* pasa el SEP o el END */ 474 if (e->cur > e->n) return false; 475 s += s[1] == '{' ? 2 : 1; 476 continue; 477 } 478 for (int k = 0; k < NTXT && !done; k++) { 479 int l = (int)strlen(TXT[k].txt); 480 if (TXT[k].tok == T_SEP || TXT[k].tok == T_END || strncmp(s, TXT[k].txt, (size_t)l)) continue; 481 int tk = TXT[k].tok; 482 if (tok_is_tpl(tk)) { if (!ex_template(e, tk)) return false; } 483 else if (!ex_insert_raw(e, tk)) return false; 484 s += l; 485 done = true; 486 } 487 if (done) continue; 488 if (s[0] == '\\' && s[1] == 'v' && s[2]) { 489 const char *v = strchr(VAR_NAMES, s[2]); 490 if (!v) return false; 491 ex_insert_raw(e, T_VAR + (int)(v - VAR_NAMES)); 492 s += 3; 493 continue; 494 } 495 if (s[0] == '\\') return false; 496 if (*s == '(') { if (!word_paren(e)) return false; s++; continue; } 497 if (!ex_insert_raw(e, (unsigned char)*s)) return false; 498 s++; 499 } 500 return true; 501 }