#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char opstack [] = {'+','-','*','^'}; // operators, with precedence sorted from lowest to highest
typedef struct node
{
char * fx; // function
struct node * gx; // left-hand side
char * op; // operator
struct node * hx; // right-hand side
} node;
node * buildTree ( char * );
char * charToString ( char c )
{
char * str = malloc(sizeof(char) * 2);
str[0] = c;
str[1] = '\0';
return str;
}
char * grabNumber ( char * begin )
{
// Interpret *begin as the start of a double and add the characters to a
// string retstr
char * begincpy = begin;
int foundDot = 0;
while ((*begin >= '0' && *begin <= '9') || *begin == '.')
{
if (*begin == '.')
{
if (foundDot == 0) foundDot = 1;
else break;
}
++begin;
}
long n = begin - begincpy; // # of characters parsed
char * retstr = malloc(sizeof(char) * (n + 1)); // string to be returned
retstr[n] = '\0'; while (--n >= 0) retstr[n] = *--begin;
return retstr;
}
void toClosingParensOrEnd ( char * * pbegin )
{
// Given a character **pbegin='(' in a null-terminated character array,
// increment *pbegin until it is the closing parenthesis or the null character
int netRFP = 1; // net # of right-facing parantheses
do
{
++*pbegin;
if (**pbegin == ')') --netRFP;
else if (**pbegin == '(') ++netRFP;
} while (*pbegin && netRFP != 0); // while current character is not the closing paranthesis or off the end of the string
}
node * getNextExpression ( char * * begptr )
{
// begptr: pointer to a pointer to the character at the beginning of the expression
// returns the expression and increments *begptr to one after the expression
// returns null if the expression is invalid
node * result;
if (**begptr == 'x') // next expression is the variable 'x'
{
result = malloc(sizeof(node));
result->fx = "x"; result->gx = NULL; result->op = NULL; result->hx = NULL;
++*begptr;
}
else if ((**begptr >= '0' && **begptr <= '9') || **begptr== '.') // next expression is a number
{
result = malloc(sizeof(node));
result->fx = grabNumber(*begptr); result->gx = NULL; result->op = NULL; result->hx = NULL;
*begptr += strlen(result->fx);
}
else if (**begptr == '(') // next expression is enclosed in parantheses
{
char * cpy = *begptr;
toClosingParensOrEnd(begptr);
if (**begptr) // if found closing paranthesis
{
long n = *begptr - cpy; // distance from opening to closing paranthesis
char * betweenParens = malloc(sizeof(char) * n); // string between parantheses
betweenParens[--n] = '\0'; for (int k = 0; k < n; ++k) betweenParens[k] = *++cpy;
printf("Between parantheses: %s\n", betweenParens); // TEST
result = buildTree(betweenParens);
if (!result) printf("buildTree(betweenParents) returned NULL\n");
++*begptr; // increment to one after the closing paranthesis
}
else // didn't find closing paranthesis
{
result = NULL;;
}
}
else // character expected to be the beginning of an expression was not
{
result = NULL;
}
return result;
}
void insertInTree ( node * * curRootPtr, char * newOp, node * newNode )
{
// crpp: Pointer to a pointer to the node element that is the current root
// newOp: New operator found
// newNode: New node corresponding to the expression following the operator
node * rightTraveler = *curRootPtr;
while (1)
{
if (rightTraveler->op)
{
long thisOpIdx = strchr(opstack, *rightTraveler->op) - opstack;
long newOpIdx = strchr(opstack, *newOp) - opstack;
if (thisOpIdx > newOpIdx) break; // if new operator has a lower precendence than the
// operator on the current node,
rightTraveler = rightTraveler->hx;
}
else // reached a node that has no children
{
break;
}
}
node * temp = rightTraveler;
rightTraveler = malloc(sizeof(node));
rightTraveler->gx = temp; rightTraveler->op = newOp; rightTraveler->hx = newNode;
}
node * buildTree ( char * fstr )
{
node * rootptr = NULL;
char * curptr = fstr;
node * thisexpr = getNextExpression(&curptr);
if (thisexpr) printf("expression: %s\n", thisexpr? thisexpr->fx : "[Parent expression, no fx]"); // TEST
if (!thisexpr)
{
printf("Could not parse beginning expression of equation beginning with character %c.\n", *fstr);
return NULL;
}
rootptr = thisexpr;
while (*curptr)
{
char thisop = *curptr;
char * opidx = strchr(opstack, thisop);
if (!opidx) // current character was not an operator
{
printf("Found %c where an operator was expected.\n", thisop);
return NULL;
}
printf("operator: %c\n", thisop); // TEST
++curptr; // increment to character following the operator
thisexpr = getNextExpression(&curptr);
if (!thisexpr) // invalid expression following operator
{
printf("Could not parse expression. Stopped at index %d, character %c.\n", (int)(curptr-fstr), *curptr);
return NULL;
}
if (thisexpr) printf("expression: %s\n", thisexpr->fx); // TEST
insertInTree(&rootptr, &thisop, thisexpr);
}
// ...
return rootptr;
}
char * deriveFromTree ( node * rt )
{
//char * dfdx = malloc(100*sizeof(char));
char * dfdx;
if (rt->op) // if rt is of the form rt = gx op hx
{
char * dgdx = deriveFromTree(rt->gx); // g'(x)
char * dhdx = deriveFromTree(rt->hx); // h'(x)
char thisop = *rt->op;
if (thisop == '+' || thisop == '-')
{
// ADDITION/SUBTRACTION RULE:
// dfdx = dgdx + thisop + dhdx
long n = strlen(dgdx) + strlen(dhdx) + 2;
dfdx = malloc(sizeof(char) * n); dfdx[n-1]='\0';
dfdx = strcat(dfdx, dgdx);
dfdx = strcat(dfdx, charToString(thisop));
dfdx = strcat(dfdx, dhdx);
}
else if (thisop == '*')
{
// PRODUCT RULE:
// dfdx = gx * dhdx + hx * dgdx
}
else if (thisop == '/')
{
// ...
}
else if (thisop == '^')
{
// ...
}
}
else // rt is a base expression -- x or a constant
{
dfdx = malloc(sizeof(char) * 2);
dfdx[0] = strcmp(rt->fx, 'x') ? '1': '0';
dfdx[1] = '\0';
}
return dfdx;
}
int main ( int argc, const char * argv [] ) {
char function [] = "x+1";
node * rootptr = buildTree(function);
puts(rootptr ? deriveFromTree(rootptr) : "Invalid function. ");
return 0;
}