/*

I) Regeln

{z}
--- wobei z eine Ziffer ist    
z
...

{T1 , T2}
---------
(T1+T2)

{T1 , T2}
---------
(T1-T2)


II)
Zeichenketten der Länge 2,3, oder 4 können keine Terme sein,
da es keine Kandidaten (Kandidatenmenge ist leere Menge) gibt.
Man muß also nur Zeichenketten der Länge 1 und größer gleich 5 
betrachten.

*/

#include "stdafx.h"

bool istZiffer(char z);
int e(char string[], int begin, int end);
int N(char string[], int begin, int end);

int main(){
	int erg;
	int wert;
	char string1[] = "((0+1)+((2+3)-4))";
	erg=e(string1,0,16);
	wert=N(string1,0,16);

	if(erg==1)
		printf("Zeichenkette %s ist ein Term und hat den Wert %d\n\n",string1,wert);
	else{
		printf("Zeichenkette %s ist kein Term und hat den Wert %d\n\n",string1,wert);
	}

	char string2[] = "(3-7)";
	erg=e(string2,0,4);
	wert=N(string2,0,4);

	if(erg==1)
		printf("Zeichenkette %s ist ein Term und hat den Wert %d\n\n",string2,wert);
	else{
		printf("Zeichenkette %s ist kein Term und hat den Wert %d\n\n",string2,wert);
	}
	

	char string3[] = "(0+1)+((2+3)-4))";
	erg=e(string3,0,15);
	wert=N(string3,0,15);

	if(erg==1)
		printf("Zeichenkette %s ist ein Term und hat den Wert %d\n\n",string3,wert);
	else{
		printf("Zeichenkette %s ist kein Term und hat den Wert %d\n\n",string3,wert);
	}


	
	return 1;
}

/****************************************************************************/
/**																	       **/
/**  int e(char string[], int begin, int end)                              **/
/**																	       **/
/****************************************************************************/
/*
  Parameter:
    (i) char *string: die zu untersuchende Zeichenkette
	(i) int begin: ab diesem Index zu untersuchende Zeichenkette
	(i) int end >= begin: bis zu diesem Index zu untersuchende Zeichenkette

	
  return:
    Zeichenkette ist Term: 1
    Zeichenkette ist kein Term: 0
  
  Beschreibung:
    prüft nach, ob eine Zeichenkette ein Term ist.
	Die Regelmenge für einen Term ist oben angegeben.

  Beispiel:
    e("(2+6)",0,3) liefert 1 zurück, da (2+6) ein Term ist.
*/


int e(char string[], int begin, int end){
	int i;
	int len;
	int erg=0;

	len = end - begin + 1;

	// Zeichenkette ist eine Ziffer
	if( len==1 && istZiffer(string[begin]) ){
		erg=1;
	}
	else{  // Zerlegungen versuchen
		for(i=begin+1; i<end; i++){
			if(len<=4)
				// Zeichenkette ist kein Term
				break;
			else{
				if((string[i]=='+' || string[i]=='-')   && string[begin]=='(' && string[end]==')'){
					erg= e(string, begin+1, i-1) * e(string, i+1, end-1);
					// Um Laufzeit zu verbessern
					if(erg==1){
						break;
					}
				}
			}
		}
	}
	return erg;
}



/****************************************************************************/
/**																	       **/
/**  int N(char string[], int begin, int end)                              **/
/**																	       **/
/****************************************************************************/
/*
  Parameter:
    (i) char *string: die zu untersuchende Zeichenkette
	(i) int begin: ab diesem Index zu untersuchende Zeichenkette
	(i) int end >= begin: bis zu diesem Index zu untersuchende Zeichenkette

	
  return:
    Wert der Zeichenkette, falls diese ein Term ist
    9999: falls Zeichenkette kein Term ist (siehe Bemerkung)
  
  Beschreibung:
    Bestimmt den Wert einer Zeichenkette.

  Bemerkung:
    Eine Zeichenkette, die kein Term ist, darf eigentlich keine Zahl als Wert
	zurückliefern, sondern sollte ein Sonderzeichen wie z.B. # 
	zurückliefern. Da ein Datentyp wie int oder double dies nicht leistet,
    könnte man einen eigenen Datentyp basteln (mit Hilfe von struct).
	Oder man könnte folgenden Trick benutzen:
	double wert;
	double null=0.0;
	wert = 1.0/null;
	wert hat dann den Wert: 1.#INF000000000
*/


int N(char string[], int begin, int end){
	int i;
	int len;
	int erg;
	int wert;
	double test;
	double null=0.0;
	
	erg = e(string, begin, end);
	// Zeichenkette ist kein Term
	if(erg==0){
		wert = 9999;
	}
	// Zeichenkette ist ein Term
	else{
		len = end - begin + 1;
		
		if( len==1 && istZiffer(string[begin]) ){
			wert=string[begin]-48;
		}
		else{  // Zerlegungen versuchen
			for(i=begin+1; i<end; i++){
				if(string[i]=='+' && string[begin]=='(' && string[end]==')'){
					erg= e(string, begin+1, i-1) * e(string, i+1, end-1);
					if(erg==1){
						wert=N(string, begin+1, i-1)+N(string, i+1, end-1);
						break;
					}
				}
				if(string[i]=='-' && string[begin]=='(' && string[end]==')'){
					erg= e(string, begin+1, i-1) * e(string, i+1, end-1);
					if(erg==1){
						wert=N(string, begin+1, i-1)-N(string, i+1, end-1);
						break;
					}
				}

			}
		}
	}
	return wert;
}



/****************************************************************************/
/**																	       **/
/**  bool istZiffer(char z)                                                **/
/**																	       **/
/****************************************************************************/
/*
  Parameter:
    (i) char z: das zu untersuchende Zeichen
	
  return:
    Zeichen ist Ziffer: true
    Zeichen ist keine Ziffer: false
  
  Beschreibung:
    prüft nach, ob ein Zeichen eine Ziffer d.h: 0,1,2,3,4,5,6,7,8,9 ist.
*/


bool istZiffer(char z){
	bool erg;
	if( 48 <= (int)z && (int)z <=57)
		erg=true;
	else
		erg=false;

	return erg;
}