Mathematische Ausdrücke parsen und berechnen bzw. auswerten



  • Ich habe mich die letzten 2-3 Tage mit dem parsen von Ausdrücken befasst, einmal
    in meinem Buch C Ent-Packt wo wie oben bereits erwähnt ein Parser für mathematische
    Ausdrücke erstellt wurde und einem in dem Buch C von A-Z, wo man einfach Regular
    Expressions
    erstellt.
    Das zweite fand ich leicht verständlich (ist auch um welten leichter gewesen).
    Jedoch mit dem parsen eines mathematischen Ausdrucks hab ich ernsthafte Probleme,
    den Quelltext den ich abtippe versteh ich ja von den Aktionen her, aber wie das
    Programm jetzt im einzelnen funktioniert leider nicht, sprich ich könnte jetzt nicht
    solch einen Parser selbst schreiben.
    Würde jemand von euch vllt. so freundlich sein und sich den Quelltext mal ansehen
    und ihn mit Kommentaren übersähen oder ihn zu zerpflücken und genau zu erklären?
    Mir bringt ja das tollste Beispiel nichts, wenn ich es nicht verstehe 😞

    Das Programm besteht aus 2Dateien, einmal den Parser mit dem Namen "advanced_parser.c" und einmal "parser_test.c", welches das eigentliche Programm
    darstellt.

    Der Parser kann folgendes:
    Addition,Subtraktion,Multiplikation,Division,Modulo-Division,Exponenten,Klammern,
    unäres + und - sowie verwenden.
    Die Variablen stellen das Double-Array dar.

    Hier einmal die beiden Dateien:

    parser_test.c

    // Testprogramm für den Parser
    #include "advanced_parser.c"
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include <string.h>
    
    char *prog;
    void eval_exp (double *answer);
    
    int main (void) {
    
    	double answer;
    	char *p;
    
    	p = (char *) malloc (100);
    	if (!p) {
    		printf ("Memory Allocation failed.\n");
    		exit (1);
    	}
    
    	// Ausdruck verarbeiten bis eine leere Zeile eingegeben wird
    	do {
    		prog = p;
    		printf ("Enter Expression: ");
    		gets (prog);
    		if (!*prog) break;
    		eval_exp (&answer);
    		printf ("\nAnswer is: %.2f\n", answer);
    	} while (*p);
    
    	return 0;
    
    }
    

    Und hier der eigentliche Parser:

    advanced_parser.c

    /* Dieses Modul enthält den Parser für rekursiven Abstieg, der Variablen erkennen kann */
    
    #include <stdlib.h>
    #include <ctype.h>
    #include <stdio.h>
    #include <string.h>
    
    #define DELIMITER 1
    #define VARIABLE 2
    #define NUMBER 3
    
    extern char *prog; // Zeigt auf den zu analysierenden Ausdruck
    char token[80];
    char tok_type;
    
    double vars[26] = {0.0};
    
    void eval_exp  (double *answer);
    void eval_exp1 (double *result);
    void eval_exp2 (double *answer);
    void eval_exp3 (double *answer);
    void eval_exp4 (double *answer);
    void eval_exp5 (double *answer);
    void eval_exp6 (double *answer);
    void atom (double *answer);
    void get_token (void);
    void putback (void);
    void serror (int error);
    double find_var (char *s);
    int isdelim (char c);
    
    // Einstiegspunkt für den Parser
    void eval_exp (double *answer) {
    
    	get_token ();
    	if (!*token) {
    		serror (2);
    		return;
    	}
    	eval_exp1 (answer);
    	if (!*token) serror (0); // letztes Token muss Null sein
    
    }
    
    // Zuweisung verarbeiten
    void eval_exp1 (double *answer) {
    
    	int slot;
    	char ttok_type;
    	char temp_token[80];
    
    	if (tok_type == VARIABLE) {
    		// altes Token speichern
    		strcpy (temp_token, token);
    		ttok_type = tok_type;
    		// Index der Variablen berechnen
    		slot = toupper (*token) - 'A';
    
    		get_token ();
    		if (*token != '=') {
    			putback (); // aktuelles Token zurückliefern
    			// altes Token wiederherstellen - keine Zuweisung
    			strcpy (token, temp_token);
    			tok_type = ttok_type;
    		}
    		else {
    			get_token (); // nächsten Teil des Ausdrucks holen
    			eval_exp2 (answer);
    			vars[slot] = *answer;
    			return;
    		}
    	}
    	eval_exp2 (answer);
    
    }
    
    // zwei Terme addieren und subtrahieren
    void eval_exp2 (double *answer) {
    
    	register char op;
    	double temp;
    
    	eval_exp3 (answer);
    	while ((op = *token) == '+' || op == '-') {
    		get_token ();
    		eval_exp3 (&temp);
    		switch (op) {
    			case '-':	*answer = *answer - temp;	break;
    			case '+':	*answer = *answer + temp;	break;
    		}
    	}
    
    }
    
    // zwei Faktoren multiplizieren oder dividieren
    void eval_exp3 (double *answer) {
    
    	register char op;
    	double temp;
    
    	eval_exp4 (answer);
    	while ((op = *token) == '*' || op == '/' || op == '%') {
    		get_token ();
    		eval_exp4 (&temp);
    		switch (op) {
    			case '*':	*answer = *answer * temp; 	break;
    			case '/':	*answer = *answer / temp;	break;
    			case '%':	*answer = (int) *answer % (int) temp;	break;
    		}
    	}
    
    }
    
    // Exponenten verarbeiten
    void eval_exp4 (double *answer) {
    
    	double temp,ex;
    	register int t;
    
    	eval_exp5 (answer);
    
    	if (*token == '^') {
    		get_token ();
    		eval_exp4 (&temp);
    		ex = *answer;
    		if (temp == 0.0) {
    			*answer = 1.0;
    			return;
    		}
    		for (t = temp-1; t >> 0; t--) *answer = (*answer) * (double) ex;
    	}
    
    }
    
    // Unäres + oder - auswerten
    void eval_exp5 (double *answer) {
    
    	register char op;
    
    	op = 0;
    	if ((tok_type == DELIMITER) && *token == '+' || *token == '-') {
    		op = *token;
    		get_token;
    	}
    	eval_exp6 (answer);
    	if (op == '-') *answer = -(*answer);
    
    }
    
    // Eingeklammerten Ausdruck verarbeiten
    void eval_exp6 (double *answer) {
    
    	if (*token == '(') {
    		get_token ();
    		eval_exp2 (answer);
    		if (*token != ')') serror (1);
    		get_token ();
    	}
    	else atom (answer);
    
    }
    
    // Wert einer Ziffer oder Variablen holen
    void atom (double *answer) {
    
    	switch (tok_type) {
    		case VARIABLE:
    					*answer = find_var (token);
    					get_token ();
    					return;
    		case NUMBER:
    					*answer = atof (token);
    					get_token ();
    					return;
    		default:
    				serror (0);
    	}
    
    }
    
    // Token dem Eingab´ngsstrom zurückgeben
    void putback (void) {
    
    	char *t;
    
    	t = token;
    	for (; *t; t++) prog--;
    
    }
    
    // Syntaxfehler anzeigen
    void serror (int error) {
    
    	static char *e[] = {
    					"Syntax Error",
    					"Unbalanced Parantheses",
    					"No Expression Present",
    					"Division by Zero" };
    	printf ("%s\n", e[error]);
    
    }
    
    // Nächstes Token zurückliefern
    void get_token (void) {
    
    	register char *temp;
    
    	tok_type = 0;
    	temp = token;
    	*temp = ' ';
    
    	if (!*prog) return; // am Ende des Ausdrucks
    
    	while (isspace (*prog)) prog++; // Whitespaces überspringen
    
    	if (strchr ("+-*/%^=()", *prog)) {
    		tok_type = DELIMITER;
    		// weiter zum nächsten Zeichen
    		*temp++ = *prog++;
    	}
    	else if (isalpha (*prog)) {
    		while (!isdelim (*prog)) *temp++ = *prog++;
    		tok_type = VARIABLE;
    	}
    	else if (isdigit (*prog)) {
    		while (!isdelim (*prog)) *temp++ = *prog++;
    		tok_type = NUMBER;
    	}
    
    	*temp = '\0';
    
    }
    
    // Falls c ein Delimiter ist, true zurückgeben
    int isdelim (char c) {
    
    	if (strchr ("+-/*%^=()", c) || c == 9 || c == '\r' || c == 0) return 1;
    	return 0;
    
    }
    
    // Wert einer Variablen zurückliefern
    double find_var (char *s) {
    
    	if (!isalpha (*s)) {
    		serror (1);
    		return 0.0;
    	}
    
    	return vars[toupper (*token) - 'A'];
    
    }
    

    Wäre wirklich spitze wenn das jemand tun könnte 🙂
    Ich weiß, dass man da mal eine Weile sitzt und wäre demjenigen daher ewig dankbar 😃





  • Danke, das sieht schonmal sehr nützlich aus, werd mir das mal genau anschauen 🙂

    Edit:
    Dein geschriebenes erklärt das Vorhaben prinzipiell, so auch wie im Buch, hilft
    mir daher nicht unbedingt 😞



  • Falls Du mir Deine e-Adresse verrätst, kriegst Du meinen kommentierten Quellcode.



  • exterminans <at> web.de

    Vielen Dank 🙂

    Habe mir den Parser im Buch und das Kapitel nochmal gründlich angeschaut und ich
    denke ich bin dem Verständnis etwas Näher gekommen. Aber dein Parser würde mich
    doch interressieren, da er total anderst aufgebaut ist so wie ich es aus dem
    Code-Snippet ersehen kann.


Log in to reply