Advertisement
Guest User

Untitled

a guest
Oct 16th, 2016
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.34 KB | None | 0 0
  1. enum Oper {
  2. OPER_NONE,
  3. OPER_POW, // prec = 0
  4. OPER_IMP = 3, // prec = 1
  5. OPER_DIV, // prec = 2
  6. OPER_MUL, // prec = 2
  7. OPER_SUB, // prec = 3
  8. OPER_ADD, // prec = 3
  9. OPER_DONE, // prec = 4
  10. OPER_LPAREN
  11. };
  12. typedef uint8_t oper_t;
  13. #define operPrec(op) ((op) >> 1)
  14. struct Poly {
  15. int degree; // This is the maximum power.
  16. float term[1]; // This contains the coefficient of degree + 1 terms (the [1] is for portability).
  17. };
  18. struct Poly *allocPoly(int degree) {
  19. struct Poly *result = calloc(2 + degree, sizeof(int));
  20. if (result)
  21. result->degree = degree;
  22. return result;
  23. }
  24. struct Poly *addPoly(struct Poly *left, struct Poly *right) {
  25. struct Poly *result = left, *other = right;
  26. if (left == NULL || right == NULL) {
  27. if (right != left)
  28. free(right);
  29. free(left);
  30. return NULL;
  31. }
  32. if (left->degree < right->degree) {
  33. result = right;
  34. other = left;
  35. }
  36. for (int i = 0; i <= other->degree; ++i)
  37. result->term[i] = left->term[i] + right->term[i];
  38. if (other != result)
  39. free(other);
  40. return result;
  41. }
  42. struct Poly *subPoly(struct Poly *left, struct Poly *right) {
  43. struct Poly *result = left, *other = right;
  44. if (left == NULL || right == NULL) {
  45. if (right != left)
  46. free(right);
  47. free(left);
  48. return NULL;
  49. }
  50. if (left->degree < other->degree) {
  51. result = right;
  52. other = left;
  53. }
  54. for (int i = 0; i <= left->degree; ++i)
  55. result->term[i] = left->term[i] - right->term[i];
  56. if (other != result)
  57. free(other);
  58. return result;
  59. }
  60. struct Poly *mulPoly(struct Poly *left, struct Poly *right) {
  61. int newDegree;
  62. struct Poly *result;
  63. if (left == NULL || right == NULL || __builtin_add_overflow(left->degree, right->degree, &newDegree) || !(result = allocPoly(newDegree))) {
  64. if (right != left)
  65. free(right);
  66. free(left);
  67. return NULL;
  68. }
  69. for (int i = 0; i <= left->degree; i++)
  70. for (int j = 0; j <= right->degree; j++)
  71. result->term[i + j] += left->term[i] * right->term[j];
  72. if (right != left)
  73. free(right);
  74. free(left);
  75. return result;
  76. }
  77. struct Poly *divPoly(struct Poly *left, struct Poly *right) {
  78. struct Poly *result, *remainder = left, *temp;
  79. int newDegree;
  80. if (left == NULL || right == NULL || right->degree < left->degree || __builtin_sub_overflow(left->degree, right->degree, &newDegree) || result = allocPoly(newDegree + 1)){
  81. if (right != left)
  82. free(right);
  83. free(left);
  84. return NULL;
  85. }
  86. int factor, ctr = left->degree - right->degree + 1;
  87. result->degree = ctr;
  88. while(remainder->degree > right->degree){
  89. temp = right;
  90. /* divide leading term divisor into leading term temp */
  91. factor = remainder->term[remainder->degree] / right->term[right->degree];
  92. /* Factor becomes term of result */
  93. result->term[ctr--] = factor;
  94. /* multiply factor by temp */
  95. for ( int i = 0; i <= temp->degree; ++i ){
  96. temp->term[i] = temp->term[i] * factor;
  97. }
  98. /* subtract temp from remainder */
  99. for ( int i = remainder->degree; i >= temp->degree; --i ){
  100. remainder->term[i] -= temp->term[i];
  101. }
  102. remainder->degree--;
  103. /* somehow we will need to adjust remainder to the correct degree to make this work */
  104.  
  105. }
  106. if ( right != left )
  107. free( right );
  108. free( left );
  109. return result;
  110. }
  111. struct Poly *powPoly(struct Poly *left, struct Poly *right) {
  112. struct Poly *result = NULL;
  113. if (!(left == NULL || right == NULL || right->degree || right->term[0] < 0 || left->degree != 1 || left->term[0] || left->term[1] != 1 || !(result = allocPoly(right->term[0]))))
  114. result->term[right->term[0]] = 1;
  115. if (right != left)
  116. free(right);
  117. free(left);
  118. return result;
  119. }
  120. struct Poly *parsePoly(const char *polyIn) { // Takes an unmodifiable string, returns the poly, or NULL on error.
  121. static struct Poly *polyStack[operPrec(OPER_DONE) + 1];
  122. static oper_t operStack[operPrec(OPER_DONE) + 1];
  123. struct Poly **polyTop = polyStack;
  124. oper_t *operTop = operStack;
  125. struct Poly *poly = NULL;
  126. oper_t oper = OPER_DONE; // sentinal oper
  127. float dec = 1;
  128. float fpart = 0;
  129. while (true) { // loop through the string
  130. int sign = 1;
  131. *operTop = oper; // Push the current oper.
  132. oper = OPER_NONE; // No operator yet
  133. // First parse a term
  134. while (*polyIn == ' ' || *polyIn == '+' || *polyIn == '-') // parse sign and skip spaces
  135. if (*polyIn++ == '-') // check for '-' case (the ' ' and '+' cases are ignored) then skip over it.
  136. sign = -sign; // negate if there was a '-'
  137. if (isdigit(*polyIn) or *polyIn == '.') { // parse number
  138. *polyTop++ = poly; // Push the current poly
  139. poly = allocPoly(0); // Create a new poly big enough to contain a constant.
  140. do {
  141. if (__builtin_mul_overflow(poly->term[0], 10, &poly->term[0])) {
  142. free(poly);
  143. poly = NULL;
  144. } else {
  145. poly->term[0] += *polyIn++ - '0'; // parse and skip the number
  146. }
  147. } while (poly && isdigit(*polyIn));
  148. if ( *polyIn == '.'){
  149. polyIn++;
  150. do {
  151. fpart += (*polyIn++ - '0') * (dec *= .1);
  152. if(__builtin_mul_overflow(dec, 10, &dec)){
  153. free(poly);
  154. poly = NULL;
  155. }
  156. } while (poly && isdigit(*polyIn));
  157. }
  158. poly->term[0] += fpart;
  159. if (poly && sign < 0)
  160. poly->term[0] = -poly->term[0];
  161. } else if (*polyIn == 'x') { // parse a variable
  162. polyIn++; // skip over the x
  163. *polyTop++ = poly; // Push the current poly
  164. poly = allocPoly(1); // Create a new poly big enough to contain a constant.
  165. if (poly)
  166. poly->term[1] = sign;
  167. } else { // We are at the end, or the next character wasn't recognized
  168. if (*operTop != OPER_DONE)
  169. operTop--; // Ignore the top operator which is the invalid trailing operator, or OPER_IMP if there was no trailing operator
  170. oper = OPER_DONE; // This forces the OPER_DONE at the bottom of the operStack to eval, which exits, and prevents another operator from being parsed
  171. }
  172. // Then parse an operator
  173. if (oper == OPER_NONE) { // Don't parse an operator if we are done.
  174. while (*polyIn == ' ') polyIn++;
  175. switch (*polyIn) { // Look for an operator
  176. case '+':
  177. oper = OPER_ADD;
  178. polyIn++;
  179. break;
  180. case '-':
  181. oper = OPER_SUB;
  182. polyIn++;
  183. break;
  184. case '*':
  185. oper = OPER_MUL;
  186. polyIn++;
  187. break;
  188. case '/':
  189. oper = OPER_DIV;
  190. polyIn++;
  191. break;
  192. case '^':
  193. oper = OPER_POW;
  194. polyIn++;
  195. break;
  196. case '(':
  197. oper = OPER_LPAREN;
  198. polyIn++;
  199. break;
  200. case ')':
  201. oper = OPER_RPAREN;
  202. polyIn++;
  203. break;
  204. default: // Unknown operator, probably implicit multiplication
  205. oper = OPER_IMP;
  206. break;
  207. }
  208. }
  209. // Now that we know the next operator, evaluate previous operators
  210. while (operPrec(*operTop) <= operPrec(oper) || (oper == OPER_RPAREN && *operTop != OPER_LPAREN )) {
  211. struct Poly *left = *--polyTop, *right = poly; // pop the left operand
  212. switch (*operTop--) { // pop the oper
  213. case OPER_LPAREN:
  214. break;
  215. case OPER_ADD:
  216. poly = addPoly(left, right);
  217. break;
  218. case OPER_SUB:
  219. poly = subPoly(left, right);
  220. break;
  221. case OPER_IMP:
  222. case OPER_MUL:
  223. poly = mulPoly(left, right);
  224. break;
  225. case OPER_DIV:
  226. poly = divPoly(left, right);
  227. break;
  228. case OPER_POW:
  229. poly = powPoly(left, right);
  230. break;
  231. case OPER_DONE:
  232. if (*polyIn) { // We didn't get through the whole string, so error
  233. free(poly);
  234. return NULL;
  235. }
  236. return poly; // Otherwise, return the result
  237. }
  238. // All of the *Poly functions should free their arguments
  239. }
  240. ++operTop; // We are about to push oper (see the top of the loop)
  241. }
  242. }
  243. void printPoly(struct Poly *poly) {
  244. if (!poly)
  245. return;
  246. bool first = true;
  247. for (int i = poly->degree; i >= 0; --i) {
  248. int term = poly->term[i];
  249. if (term || (first && !i)) {
  250. char sign = '+';
  251. if (term < 0) {
  252. term = -term;
  253. sign = '-';
  254. }
  255. if (!first)
  256. putchar(' ');
  257. if (!first || sign == '-')
  258. putchar(sign);
  259. if (!first)
  260. putchar(' ');
  261. if (term != 1 || !i)
  262. printf("%u", term);
  263. if (i) {
  264. putchar('x');
  265. if (i > 1) {
  266. putchar('^');
  267. printf("%u", i);
  268. }
  269. }
  270. first = false;
  271. }
  272. }
  273. putchar('\n');
  274. }
  275.  
  276. int opp(int argc, char **argv) {
  277. if (argc < 2) errx(2, "not enough args");
  278. struct Poly *poly = parsePoly(argv[1]);
  279. if (!poly) errx(1, "parse error");
  280. printPoly(poly);
  281. free(poly);
  282. return 0;
  283. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement