API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 16th, 2016
109
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.34 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!