Here's a C problem

[crosswire]

Let me know how you would do it.

I will prepare my psuedo code, and try to mimick a person working out the equation. As a result, it may not be efficient in terms of speed and memory usage. A stack would not be necessary in the design, but it would help memory usage; not very critical for a small program, but it will make the perfectionists out there happy.

Google SimplexParser.
http://www.topshareware.com/SimplexP...load-19003.htm
I downloaded the C/C++ source code a long time ago. It is an independent implementation.

We techies want to sharpen our skills, and pass idle time. We need more fun programs like this to write.

[crosswire]

it wasn't perfect i wanted to add precedence and better error checking but i didn't got the time for it. Even though while writing it it seems like i was doing work (cause i was writing code) but sooner or later somone would have recognized that it has nothing to do with the project im working on, so i just made it work. Im a bit of a perfectionist so i didn't like the code actually.

Not doing work work is just as bad as not doing school work

I am still playing with the program and I cannot believe that it is working because the code is short even when minus the precedence.

I might be able to add precedence by sorting the input term, and rearranging in order of highest priorty operation first.

[leoandru]

Alright cool, let me see the modified version when ur done. Im going to think about the 2nd question as soon as i get off work.

[crosswire]

OK, the modified version will place all the '*' and '/' at the front. I will work it that way

[crosswire]

@Leoandru,
I thought a modification would work, I was almost sure of it, but it will not work.

I looked at a*b+c*a+d*a*c-b*c/a+b/a and I was going to place all the '*','/' at the front but doing this would have messed up what the term was saying. Picture all the '*'s being together, and they do not convey the same meaning or value as the original term.

So a new plan, maybe I could break up the original term into sub-terms. Eg this term "a*b+c*a+d*a*c-b*c/a+b/a" gives sub-terms a*b , c*a , d*a*c , b*c/a , b/a. Then I evaluate the sub-terms and sum the results. This may work, but as a perfectionist too, I see it as hard to upgrade.

@TJRAK,
I think I see your intention with using a stack. You could work out the first operation and if its operands need to be evaluated, you would then resurse a calculation for each operand and so on. However you would use a stack as a substitute for the recursive calls. Still want to hear from you, with the stack idea.

(Next time I want to drop a problem with a text undo buffer or some rat AI in a maze, but one thing at a time.)

[leoandru]

@Leoandru,
I thought a modification would work, I was almost sure of it, but it will not work.

I looked at a*b+c*a+d*a*c-b*c/a+b/a and I was going to place all the '*','/' at the front but doing this would have messed up what the term was saying. Picture all the '*'s being together, and they do not convey the same meaning or value as the original term.

So a new plan, maybe I could break up the original term into sub-terms. Eg this term "a*b+c*a+d*a*c-b*c/a+b/a" gives sub-terms a*b , c*a , d*a*c , b*c/a , b/a. Then I evaluate the sub-terms and sum the results. This may work, but as a perfectionist too, I see it as hard to upgrade.

hmmmh like the idea but ur right about the upgarding part. I was thinking about making a pass over the array and removing the * and / operators by calculation using the both operands around the operator.
take for example a+b*c/d
the first pass will have
a+q1/d
where q1 = b*c

the second pass will give
a+q2
where q2 = q1/d

and so on.

then we will be left with simple addition and subtraction to deal with. umm let me know what u think.

[TJRAK]

@Leoandru,

@TJRAK,
I think I see your intention with using a stack. You could work out the first operation and if its operands need to be evaluated, you would then resurse a calculation for each operand and so on. However you would use a stack as a substitute for the recursive calls. Still want to hear from you, with the stack idea.

I was thinking along that line then. But when I went home last night and start thinking about it, a stack is not necessary (not a bad idea tho). started thinking along the lines that Leoandru is thinking. Kinda behind in my class preparation so if you people don't solve it by weekend I'll try and create a simple solution

[crosswire]

OK here is a psuedo code. I know that you all are pretty busy so I will pitch in most of the coding.

/*
Pseudo code

We are trying to solve a term like "a+(b*c-a)*(c/b)"

1. Validate eqaution (1b part not important, but hard still)
1a. Remove redundant spaces and brackets, eg convert a *b to a*b, and convert b+(a) to b+a
1b. Check for invalid characters, and operators, also check for typos eg print error if a*+b is used.

2. Search term for position of most precedence operator and respect all brackets
2a. Search for the most precedence operator. Start looking for any '*'
2b. When found, check if it is indeed the most precedent by checking if its operands have brackets eg a*(b..
2c. If operands have brackets, continue searching the term for another '*'
2d. If operands do not have brackets, most precedence operator is found and return its handle
2e. If '*' is not found, search for '/' (because we cannot calculate any '*' at this point)
2f. Repeat the same proceedure so far, until we can execute something.
2g. When we found something we return the position of the opertator handle to be calculated.
2h. For every use of this search, we must start at 2a or initialize properly.

3. Calulate the result of the operation using the operands on the left and right of that position and save it
3a By using the operator position, take the operands and the operator handles to our calculator, eg 'a' 'c' and '*'
3b Use the handles 'a' and 'c' to load to floating point values for calulation.
3c Save the floating point result into a array of temporary results, using an empty or un-used slot in the array.
3d Pass the handle of this tempoary result back as a return, eg return 'q01' which is our handle to a temporary result which is located in the array in position q01=1st position. The tracking of empty result slots are handled here.
3e Update the equation by inserting the new handle "q01" as a replacement for the previous "a*c", clean up redundant spaces and brackets again eg "(q01)" becomes 'q01'

4. Loop until done.


class TermSolver

OriginalEquation
ModifiedEquation
ParameterValues
ParameterHandles
OperaterList
*/

In the psuedo, I previously had 'h' as a temporary result location and not 'q01'. A string like 'qnn' would give more temporary result locations but I had an idea to encode the equation to 32bit handles for operators and operands instead of 8bit char handles. I doubt I am going to do that still, but it would not be a bad idea.

[TJRAK]

Didn't get a chance to work on this but I found something similar to it that I did while at UTECH. Think I can make it better but...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
#include <iomanip>



///////////////////////////////////////////////////////////////////////////////

struct stack{        //declaration of stack
	int val;
	struct stack *next;   //use to store values for calculation
};

typedef struct stack element;     // defining element as type stack
typedef element *top;             // defining a pointer to type element

int isempty (top t){             // check for empty stack and return
	return(t==NULL);					// NULL if empty
}

int vtop(top t){                // Return the top of the the stack
	return(t->val);
}

void pop(top *t, int *c){       // pop the top entry from the stack
	top t1 = *t;
	if(!isempty(t1)){
		*c = t1->val;
		*t = t1->next;
		free(t1);
	}
}

void push(top *t, int c){     // push values onto the stack
	top tmp;
	tmp = (top)malloc(sizeof(element));   //reallocate memory for the stack
	tmp->val = c;
	tmp->next = *t;
	*t = tmp;
}

///////////////////////////////////////////////////////////////////////////////

                          // function use to do calculation of values.
int calculate( int first, char func, int second)
{
   int ans;
	if (func=='*')
   	ans=(first * second);
   else
   if (func=='/')
   	ans= (first / second);
   else
   if (func=='+')
   	ans= (first + second);
   else
   if (func=='-')
   	ans= (first - second);
   return ans;
}


char oper[] = {'+', '-', '*', '/'}; //Operators to be used in calculation

bool isoperator(char c);
void postfix(char[]);
void infix (char []);
void prefix (char *);
void determine(char *);
void associate();
void unary(char *);
//^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^

void main ()
{						
	char choice;
	char expression[15];

	do{
		system("CLS"); //clrscr();
/**////////////////////// Menu Option For Program  //////////////////////////**/
/**/                                                                        /**/
/**/		printf("\t^-^^-^^-^^-^^-^^-^ CHOOSE OPERATION ^-^^-^^-^^-^^-^^-^");/**/
/**/		printf("\n\n");                                                    /**/
/**/		printf("\t\t1. Prefix, Infix or Postfix");                         /**/
/**/		printf("\n");                                                      /**/
/**/		printf("\t\t2. Associated List");                                  /**/
/**/		printf("\n");													   /**/
/**/		printf("\t\t3. Unary Plus or Minus");                              /**/
/**/		printf("\n");                                                      /**/
/**/		printf("\t\t0. Exit Program");                                     /**/
/**/		printf("\n\n");                                                    /**/
/**/		printf("\t\tEnter Choice: ");                                      /**/
/**/                                                                        /**/
/**//////////////////////////////////////////////////////////////////////////**/
		choice = getche();

		system("CLS"); //clrscr();

	switch (choice)                // Switch for choosen option
   {
   	   case '0':      	       // Exits Program
         exit(1);
         break;

	   case '1':                  // Use for infix, postfix and prefix expression
		   printf("\t^-^^-^^-^^-^^-^ Prefix, Infix or Postfix ^-^^-^^-^^-^^-^");
		   printf("\n\n\tEnter expression for parsing: ");// Prompt user for input
		   gets(expression);
		   determine(expression); 
         break;

      case '2':                   // Use for associated list  of expressions
		  printf("\t^-^^-^^-^^-^^-^^-^ Associated List ^-^^-^^-^^-^^-^^-^");
		  associate();
         break;

      case '3':                   // usfor unary expression
         printf("\t^-^^-^^-^^-^^-^^-^ Unary Plus or Minus ^-^^-^^-^^-^^-^^-^");
         printf("\n\n\tEnter expression for parsing: ");// Prompt user for input
		   gets(expression);
         unary(expression);
         break;

	  default:                 // Any Other Input apart from those in the menu
         printf("Incorect Entry. Press any Key to return to menu");
         break;
      }

	} while(choice != '0');   //Loop Menu					

}//end of main

[TJRAK]

Here's the rest of it

bool isoperator(char c)
{
 for(int a = 0; oper[a]!='\0'; a++) //check if value is an isoperator
 {
	 
	if(c == oper[a])
		return true;		//return true if isoperator
 }
 return false;				// return false otherwise
}

//=============================================================================

void postfix (char exp[])       // Function used to evaluate Postfix expression
{
	int num1, num2, value;
	int a;
	top t = NULL;

	for(int i = 0 ; i < strlen(exp); i++)
	{
		if(isspace(exp[i])) continue;  //Ignore white space

		if(isdigit(exp[i]))
			push(&t, exp[i]- '0');
		else
		{
			pop(&t,&num2);
			pop(&t,&num1);
			value = calculate(num1, exp[i], num2);
			push (&t, value);  //push result of calculation to the stack

		}

	}//ends for loop

	pop(&t, &a);
   printf("\n\tValid Notation\n");
	printf("\n\tResult: %d\n", a);
	free(t);
   getch();
	
}//ends function

//=============================================================================

void infix (char exp[])       // Function used to evaluate Infix expression
{
           // Declaration of variable
  char store[14];
  int a = 0, b = 0,x;
  int num1, num2, value;
  top t = NULL;

  for(int i = 0 ; i < strlen(exp); i++)
	{

     if (strlen(exp)>3)
     	if(exp[i]=='*' || exp[i]=='/')
      	if(isoperator(exp[i+2]) || isoperator(exp[i-2]))
         if(exp[i]=='*' && (exp[i+2]!='*' && exp[i-2]!='*'))
         {
           printf("\n\tERROR!!\n\tCheck expression");
           getch();
           return;
         }

	  if(isspace(exp[i])) continue;   // Ignore white space in expression

	  if(isdigit(exp[i]))            //If value is a digit, push to stack
	  {
			b++;
		  push(&t, exp[i]- '0');
	  }

	  else if(exp[i] == '(')	b--; //Keep track of open brackets

	  else if (isoperator(exp[i]))  //if value is operator, store in array stack
	  {
		  store[a] = exp[i];
		  a++;
	  }

	  else if (exp[i] == ')')  //Keep track of close brackets
	  {                        //Give priority to '*' and '/' following clsing
     								   //Brackets
		  if(exp[i+1] != '*' || exp[i+1] != '/')
			  b++;

	  }
	   if(b == 2)   // Do calculation for every 2 operands and an operator
	  {
		  a--;
		  pop(&t,&num2);		      
		  pop(&t,&num1);
		  value = calculate(num1, store[a], num2);		  
		  push (&t, value); //push result of calculation to the stack
		  b = 1;

	  }	  

  }//ends for loop

   pop(&t, &x);
  	if(isempty(t))
   {
      printf("\n\tValid Notation\n");
      printf("\n\tResult is: %d\n", x);
   }
   else
   	printf("\n\tERROR!!\n\tCheck expression");

	free(t);
   getch();

}//ends function

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

                        // Function used to determine type of expression.
                        // That is, if it is in Infix, Prefix or Postfix form
void determine(char *expression)
{
							  //Declaration of variables
	int optr = 0, oprd = 0, sum;
							  //loop through expression to check validity of input
	for(int i =0; expression[i]!='\0'; i++)
	{
							  //Ignore white space and brackets in expression
		if(isspace(expression[i]) || expression[i] =='(' || expression[i] ==')')
      		continue;
                       //keep track of number of isoperators
		if (isoperator(expression[i]))	optr++;

		                //keep track of number of operands
		else if (isdigit(expression[i]))	oprd++;

                     //prompt user if invalid symbol is entered in expression
		else if (!isoperator(expression[i]) && !isdigit(expression[i]) )
		{

			printf("\n\t\tERROR!!\n");
			printf("\t\t%s is not a valid expression\n", expression);
         getch();
         return;
		}

	}//ends for loop

	sum = (optr*-1) + (oprd*1);

   	// check to see if number of operands correspond to number of operators
	if(sum == 1)
	{
	 if(isoperator(expression[0])) // If first term in expression is an operator
      {                             // call the prefix function
         printf("\n\n\t Prefix Notation\n");
		  	prefix(expression);
      }
                                   // If first and second term in expression is
                                   // an operand and an operator repectively
      									  // call the Infix function
  	else if (isdigit(expression[0]) && isoperator(expression[1])||
             expression[0] == '(')
      {
      	printf("\n\n\t Infix Notation\n");
		  	infix(expression);
      }
                                  // If first and second term in expression is
                                   // an operand call the postfix function
	  	else if (isdigit(expression[0]) && isdigit(expression[1]))
      {
      	printf("\n\n\t Postfix Notation\n");
			postfix(expression);
      }
	}
	else
   {           //error message for missing operator or operand
	 printf("\n\t\tERROR!\n");
    printf("\t\tMissing operator or operand in the expression %s\n", expression);
     getch();
   }

}

//#############################################################################

void associate()
{
	char exp[50];
	char *tokenptr;

	printf("\n\n\tEnter expression for parsing: "); // Prompt user for input
	gets(exp);


	tokenptr = strtok(exp, ",");   //Tokenize each expresion seperated by ','
	while (tokenptr!=NULL) 
	{
 		determine(tokenptr);       //Determine the form of each tokenized string
 		tokenptr = strtok(NULL, ","); 	
 	} //end while loop

}

//[][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]

void unary(char *exp) // Function to evaluate Infix notation
{
	char temp[3] = {'0'};

    if (strlen(exp)>2) //Check to see if expression contains more than 2 terms
    {
      printf("Not a Unary Expresion");
      getch();
      return;
    }

    for(int i = 0; i < strlen(exp); i++) //Add a zero infront of expression
    	temp[i+1] = exp[i];

    printf("\n\tUnary Notation\n");
    infix(temp);


}

//******************************************************************************

void prefix (char *exp)      // Function to evaluate prefix notation
{
     // Declaration of variable
  char store[14];
  int a = 0, b = 0, c=0,x;
  int num1, num2, value;
  top t = NULL;

  for(int i = 0 ; i < strlen(exp); i++)
	{

	  if(isspace(exp[i])) continue;   // Ignore white space in expression

	  if(isdigit(exp[i]))            //If value is a digit, push to stack
	  {
			b++;
		  push(&t, exp[i]- '0');
	  }


	  else if (isoperator(exp[i]))  //if value is operator, store in array stack
	  {
		  store[a] = exp[i];
		  a++;
	  }

     if (b == 2 && isoperator(exp[i-1]))
     {
        c++;
        b = 1;
     }

	 if(b == 2)   // Do calculation for every operator followed by 2 operands
	 	 {
		  a--;
		  pop(&t,&num2);
		  pop(&t,&num1);
		  value = calculate(num1, store[a], num2);
		  push (&t, value); //push result of calculation to the stack
        if (c == 1)
        	{
            a--;    //Use in case where operator occur mid way in the grammar
            pop(&t,&num2);
		  		pop(&t,&num1);
		  		value = calculate(num1, store[a], num2);
		  		push (&t, value); //push result of calculation to the stack
         	c=0;
         }
        else
        	b = 1;
	  	}

  }//ends for loop

   pop(&t, &x);
  	if(isempty(t))
   {
      printf("\n\tValid Notation\n");
      printf("\n\tResult is: %d\n", x);
   }
   else
   	printf("\n\tERROR!!\n\tCheck expression");

	free(t);
   getch();
}