Nummerischen Ausdruck auflösen

[paule22]

Hallo programmers,

ich habe hier ein kleines Problem:

Wie kann ich den unten stehenden Code so erweitern, dass nummerische Ausdrücke wie dieser ausgewertet werden können:

1. Ausdruck: 200-50/2*3;

2. Ausdruck: 200-50/(2+3);

zum Code:

"token_value" ist eine INTeger Variable die aus einer Datei gephrast wird, lex() ist dafür zuständig.

hier der Code:

---------------------

int ptr__value = 0;

int handle_expr(void)

{

char buffer[100];

int lr = LR_PLUS;

int code;

for (; {

code = lex();

switch (code)

{

case '-':

{

lr = LR_MINUS;

}

break;

case NUMBER:

{

switch (lr)

{

case LR_PLUS: ptr__value += token_value; break;

case LR_MINUS: ptr__value -= token_value; break;

case LR_MUL: ptr__value *= token_value; break;

case LR_DIV: ptr__value /= token_value; break;

}

code = lex();

switch (code)

{

case ENDFILE:

{

return fatal("Ausdruck nicht korrekt beendet.\nDateiende erreicht.");

}

break;

case ';':

{

goto ende;

}

break;

case '-': lr = LR_MINUS; break;

case '+': lr = LR_PLUS; break;

case '*': lr = LR_MUL; break;

case '/': lr = LR_DIV; break;

default:

{

return fatal("Kein gÂltiger nummerischer Operator.");

}

break;

}

}

break;

case ';':

{ ende:

AnsiString ptr_str;

ptr_str = "Der Wert betr„gt: ";

ptr_str += ptr__value;

ShowMessage(ptr_str);

ptr__value = 0;

n = 0;

return RET_OK;

}

break;

default: return fatal("Zeile nicht korrekt abgeschlossen"); break;

}

}

}

--------

und hier der Code zu lex():

------------

int skip_white_space(void)

{

char buffer[200];

register int c;

register int inside;

c = fgetc(input_file);

for (; {

int cplus_comment;

switch ©

{

case '/':

c = fgetc(input_file);

if (c >= '0' && c <= '9' || c == ' ' || c == '\n') {

ungetc(c,input_file);

return '/';

} else

if (c != '*' && c != '/') {

sprintf(buffer,"unerwartetes Zeichen `/%c' gefunden",c);

return fatal(buffer);

}

cplus_comment = (c == '/');

c = fgetc(input_file);

inside = 1;

while (inside)

{

if (!cplus_comment && c == '*')

{

while (c == '*')

c = fgetc(input_file);

if (c == '/')

{

inside = 0;

c = fgetc(input_file);

}

}

else if (c == '\n')

{

line_no++;

if (cplus_comment)

inside = 0;

c = fgetc(input_file);

}

else if (c == EOF)

return fatal("Kommentarzeile wurde nicht richtig abgeschlossen.");

else

c = fgetc(input_file);

}

break;

case '\n': line_no++;

case ' ':

case '\t':

case '\f':

c = fgetc(input_file);

break;

default:

return ©;

}

}

}

int lex(void)

{

char buffer[5];

int pos = 0;

int c;

c = skip_white_space();

if (c==RET_FAIL) return RET_FAIL;

switch ©

{

case EOF: { return (ENDFILE); }

break;

case '.': return POINT_TOKEN;

case 'A': case 'B': case 'C': case 'D': case 'E':

case 'F': case 'G': case 'H': case 'I': case 'J':

case 'K': case 'L': case 'M': case 'N': case 'O':

case 'P': case 'Q': case 'R': case 'S': case 'T':

case 'U': case 'V': case 'W': case 'X': case 'Y':

case 'Z':

case 'a': case 'b': case 'c': case 'd': case 'e':

case 'f': case 'g': case 'h': case 'i': case 'j':

case 'k': case 'l': case 'm': case 'n': case 'o':

case 'p': case 'q': case 'r': case 's': case 't':

case 'u': case 'v': case 'w': case 'x': case 'y':

case 'z':

case '_':

{

sprintf(buffer,"%c",c);

token_buffer = buffer;

while (isalnum© || c == '_')

{

if (pos) {

sprintf(buffer,"%c",c);

token_buffer += buffer;

}

c = fgetc(input_file);

pos++;

}

ungetc(c, input_file);

return (IDENTIFIER);

}

break;

case '0': case '1': case '2': case '3': case '4':

case '5': case '6': case '7': case '8': case '9':

{

token_value = 0;

while (isdigit©)

{

token_value = token_value*10 + c - '0';

c = fgetc(input_file);

}

ungetc(c, input_file);

return (NUMBER);

}

break;

case '=': { return EQUALSIGN; } break;

case '-': { return '-'; } break;

case '*': { return '*'; } break;

case '/': { return '/'; } break;

case ';': { return ';'; } break;

case '(': { return '('; } break;

case ')': { return ')'; } break;

default: { return c; }

}

return ILLEGAL;

}

------

so das wars, hoffe auf Hilfe, grosses DANKEschön schon mal im vorraus...

[Crush]

Es ist ziemlich aufwendig, diese Version zu erweitern. Einfacher wäre es einen rekursiven Ansatz zu verwenden. D.h. jede "(" springt rekursiv in die Hauptschleife und liefert das Ergebnis als Rückgabewert bei ")" zurück. Dadurch könnte man das Verschachteln mehrer Klammern problemlos realisieren. Das würde sich auch prima als C++-Lösung anbieten, weil ja Operatoren überschrieben werden können und man mit CArrays arbeiten könnte (wächst mit bei Bedarf)! Ich würde dann nämlich die Reihenfolge von Operatoren auch noch kontrollieren. Nach jeder Multiplikation oder Division einfach wieder eine rekursiv-Klammer öffnen und die +,- Operatoren erhalten eine niedrigere Priorität.

Da Dein Design dies so noch nicht erlaubt würde ich bei Klammern ein Array mit Zwischenergebnissen erzeugen und diese mit den Ergebnissen füllen, also nicht mehr mit ptr_value arbeiten sondern ein int ptr_value[100]; (initialisieren nicht vergessen, es tut´s aber auch bei jeder "(" den hochgezählten ptr auf 0 zu setzen) erzeugen und halt eine int ptr_valCounter=0; setzen, welche dann im Code überall mit ptr_value[ptr_valCounter]*=,/=,-=,+=Ergebnis; verwendet wird. "(" erhöht einfach den Counter. Kommt eine ")" wird er runtergezählt. Wie gesagt bei Punktoperatoren (Multiplikation oder Division) einfach automatisch wieder eine neue Klammer eröffnen indem man den Counter hochzählt. Das Ergebnis muß folglich am Ende nach der letzten Operation auf den 0-Counter sein.

Damit ist es aber noch immer nicht getan, weil einfach noch vor dem berechnen der Operatoren die Klammer-Ergebnisse vorliegen müssen. Das heißt bei: 200-50/(2+3); nach dem Beenden der Klammer muß bekannt sein, daß vorher eine Division stattgefunden hat. Also muß nach ")" der Operator erst abgearbeitet werden. Im Zweifelsfall das bis dahin bekannte Ergebnis und Operator auch auf ein Array ablegen. Autsch! Das wird wirklich kompliziert. Erst Counter runterzählen nachdem man das Klammer-Ergebnis im Array abgelegt hat, dann ptr_value[ptr_valCounter]/=ptr_value[ptr_valCounter+1]; Vorsicht: Eine Bereichsüberprüfung wäre ohnehin überall angebracht! Also würde die Case-Abfrage auch noch ein kleines Problem darstellen, welches anders gelöst werden muß. Da hast Du schon einiges an Arbeit vor Dir!

Also die rekursive Lösung mit Rückgabeparameter ist die eindeutig beste mit dem wenigsten Aufwand - außerdem könnteman sich Arrays sparen, weil ja alles über den Stack läuft. Dann soll einfach jeder Operator eine Funktion aufrufen, die ein letztes Ergebnis rückwärts weiterreicht. und dann ist das Operator-Problem und die unbekannten Ergebnisse nachfolgender Operatoren komplett und (relativ) einfach gelöst.

Diese Lösung verlangt halt, daß alle ptr_values und Operatoren aufs Array umgeschrieben werden. Oder das ganze einen rekursiven Ansatz erhält.

<FONT COLOR="#a62a2a" SIZE="1">[ 11. November 2001 07:48: Beitrag 3 mal editiert, zuletzt von Crush ]</font>

[paule22]

Halle Crush,

ich habe nun die Funktion optimiert, sodass sie nun den

Ausdruck width = 200+20+(((15-5)-(10*2))-5);

aber der Ausdruck bringt einen Fehler in der Berechnung:

width = 200+20+(((15-5)-2-(10*2))-5);

Vermutlich weil bei der Berechnung des Ausdrucks immer zwei paare zusammen sein müssen,

wäre dankbar für (ab)Hilfe des Problems ...

kann man den Code so nehmen? ist der rekursiv programmiert?

hier der Code für 'handle_expr()'

-----------

double stack_value[2048];

int result_stack[2048];

int ptr__value = 0;

int ptr__error = 0;

static int ptr__lr = LR_PLUS;

double handle_expr(void)

{

char buffer[100];

int lr = LR_PLUS;

int code, r3;

static int pos = 0;

static int klammer = 0;

static int num = 0;

static int n = 0;

double result;

for (; {

code = lex();

switch (code)

{

case '(':

{

klammer++;

ptr__value = 0;

double result = handle_expr();

stack_value[n] = result;

#ifdef DEBUG

AnsiString str;

str = "result = ";

str += IntToStr(ptr__value);

str += " / ";

if (n-1 < 0) str += FloatToStr((int)stack_value[n]);

else str += FloatToStr((int)stack_value[n-1]);

ShowMessage(str);

#endif

}

break;

case ')':

{

klammer--;

return stack_value[n];

}

break;

case '-':

{

if (!pos) { ptr__lr = LR_MINUS; continue; }

else {

result_stack[n] = ptr__lr;

stack_value [n] = token_value;

ptr__lr = LR_MINUS;

num = 0;

continue;

}

}

break;

case '+':

{

if (!pos) {

ptr__error++;

ptr__value = 0;

pos = 0;

fatal("[+] nur Minus-Operator hier erlaubt.");

return 0;

}

else {

result_stack[n] = ptr__lr;

stack_value [n] = token_value;

ptr__lr = LR_PLUS;

num = 0;

continue;

}

}

break;

case '/':

{

if (!pos) {

ptr__error++;

ptr__value = 0;

pos = 0;

fatal("[/] nur Minus-Operator hier erlaubt.");

return 0;

}

else {

result_stack[n] = ptr__lr;

stack_value [n] = token_value;

ptr__lr = LR_DIV;

num = 0;

continue;

}

}

break;

case '*':

{

if (!pos) {

ptr__error++;

ptr__value = 0;

pos = 0;

fatal("[*] nur Minus-Operator hier erlaubt.");

return 0;

}

else {

result_stack[n] = ptr__lr;

stack_value [n] = token_value;

ptr__lr = LR_MUL;

num = 0;

continue;

}

}

break;

case NUMBER:

{

switch (ptr__lr)

{

case LR_PLUS : stack_value[n] += (double) token_value; break;

case LR_MINUS: stack_value[n] -= (double) token_value; break;

case LR_MUL : stack_value[n] *= (double) token_value; break;

case LR_DIV : stack_value[n] /= (double) token_value; break;

}

result_stack[n] = ptr__lr;

stack_value[n] = token_value;

pos++;

num++;

n++;

if (klammer) {

ShowMessage("in klammer");

}

continue;

}

break;

case ';':

{

result = 0;

int c;

// #ifdef DEBUG

AnsiString str;

for (c = 0; c < 20; c++) {

str += "results = ";

str += FloatToStr(stack_value[c]);

str += " / ";

str += IntToStr(result_stack[c]);

str += "\n";

}

ShowMessage(str);

// #endif

// --------------------------------------

// Handles/calculates the stacked values.

// each math operation appear in a

// stacked value ...

// --------------------------------------

for (c = 0; c < EXPR_MAX; c++)

{

// ---------

// +expr ...

// ---------

if (result_stack[c] == LR_PLUS)

{

int r1 = stack_value[c];

int r2 = stack_value[c+1];

if (result_stack[c+1] == LR_MUL) {

int r3 = r1*r2;

result += r3;

c++;

}

else if (result_stack[c+1] == LR_DIV)

{

// -----------------------------

// Division durch 0 abfangen ...

// -----------------------------

if (r2 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else

r3 = r1/r2;

result += r3;

c++;

}

else if (result_stack[c+1] == LR_MINUS) {

int r3 = r1-r2;

result += r3;

c++;

}

else

{

int r3 = r1+r2;

result += r3;

c++;

}

}

// ---------

// -expr ...

// ---------

else if (result_stack[c] == LR_MINUS)

{

int r1 = stack_value[c];

int r2 = stack_value[c+1];

if (result_stack[c+1] == LR_MUL) {

int r3 = r1*r2;

result -= r3;

c++;

}

else if (result_stack[c+1] == LR_DIV) {

// -----------------------------

// Division durch 0 abfangen ...

// -----------------------------

if (r2 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else

r3 = r1/r2;

result -= r3;

c++;

}

else if (result_stack[c+1] == LR_MINUS) {

int r3 = r1-r2;

result -= r3;

c++;

}

else

{

result -= (r1+r2);

c++;

}

}

// ---------

// *expr ...

// ---------

else if (result_stack[c] == LR_MUL)

{

int r1 = stack_value[c];

int r2 = stack_value[c+1];

if (result_stack[c+1] == LR_MUL) {

int r3 = r1*r2;

result *= r3;

c++;

}

else if (result_stack[c+1] == LR_DIV) {

// -----------------------------

// Division durch 0 abfangen ...

// -----------------------------

if (r2 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else

r3 = r1/r2;

result *= r3;

c++;

}

else if (result_stack[c+1] == LR_MINUS) {

int r3 = r1-r2;

result *= r3;

c++;

}

else

{

result *= (r1+r2);

c++;

}

}

// ---------

// /expr ...

// ---------

else if (result_stack[c] == LR_DIV)

{

int r1 = stack_value[c];

int r2 = stack_value[c+1];

if (result_stack[c+1] == LR_MUL) {

int r3 = r1*r2;

if (r3 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

result /= r3;

c++;

}

else if (result_stack[c+1] == LR_DIV) {

// -----------------------------

// Division durch 0 abfangen ...

// -----------------------------

if (r2 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else

r3 = r1/r2;

if (r3 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else

{

result /= r3;

c++;

}

}

else if (result_stack[c+1] == LR_MINUS) {

int r3 = r1-r2;

if (r3 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else

{

result /= r3;

c++;

}

}

else

{

// -----------------------------

// Division durch 0 abfangen ...

// -----------------------------

if (r2 == 0)

r3 = 0; else

r3 = r1/r2;

if (r3 == 0)

{

ptr__error++;

fatal("Division durch Null nicht erlaubt.");

return 0;

}

else {

result /= r3;

c++;

}

}

}

}

// ------------------------------

// at end, clear the value stack-

// set all value to null...

// ------------------------------

for (c = 0; c < EXPR_MAX; c++) stack_value[c] = 0;

klammer = 0;

n = 0;

num = 0;

pos = 0;

ptr__value = 0;

ptr__error = 0;

ptr__lr = LR_PLUS;

return result;

}

break;

default:

{

error_expr:

ptr__error++;

pos = 0;

num = 0;

ptr__value = 0;

fatal("Nummerischer Ausdruck erforderlich.\nVermutlich Zeile nicht korrekt abgeschlossen.");

return 0;

}

break;

}

}

}

-----

vielen Dank im vorraus und für deine Tips !!!

[Crush]

Sieht eigentlich ganz gut aus. Das Verwenden vom Stack ist schon rekursiv, also ok. Ich sehe keinen direkten Fehler, der mir ins Auge sticht, aber vermutlich liegt hier irgendwo der Hund begraben:

case '-':

{

if (!pos) { ptr__lr = LR_MINUS; continue; }

else {

result_stack[n] = ptr__lr;

stack_value [n] = token_value;

ptr__lr = LR_MINUS;

num = 0;

continue;

}

}

break;

->Es fehlt mir einmal der ptr_value, der sonst überall gesetzt wird. Warum soll der bei "-" nicht verwendet werden? Sollte der nicht auch eigentlich ein Wert auf dem Stack sein? Ich würde grundsätzlich nur mit dem Result-Stack arbeiten: Auch das Endergebnis sollte da am besten drinstehen. Halt auf den ersten Eintrag.

case '+':

{

if (!pos) {

ptr__error++;

ptr__value = 0;

pos = 0;

fatal("[+] nur Minus-Operator hier erlaubt.");

-> Wieso nur Minus und nicht plus??? Falls die erste Zahl negativ ist, oder?

return 0;

}

else {

result_stack[n] = ptr__lr;

stack_value [n] = token_value;

ptr__lr = LR_PLUS;

num = 0;

continue;

}

}

break;

->width = 200+20+(((15-5)-2-(10*2))-5);

Warum wird der (15-5) nicht als erstes Wertpaar verwendet? Arbeitet das -2 nicht mit dem stack_value[n] richtig zusammen? Es könnte sein, daß die Klammern vor (15-5) den ptr_lr auf - und + falsch behandeln. Eine ")" legt ja nach dem ersten Beispiel den Wert korrekt auf den Rückgabestack, welcher mit dem einzelnen "-" zwischen den Beiden Klammern auch richtig funktioniert. Es wird wohl nur beim direkten - oder + nicht richtig auf den Result-Stack verrechnet und abgelegt (eigentlich sollte das -2 direkt auf dem Wert des Result-Stacks zugreifen ohne diesen runter- oder hochzuzählen!!! Hier mußt Du einfach mal im Debugger durchsteppen um zu sehen, wovon die "-2" abgezogen wird. Vermutlich ist hier nur der Value_ptr nicht richtig gesetzt oder wird einmal zuviel oder zuwenig hoch-, bzw. runtergezählt.

Der Debugger wird hier wohl den Schlüssel zur Rätselslösung geben. Ausprobieren! Vielleicht halt mit was einfacherem wie width = 10+((15-5)-2);

Ansonsten muß ich sagen ist diese Version im Gegensatz zur ersten ein echter Fortschritt und nah dran am Optimum!