Cags's C-Learning Thread
» > >
» Goto page Previous  1, 2, 3, 4, 5, 6  Next
» View previous topic :: View next topic  
Wow, I didnt realize how simple that would be, but I'll have to modify that for letters, operations, and parentheses. I havent yet created the lookup string, but I did create normal/alpha toggle and i added a character limiter to your code.


Code:
uint8_t inputMode = 0;  /* 0 = normal, 1 = alpha */
const char charsAlpha[] = "\0\0\0\0\0\0\0\0\0\0\"WRMH\0\0?[VQLG\0\0:ZUPKFC\0 YTOJEB\0\0XSNIDA\0\0\0\0\0\0\0\0";
const char charsNorm[] = "";
uint8_t key, i = 0;

while((key = os_GetCSC()) != sk_Enter) {
    if(key == sk_Alpha) {
        inputMode = (inputMode == 0);
    }
    if(chars[key] and i<257) {
        if(inputMode == 0){
            inputBuffer[i++] = charsNorm[key];
        }
        if(inputMode == 1){
            inputBuffer[i++] = charsAlpha[key];
        }
    }
}


As an aside I HAD been updating properly, but XCode doesnt update files added to the project. You have to add the folder. Its weird. :p

Edit: I compiled the normal char list. The issue with this is some of these tokens are two bytes. Did I do this right, or do I have to declare the number tokens too?

Code:
const char charsNorm[] = "\0\0\0\0\0\0\0\0\0\0+-*/^\0" + tChs + "\0369)" + tTan + "\0\0.258(" + tCos + "\0\00147\0" + tSin + "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";


Edit 2: Is there a fast way in C so do a copy of bytes from a location to location+1 for a certain range of bytes?
Check out memcpy and memmove.
MateoConLechuga wrote:
Check out memcpy and memmove.

I had a feeling it would involve that. As for my charsNormal string, will I need to make 2-byte tokens? Some of them are two bytes? And for the other ones that have token defines, do I need to specify the token values, or can I leave them in string like that?

Edit: Unless I have to do something more with the charsNormal string, the string input routine seems to be done. Ya'll can scan for some obvious mistakes, let me know how i did :p. This and processing that string into an array of polynomial coefficients might be the hardest part of the entire program. (Yes, this is a re-write of Polynomials AIO for the CE).


Code:
getString(&polyIn){
    uint8_t inputMode = 0;  /* 0 = normal, 1 = alpha */
    uint8_t insertMode = 0; /* 0 = insert off, 1 = insert on */
    const char charsAlpha[] = "\0\0\0\0\0\0\0\0\0\0\"WRMH\0\0?[VQLG\0\0:ZUPKFC\0 YTOJEB\0\0XSNIDA\0\0\0\0\0\0\0\0";
    const char charsNorm[] = "\0\0\0\0\0\0\0\0\0\0+-*/^\0" + tChs + "\0369)" + tTan + "\0\0.258(" + tCos + "\0\00147\0" + tSin + "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
    uint8_t key, i = 0;

    while((key = os_GetCSC()) != sk_Enter) {
        if(key == sk_Alpha) {
            inputMode = (inputMode == 0);
        }
        if(key == sk_Mode){
            insertMode = (insertMode == 0);
        }
        if(key == sk_Left){
            i--;
        }
        if(key == sk_Right){
            i++;
        }
        if(key == sk_Del) {
            polyIn[i--] = "\0";
        }
        if(key == sk_Clear) {
            memset(polyIn, 0, 257);
            i = 0;
        }
        if(chars[key] and i<257) {
            if(insertMode == 1){
                memmove(polyIn[i], polyIn[i+1], 256-i);
            }
            if(inputMode == 0){
                polyIn[i++] = charsNorm[key];
            }
            if(inputMode == 1){
                polyIn[i++] = charsAlpha[key];
            }
        }
    }
}
bump/update:

Next step in this program is an order of operations parser. For this I understand the concept of shunting yard, but I need some suggestions/advice.

1. First, in places like 4x + 7x^2, can I write in the whole term (like 4x) for instance, and save myself the computations involved in splitting 4x into 4*x? With polynomials, you kinda dont even need to split up terms.

I'm going to work on an OOP and as I do, post snippets for checking. Smile
Assuming that code was supposed to be C and not pseudocode or something, it has some errors:


Code:
getString(&polyIn){

First, all functions need a return type. If there is no returned value, then use void. Second the polyIn argument needs a type (maybe a uint8_t *?), and also, & can't be used in C types anyway (it is used for C++ references though).


Code:
const char charsNorm[] = "\0\0\0\0\0\0\0\0\0\0+-*/^\0" + tChs + "\0369)" + tTan + "\0\0.258(" + tCos + "\0\00147\0" + tSin + "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";

You can't use + with strings in C. The most readable fix for this is to use array initialization syntax:

Code:
const char charsNorm[] = { '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '+', '-', '*', '/', '^', '\0', tChs, '\0', '3', '6', '9', ')', tTan, '\0', '\0', '.', '2', '5', '8', '(', tCos, '\0', '\0', '0', '1', '4', '7', '\0', tSin, '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0' };

Note that these are all 1-byte tokens, but if you ever needed 2-byte tokens, you would need to use uint16_t instead of char.


Code:
memmove(polyIn[i], polyIn[i+1], 256-i);

polyIn[i] loads the uint8_t at index i from memory, at which point it doesn't make sense as an argument to memmove. Two equivalent ways to do this correctly are &polyIn[i] and polyIn + i, both of which get the address of the ith element of polyIn.


Code:
if(chars[key] and i<257) {

You need to use && for and in C (unless you #include <iso646.h>).

Also, this isn't a bug but

Code:
inputMode = (inputMode == 0);

is more readable if you do

Code:
inputMode = !inputMode;
Thanks for that! As far as the below quoted bit, if any of the tokens are two bytes, I'm assuming the entire string needs to be 2-byte, and that any one byte tokens within it would then need padding?
jacobly wrote:


Code:
const char charsNorm[] = "\0\0\0\0\0\0\0\0\0\0+-*/^\0" + tChs + "\0369)" + tTan + "\0\0.258(" + tCos + "\0\00147\0" + tSin + "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";

You can't use + with strings in C. The most readable fix for this is to use array initialization syntax:

Code:
const char charsNorm[] = { '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '+', '-', '*', '/', '^', '\0', tChs, '\0', '3', '6', '9', ')', tTan, '\0', '\0', '.', '2', '5', '8', '(', tCos, '\0', '\0', '0', '1', '4', '7', '\0', tSin, '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0' };

Note that these are all 1-byte tokens, but if you ever needed 2-byte tokens, you would need to use uint16_t instead of char.
No, if you just replace char with uint16_t and use the { ... } syntax then everything will take up two bytes automatically. To include a 2 byte token you would do something like

Code:
uint16_t test = {
   'A', // some char
   tA, // same as the 'A'
   tChs, // one-byte token
   t2ByteTok << 8 | tLa // two-byte token
};
Thanks for that! Now in the charsNormal section of code, since we're writing in two bytes instead of one, will I have to advance i (i++) a second time?
ACagliano wrote:
Thanks for that! Now in the charsNormal section of code, since we're writing in two bytes instead of one, will I have to advance i (i++) a second time?

Nah, because of C pointer magicness.
Awesome!! So seems like that is done! Now, onto an operator precedence parser. Here is what I understand:

1. Process string LTR.
2. Push any numbers to output in the order in which they occur.
3. Push any operators to temporary operator stack in order they occur. If one currently being pushed has higher precedence than last one, push last one to output and current one to temporary stack.
4. If you encounter a right parenthesis, push operators from stack to output until you hit a left parenthesis.
5. When you hit the end of the input string, pop everything remaining on the operator stack to output.

Do I have this right? Shouldn't be too hard to handle in C.


Edit: here is the start of my OPP parser. Some notes... I do not plan to split a term like 7x^3 into 7, x, and 3. I'll just push the 7x^3 as is. Saves myself having to iterate the parser 2 times per term.

Could I, instead of all these tests and stuff, keep looping copying chars to ouput until I hit an operator or a null character?


Code:
void parseString(&polyIn){
    uint8_t parserEnd = strlen(polyIn), i = 0;
    uint8_t nextOp[4];
    while( i <= parserEnd ){
        if(strstr(polyIn[i], "0123456789")){
            /* Seems we have encountered start of a term
             Now we need to find the end of it (next occurence of +,-,*, or / */
            nextOp[] = {
                strchr(polyIn + i, '+') - i,
                strchr(polyIn + i, '-') - i,
                strchr(polyIn + i, '*') - i,
                strchr(polyIn + i, '/') - i
                };
                      uint8_t min = min(nextOp);
            strcpy(Ops_OutputStack + i, polyIn + i, min - 1);
            i = i + min - 1;
            if( polyIn[i] != "\0" ){
                cp_precedence(polyIn[i]);
            }
           
        }
       
    }
}

uint8_t min(uint8_t a[]) {
    uint8_t a;
    val = a[0] * ( a[0] < a[1] ) + a[1] * ( a[1] < a[0] );
    val2 = a[2] * ( a[2] < a[3] ) + a[3] * ( a[3] < a[2] );
    uint8_t min = val * ( val < val2 ) + val2 * ( val2 < val );
    if( !min ){
        min = a[4];
    }
    return min;
}

bool cp_precedence(char a){
    if(){}
// still working on this!
}
   

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;
}
jacobly wrote:
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])) {
               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;
}


Thanks, I'll have to evaluate your code to figure out how it works and if i'll need to modify it at all. Am I correct in the assumption it handles variables (a-z), or at least x,y,z?
As far as some of the things you pointed out in my code, still learning :p. So and yea, I needed to handle the (-) negation sign, and strings starting with a variable. I just hadn't added in handling for that. To make a long story short, my code was gonna be novicely overcomplicated.

A second, easier question to answer is the token for the negation sign. I've seen sk_Chs for change sign, but I don't actually see the token in the list for the (-). Is it tChs? Or what is its value?
My code was an example of converting an ascii string into a polynomial in terms of x (so x is the only letter supported). It will definitely need to be modified to run on calc. As for the negative sign, yes the token is tChs = 0xB0 on calc.
jacobly wrote:
My code was an example of converting an ascii string into a polynomial in terms of x (so x is the only letter supported). It will definitely need to be modified to run on calc. As for the negative sign, yes the token is tChs = 0xB0 on calc.

Ok awesome! I'll scan through it and make the modifications. I already can see one thing needing modification.. putchar :p haha.
Bump. So some questions about the code you supplied. I noticed you tossed in some error catching for negative exponents. In my TI-Basic version, I also added similar catching for negative exponents. How trivial/non-trivial would it be to add support for negative exponents, be it through allocating memory areas for negative exponents or appending 1/[the term with negative exponent]?

Secondly, I noticed the division routine isn't implemented. I'm gonna give that a try myself and post up code. As far as mulPoly goes, is that fully implemented?

Edit: Some psuedocode for division.

Code:
struct Poly *divPoly(struct Poly *left, struct Poly *right) {
    struct Poly *result, *temp, *remainder;
    /* copy right to temp */
    if (test for errors){
        if (right != left)
            free(right);
        free(left);
        return NULL;
    }
    int j = temp->term;
    while(/* degree remainder > degree divisor */){
        /* divide leading term divisor into leading term temp
         answer becomes first term of result.
         Multiply that term by divisor to get new poly.
         temp = temp - new poly;
         repeat algorithm */
    }
}


Edit 2: Began converting some psuedo-code into actual code. Some things I'm not sure about... matching up the correct terms in the second for loop, and how to ensure *result is the correct size.


Code:
struct Poly *divPoly(struct Poly *left, struct Poly *right) {
    struct Poly *result, *remainder = left, *temp;
    if (test for errors){
        if (right != left)
            free(right);
        free(left);
        return NULL;
    }
    while(remainder->degree > right->degree){
        temp = right;
        /* divide leading term divisor into leading term temp
         Answer becomes first term of result */
        int factor = remainder->term[remainder->degree] / right->term[right->degree];
        /* multiply factor by temp */
        for ( int i = 0; i <= temp->degree; ++i ){
            temp->term[i] = temp->term[i] * factor;
        }
        /* subtract temp from remainder */
        for ( int i = remainder->degree; i >= temp->degree; --i ){
            remainder->term[i] = remainder->term[i] - temp->term[i];
        }
        /* somehow we will need to adjust remainder to the correct degree to make this work */
       
    }
}


Edit 3, a few other questions. I modified your code to provide float support for the input (fractional coefficients) in the following manner. Would this work?


Code:
struct Poly {
    int degree; // This is the maximum power.
    float term[1]; // This contains the coefficient of degree + 1 terms (the [1] is for portability).
};
...
...
// right after the first do...while loop in parsePoly()
// dec is initialized to 10 before this would run
if ( *polyIn == '.'){
                polyIn++;
                do {
                    fpart += (*polyIn++ - '0') / dec;
                    if(__builtin_mul_overflow(dec, 10, dec)){
                        poly = NULL;
                    }
                } while (poly && isdigit(*polyIn));
            }
            poly->term[0] += fpart;
If you wanted to support negative exponents, you would need to keep track of both the minimum and maximum degree and subtract the minimum degree from all term accesses.

To update a degree, you would just use a loop:

Code:
while (poly->degree && poly->term[degree] == 0) poly->degree--;


If you divide two integers in C you get a truncated integer result. You can either cast one of the arguments like:

Code:
fpart += (float)(*polyIn++ - '0') / dec;

or you could just make dec a float to begin with, in which case it would be faster to do:

Code:
float dec = 1;
// ...
fpart += (*polyIn++ - '0') * (dec *= .1); // no need to check for overflow on floats


Edit: I just noticed that there's a problem with my code and poly = NULL; should have been free(poly); poly = NULL;.
The code as I now have it, with division partially implemented, and floats supported. Still a little unsure if exponents needs to be done or not.

http://pastebin.com/cgP8JVFY
For supporting parentheses, something like this might work:

Code:
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_PAREN,   // prec = 4
   OPER_DONE     // prec = 4
};

Code:
      // Now that we know the next operator, evaluate previous operators
      while (operPrec(*operTop) <= operPrec(oper)) { // of valid precedence
         switch (*operTop--) { // pop the oper
            case OPER_ADD:
               poly = addPoly(*--polyTop, poly); // pop the left poly
               break;
            case OPER_SUB:
               poly = subPoly(*--polyTop, poly); // pop the left poly
               break;
            case OPER_IMP:
            case OPER_MUL:
               poly = mulPoly(*--polyTop, poly); // pop the left poly
               break;
            case OPER_DIV:
               poly = divPoly(*--polyTop, poly); // pop the left poly
               break;
            case OPER_POW:
               poly = powPoly(*--polyTop, poly); // pop the left poly
               break;
            case OPER_PAREN:
               oper = OPER_NONE; // this breaks out of the outer while
               break;
            case OPER_DONE:
               if (*polyIn || oper == OPER_PAREN) { // We didn't get through the whole string, or too many ), so error
                  free(poly);
                  return NULL;
               }
               return poly; // Otherwise, return the result
         }
         // All of the *Poly functions should free their arguments
      }

Code:
int opp(int argc, char **argv)

what are these arguments for?

Edit: I'm trying to build pieces of the code and I'm getting this. I have included ALL configuration settings, and the output of the build command.

Code:

Build target polyaio-ce of project polyaio-ce with configuration Debug

    /opt/local/bin/wine /Users/acagliano/CEdev/bin/make.exe

Z:\Users\acagliano\CEdev\source\polyaio-ce\src\main.c
\USERS\ACAGLIANO\CEDEV\INCLUDE\LIB\CE\GRAPHC.H   (3,9) :   WARNING (38) "The graphc library is deprecated! The graphx library should be used instead "
Z:\USERS\ACAGLIANO\CEDEV\SOURCE\POLYAIO-CE\SRC\MAIN.C   (61,15) :   WARNING (197) No function prototype "gfx_Begin" in scope
Z:\USERS\ACAGLIANO\CEDEV\SOURCE\POLYAIO-CE\SRC\MAIN.C   (61,24) :   ERROR (128) Identifier "gfx_8bpp" not defined within current scope
Z:\USERS\ACAGLIANO\CEDEV\SOURCE\POLYAIO-CE\SRC\MAIN.C   (62,27) :   WARNING (197) No function prototype "gfx_SetDefaultPalette" in scope
Z:\USERS\ACAGLIANO\CEDEV\SOURCE\POLYAIO-CE\SRC\MAIN.C   (63,22) :   WARNING (197) No function prototype "lcl_renderSplash" in scope
Z:\USERS\ACAGLIANO\CEDEV\SOURCE\POLYAIO-CE\SRC\MAIN.C   (68,18) :   WARNING (197) No function prototype "prgm_Cleanup" in scope
Z:\USERS\ACAGLIANO\CEDEV\SOURCE\POLYAIO-CE\SRC\MAIN.C   (174,9) :   ERROR (217) Cannot open include file "polyaio.h"
make: *** [obj/main.obj] Error -1
Command /opt/local/bin/wine failed with exit code 2


I'm so frustrated with this im reinstalling Parallels Desktop to compile :p
Seems like you included the lib "graphc" instead of the new one "graphx". Use "graphx" instead, and I'm sure most of the problems are solved Wink
Sola Fide
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Cags's C-Learning Thread
» Goto page Previous  1, 2, 3, 4, 5, 6  Next
» View previous topic :: View next topic  
Page 2 of 6
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement