# Untitled

a guest
Oct 16th, 2016
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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;
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 '+':
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;
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. }