I'm not convinced that your code handles terms that don't start with a number (such as just an x). Also,
strstr finds the first instance of an entire
substring, not the first instance of a set of characters, which I guess
strcspn does. You can't assign to an array in C with
array = { ...
}; except when it is first initialized. After that you have to use
nextOp[1] = ...
;, etc. There's no general way to implement min in C as you call it, because passing arrays as arguments loses sizing information, and in addition, variables and functions can't have the same name (if you want to use both). Normally, you would do something like
uint8_t min = array_min(nextOp, 4);. Comparing strings for equality doesn't do what you expect in C so you probably want
if (polyIn[i] != '\0') which is identical to
if (polyIn[i]). Lastly,
strcpy copies an entire string and only takes two arguments. You could use
strncpy to copy no more that the third argument's number of characters or
memcpy to copy exactly that many characters (bytes). Although, I'm not entirely sure what the purpose of Ops_OutputStack is, since in the end, it just contains the entire input exactly.
A simpler way to do all this is to just treat ^ and implicit multiplication as actual operators with the correct precedence. Here's how I would do it, though this is by no means the only way:
Code: #include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <err.h>
enum Oper {
OPER_NONE,
OPER_POW, // prec = 0
OPER_IMP = 3, // prec = 1
OPER_DIV, // prec = 2
OPER_MUL, // prec = 2
OPER_SUB, // prec = 3
OPER_ADD, // prec = 3
OPER_DONE // prec = 4
};
typedef uint8_t oper_t;
#define operPrec(op) ((op) >> 1)
struct Poly {
int degree; // This is the maximum power.
int term[1]; // This contains the coefficient of degree + 1 terms (the [1] is for portability).
};
struct Poly *allocPoly(int degree) {
struct Poly *result = calloc(2 + degree, sizeof(int));
if (result)
result->degree = degree;
return result;
}
struct Poly *addPoly(struct Poly *left, struct Poly *right) {
struct Poly *result = left, *other = right;
if (left == NULL || right == NULL) {
if (right != left)
free(right);
free(left);
return NULL;
}
if (left->degree < right->degree) {
result = right;
other = left;
}
for (int i = 0; i <= other->degree; ++i)
result->term[i] = left->term[i] + right->term[i];
if (other != result)
free(other);
return result;
}
struct Poly *subPoly(struct Poly *left, struct Poly *right) {
struct Poly *result = left, *other = right;
if (left == NULL || right == NULL) {
if (right != left)
free(right);
free(left);
return NULL;
}
if (left->degree < other->degree) {
result = right;
other = left;
}
for (int i = 0; i <= left->degree; ++i)
result->term[i] = left->term[i] - right->term[i];
if (other != result)
free(other);
return result;
}
struct Poly *mulPoly(struct Poly *left, struct Poly *right) {
int newDegree;
struct Poly *result;
if (left == NULL || right == NULL || __builtin_add_overflow(left->degree, right->degree, &newDegree) || !(result = allocPoly(newDegree))) {
if (right != left)
free(right);
free(left);
return NULL;
}
for (int i = 0; i <= left->degree; i++)
for (int j = 0; j <= right->degree; j++)
result->term[i + j] += left->term[i] * right->term[j];
if (right != left)
free(right);
free(left);
return result;
}
struct Poly *divPoly(struct Poly *left, struct Poly *right) {
if (right != left)
free(right);
free(left);
return NULL;
}
struct Poly *powPoly(struct Poly *left, struct Poly *right) {
struct Poly *result = NULL;
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]))))
result->term[right->term[0]] = 1;
if (right != left)
free(right);
free(left);
return result;
}
struct Poly *parsePoly(const char *polyIn) { // Takes an unmodifiable string, returns the poly, or NULL on error.
static struct Poly *polyStack[operPrec(OPER_DONE) + 1];
static oper_t operStack[operPrec(OPER_DONE) + 1];
struct Poly **polyTop = polyStack;
oper_t *operTop = operStack;
struct Poly *poly = NULL;
oper_t oper = OPER_DONE; // sentinal oper
while (true) { // loop through the string
int sign = 1;
*operTop = oper; // Push the current oper.
oper = OPER_NONE; // No operator yet
// First parse a term
while (*polyIn == ' ' || *polyIn == '+' || *polyIn == '-') // parse sign and skip spaces
if (*polyIn++ == '-') // check for '-' case (the ' ' and '+' cases are ignored) then skip over it.
sign = -sign; // negate if there was a '-'
if (isdigit(*polyIn)) { // parse number
*polyTop++ = poly; // Push the current poly
poly = allocPoly(0); // Create a new poly big enough to contain a constant.
do {
if (__builtin_mul_overflow(poly->term[0], 10, &poly->term[0])) {
free(poly);
poly = NULL;
} else {
poly->term[0] += *polyIn++ - '0'; // parse and skip the number
}
} while (poly && isdigit(*polyIn));
if (poly && sign < 0)
poly->term[0] = -poly->term[0];
} else if (*polyIn == 'x') { // parse a variable
polyIn++; // skip over the x
*polyTop++ = poly; // Push the current poly
poly = allocPoly(1); // Create a new poly big enough to contain a constant.
if (poly)
poly->term[1] = sign;
} else { // We are at the end, or the next character wasn't recognized
if (*operTop != OPER_DONE)
operTop--; // Ignore the top operator which is the invalid trailing operator, or OPER_IMP if there was no trailing operator
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
}
// Then parse an operator
if (oper == OPER_NONE) { // Don't parse an operator if we are done.
while (*polyIn == ' ') polyIn++;
switch (*polyIn) { // Look for an operator
case '+':
oper = OPER_ADD;
polyIn++;
break;
case '-':
oper = OPER_SUB;
polyIn++;
break;
case '*':
oper = OPER_MUL;
polyIn++;
break;
case '/':
oper = OPER_DIV;
polyIn++;
break;
case '^':
oper = OPER_POW;
polyIn++;
break;
default: // Unknown operator, probably implicit multiplication
oper = OPER_IMP;
break;
}
}
// Now that we know the next operator, evaluate previous operators
while (operPrec(*operTop) <= operPrec(oper)) { // of valid precedence
struct Poly *left = *--polyTop, *right = poly; // pop the left operand
switch (*operTop--) { // pop the oper
case OPER_ADD:
poly = addPoly(left, right);
break;
case OPER_SUB:
poly = subPoly(left, right);
break;
case OPER_IMP:
case OPER_MUL:
poly = mulPoly(left, right);
break;
case OPER_DIV:
poly = divPoly(left, right);
break;
case OPER_POW:
poly = powPoly(left, right);
break;
case OPER_DONE:
if (*polyIn) { // We didn't get through the whole string, so error
free(poly);
return NULL;
}
return poly; // Otherwise, return the result
}
// All of the *Poly functions should free their arguments
}
++operTop; // We are about to push oper (see the top of the loop)
}
}
void printPoly(struct Poly *poly) {
if (!poly)
return;
bool first = true;
for (int i = poly->degree; i >= 0; --i) {
int term = poly->term[i];
if (term || (first && !i)) {
char sign = '+';
if (term < 0) {
term = -term;
sign = '-';
}
if (!first)
putchar(' ');
if (!first || sign == '-')
putchar(sign);
if (!first)
putchar(' ');
if (term != 1 || !i)
printf("%u", term);
if (i) {
putchar('x');
if (i > 1) {
putchar('^');
printf("%u", i);
}
}
first = false;
}
}
putchar('\n');
}
int main(int argc, char **argv) {
if (argc < 2) errx(2, "not enough args");
struct Poly *poly = parsePoly(argv[1]);
if (!poly) errx(1, "parse error");
printPoly(poly);
free(poly);
return 0;
}
It also looks like "polyaio.h" doesn't exist in your source directory.