suppose this:

string a;

int b,c;

b=7;

c=5;

a="b+c"

where b=7 and c=5

I need a function like Eval in order to convert the string "b+c" into 7+5 where the result is 12

5 posts • Page **1** of **1**

What you need is a parser I think. This is not very easy. I have made some tries, but it never worked very good. One method could be:

string str;

str = "3*(4+3*(2-1))";

Ok. I would handle it like that: I would search for the most inner brackets, then, I would calculate the term (2-1), reinsert it, then get the outer bracket (4+3*1) calculate it, reinsert it and calculate the remaining term...

To calculate it, you will have to find two numbers and calculate it with the operator between them. You will neeed a lot of string operations. Or you read the whole term into the memory what would be faster, but would need more work...

Or you search for a c-algorithm. I don't know where to find one. If you are lucky, you could tell me, because I am interested in this, too...

Eike

http://www.strange-phenomenom.de/newp/pocketc.htm

string str;

str = "3*(4+3*(2-1))";

Ok. I would handle it like that: I would search for the most inner brackets, then, I would calculate the term (2-1), reinsert it, then get the outer bracket (4+3*1) calculate it, reinsert it and calculate the remaining term...

To calculate it, you will have to find two numbers and calculate it with the operator between them. You will neeed a lot of string operations. Or you read the whole term into the memory what would be faster, but would need more work...

Or you search for a c-algorithm. I don't know where to find one. If you are lucky, you could tell me, because I am interested in this, too...

Eike

http://www.strange-phenomenom.de/newp/pocketc.htm

- darwin
**Posts:**71**Joined:**Tue Dec 05, 2000 12:04 pm**Location:**Germany

You just need a simple state machine with a state table that describes the grammar for the expressions that you want to parse.

Each state transition can be accompanied by an action routine, those that represent the completion of a token result in the insertion of the token into a tree.

Once you've finished the expression and have the tree you just walk it in order of operator precedence evaluating the nodes and replacing them with their result. When you've finished you have a single node containing the result of the expression.

The difficulty that you have in your example is that the PocketC variables and the variables inside your expressions are in a different scope. The PocketC variable names don't even exist at run time.

If you need to include variables in your expressions as well as constants, then you need to extend the parser to include a symbol table for variables that is preserved across calls to the eval function. You can then support an assignment operator in your state machine.

To make this work you need your tree to store both "lvalue" and "rvalue" values for nodes. The lvalue is the address in your symbol table where the variable lives, the rvalue is its actual value.

Once you have the symbol table and state table then you can simply call:

Eval("b=7") ;

Eval("c=5") ;

a=Eval("b+c") ;

Eval("a=" + a) ;

You could probably build the code and tables for this using yacc, then convert the code from C to PocketC.

Guy

Each state transition can be accompanied by an action routine, those that represent the completion of a token result in the insertion of the token into a tree.

Once you've finished the expression and have the tree you just walk it in order of operator precedence evaluating the nodes and replacing them with their result. When you've finished you have a single node containing the result of the expression.

The difficulty that you have in your example is that the PocketC variables and the variables inside your expressions are in a different scope. The PocketC variable names don't even exist at run time.

If you need to include variables in your expressions as well as constants, then you need to extend the parser to include a symbol table for variables that is preserved across calls to the eval function. You can then support an assignment operator in your state machine.

To make this work you need your tree to store both "lvalue" and "rvalue" values for nodes. The lvalue is the address in your symbol table where the variable lives, the rvalue is its actual value.

Once you have the symbol table and state table then you can simply call:

Eval("b=7") ;

Eval("c=5") ;

a=Eval("b+c") ;

Eval("a=" + a) ;

You could probably build the code and tables for this using yacc, then convert the code from C to PocketC.

Guy

Guy

[url]mailto:pcform@pcform.net[/url]

http://www.pcform.net

PocketC CE API interface: http://www.networkdynamics.net/PCForm.html#library

PCForm and CE API forum: http://www.networkdynamics.net/forum

[url]mailto:pcform@pcform.net[/url]

http://www.pcform.net

PocketC CE API interface: http://www.networkdynamics.net/PCForm.html#library

PCForm and CE API forum: http://www.networkdynamics.net/forum

- guy
**Posts:**879**Joined:**Thu Dec 07, 2000 8:58 am**Location:**United Kingdom

Somewhere I've got a Numerical Integrator I wrote for class. It's capable of taking single-variable input equations in algebraic (or rpn), converting to rpn, and stack-processing them. I don't see why it wouldn't for for multi-variables. You'd have to convert it to PocketC Is it possible to attach files here?

Chris

Chris

- Chris Kelly
**Posts:**5**Joined:**Fri Feb 09, 2001 11:25 am**Location:**USA

Okay, I'm gonna try to include the code...

Oh, I forgot, it was an MPI project. Just strip all that crap out...

Chris

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

*

* Program: num_int.c

* Name: Chris Kelly - kelly@cs.utk.edu

* Date: 11/14/99

* Class: CS140 - 31788 - Wed. 5:45-8:35 - Lab 8

* Description: This program uses MPI to parallel-process

* a large problem. I have no idea what problem

* at this time, probably computing pi or

* some such. Okay, I've decided what to do. I'm

* gonna set it up to process a segment of a

* given function, expressed in RPN. Yep, good

* ol' numerical integration. If time

* allows, I'll use the process in ch. 3.3 to

* translate algebraic to RPN, making it slicker.

*

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

#include <stdio.h>

#include <mpi.h>

#include <string.h>

#define TRUE 1

#define FALSE 0

float evaluate (char *, float);

void alg(char *);

main(int argc,char *argv[]) {

int rank,size,tag=0,retval,i,source;

char expr[40],mode[4];

MPI_Status sts;

float area,seg,myrange,eachseg,mystart,mystop,f,limits[3];

float temp;

retval = MPI_Init(&argc,&argv);

retval = MPI_Comm_size(MPI_COMM_WORLD,&size);

retval = MPI_Comm_rank(MPI_COMM_WORLD,&rank);

/* find out who we are */

if (rank == 0) { /* we're boss, divvy up the work */

printf("Need Help? (y/n) ");

scanf("%s",expr);

if (expr[0] == 'y') {

printf("This program calculates the area under a \n");

printf("expression, between given limits, by adding\n");

printf("up the requested number of calculated rect-\n");

printf("angles. Just like in the calculus book, the\n");

printf("expression must be a FUNCTION, and it must\n");

printf("be CONTINUOUS between the given limits.\n");

printf("I only support +-/* , x and SINGLE digits.\n");

printf("The expression is entered in RPN or Algebraic,\n");

printf("Algebraic supports parenthesis, but the RPN\n");

printf("is more stable -\n");

printf("e.g. RPN 2x*x*3x*+2+\n\n");

printf("e.g. Alg 2*x*x+3*x+2\n\n");

printf("Note - unary minus not supported.\n\n");

}

printf("Will expression be in (r)pn or (a)lgebraic :");

scanf("%s",mode);

printf("Enter expression (NO SPACES) :");

scanf("%s",expr);

printf("Enter beginning of interval :");

scanf("%f",&limits[0]);

printf("Enter end of interval :");

scanf("%f",&temp);

limits[1]=(double) temp;

printf("Enter # of slices per processor :");

scanf("%f",&limits[2]);

if (mode[0] == 'a')

alg(expr);

for (i=1;i<size;i++) {

MPI_Send(expr,40,MPI_CHAR,i,tag,MPI_COMM_WORLD);

MPI_Send(limits,3,MPI_FLOAT,i,tag,MPI_COMM_WORLD);

}

area = 0.;

for (i = 1;i<size;i++) {

MPI_Recv(&seg,1,MPI_FLOAT,i,tag,MPI_COMM_WORLD,&sts);

area = area + seg;

}

printf("The area under the function is %f\n",area);

}

else { /* slave, accept work */

MPI_Recv(expr,40,MPI_CHAR,0,tag,MPI_COMM_WORLD,&sts);

MPI_Recv(limits,3,MPI_FLOAT,0,tag,MPI_COMM_WORLD,&sts);

myrange = limits[1] - limits[0];

eachseg = myrange/(size-1);

mystart = limits[0] + (rank-1)*eachseg;

mystop = mystart + eachseg;

area = 0.0;

for (f=mystart;f<mystop;f=f+eachseg/limits[2]) {

area = area + eachseg/limits[2] * evaluate(expr,f);

}

MPI_Send(&area,1,MPI_FLOAT,0,tag,MPI_COMM_WORLD);

}

retval = MPI_Finalize();

}

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

* evaluate - figure out value of given

* RPN function at given point

* WARNING - this sucker does NO error

* checking! expression MUST be right!

* code is mine, but concept is from

* Weiss text, page 72.

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

float evaluate (char *expr, float x) {

float stack[30];

int ptr=0,i;

for (i = 0; i<(strlen(expr));i++) {

if (expr[i] == ' ') {

/* ignore for now */

}

if (expr[i] == 'x') {

/* move current val onto stack */

stack[ptr] = x;

ptr++;

}

if ((expr[i] >= '0') && (expr[i] <='9')) {

/* is digit, stack it as value */

stack[ptr] = (int)expr[i] - 48;

ptr++;

}

if (expr[i] == '+') {

/* is add, add two vals on stack */

stack[ptr-2]=stack[ptr-2]+stack[ptr-1];

ptr = ptr -1;

}

if (expr[i] == '-') {

/* is minus, subtract two vals on stack */

stack[ptr-2]=stack[ptr-2]-stack[ptr-1];

ptr = ptr -1;

}

if (expr[i] == '*') {

/* is asterisk, multiply two vals on stack */

stack[ptr-2]=stack[ptr-2]*stack[ptr-1];

ptr = ptr -1;

}

if (expr[i] == '/') {

/* is slash, divide two vals on stack */

stack[ptr-2]=stack[ptr-2]/stack[ptr-1];

ptr = ptr -1;

}

}

if (ptr != 1) {

printf("Evaluate - stack failure!\n");

exit();

}

return(stack[0]);

}

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

* alg - infix->postfix converter -

* this damn routine was harder than the MPI!

* the code is mine, but the process comes

* from Weiss pg. 74.

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

void alg(char *expr) {

char expr2[40];

char stack[20];

int i,sptr = 0,eptr = 0,val,done = 0,sval;

for (i = 0; i<(strlen(expr));i++) {

val = 0;

if (expr[i] == ' ') {

/* ignore for now */

}

if (expr[i] == 'x') {

expr2[eptr] = 'x';

eptr++;

}

if ((expr[i] >= '0') && (expr[i] <='9')) {

expr2[eptr++] = expr[i];

}

if (expr[i] == '(') {

stack[sptr++]=expr[i];

}

if (expr[i] == ')') {

/* pop until left found */

while ((sptr > 0) && (stack[sptr-1] != '(')) {

expr2[eptr++]=stack[sptr-1];

sptr--;

}

sptr--; /* get rid of ( */

}

if (expr[i] == '+')

val = 1;

if (expr[i] == '-')

val = 1;

if (expr[i] == '*')

val = 2;

if (expr[i] == '/')

val = 2;

if (val > 0) {

done = 0;

while (done == 0) {

if (sptr == 0) { /* stack empty */

stack [sptr++] = expr[i];

done = 1;

}

else {

/* check for ( */

if (stack[sptr-1] == '(') {

stack[sptr++] = expr[i];

done = 1;

}

else {

if (stack[sptr-1] == '+')

sval = 1;

if (stack[sptr-1] == '-')

sval = 1;

if (stack[sptr-1] == '*')

sval = 2;

if (stack[sptr-1] == '/')

sval = 2;

/* pop til LWR stck val fnd */

if (sval<val) {

stack[sptr++]=expr[i];

done = 1;

}

else {

expr2[eptr++]=stack[sptr-1];

sptr--;

}

}

}

}

}

}

while (sptr>0) {

/* pop last of stack */

expr2[eptr++]=stack[sptr-1];

sptr--;

}

expr2[eptr]='\0';

strcpy(expr,expr2);

}

Oh, I forgot, it was an MPI project. Just strip all that crap out...

Chris

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

*

* Program: num_int.c

* Name: Chris Kelly - kelly@cs.utk.edu

* Date: 11/14/99

* Class: CS140 - 31788 - Wed. 5:45-8:35 - Lab 8

* Description: This program uses MPI to parallel-process

* a large problem. I have no idea what problem

* at this time, probably computing pi or

* some such. Okay, I've decided what to do. I'm

* gonna set it up to process a segment of a

* given function, expressed in RPN. Yep, good

* ol' numerical integration. If time

* allows, I'll use the process in ch. 3.3 to

* translate algebraic to RPN, making it slicker.

*

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

#include <stdio.h>

#include <mpi.h>

#include <string.h>

#define TRUE 1

#define FALSE 0

float evaluate (char *, float);

void alg(char *);

main(int argc,char *argv[]) {

int rank,size,tag=0,retval,i,source;

char expr[40],mode[4];

MPI_Status sts;

float area,seg,myrange,eachseg,mystart,mystop,f,limits[3];

float temp;

retval = MPI_Init(&argc,&argv);

retval = MPI_Comm_size(MPI_COMM_WORLD,&size);

retval = MPI_Comm_rank(MPI_COMM_WORLD,&rank);

/* find out who we are */

if (rank == 0) { /* we're boss, divvy up the work */

printf("Need Help? (y/n) ");

scanf("%s",expr);

if (expr[0] == 'y') {

printf("This program calculates the area under a \n");

printf("expression, between given limits, by adding\n");

printf("up the requested number of calculated rect-\n");

printf("angles. Just like in the calculus book, the\n");

printf("expression must be a FUNCTION, and it must\n");

printf("be CONTINUOUS between the given limits.\n");

printf("I only support +-/* , x and SINGLE digits.\n");

printf("The expression is entered in RPN or Algebraic,\n");

printf("Algebraic supports parenthesis, but the RPN\n");

printf("is more stable -\n");

printf("e.g. RPN 2x*x*3x*+2+\n\n");

printf("e.g. Alg 2*x*x+3*x+2\n\n");

printf("Note - unary minus not supported.\n\n");

}

printf("Will expression be in (r)pn or (a)lgebraic :");

scanf("%s",mode);

printf("Enter expression (NO SPACES) :");

scanf("%s",expr);

printf("Enter beginning of interval :");

scanf("%f",&limits[0]);

printf("Enter end of interval :");

scanf("%f",&temp);

limits[1]=(double) temp;

printf("Enter # of slices per processor :");

scanf("%f",&limits[2]);

if (mode[0] == 'a')

alg(expr);

for (i=1;i<size;i++) {

MPI_Send(expr,40,MPI_CHAR,i,tag,MPI_COMM_WORLD);

MPI_Send(limits,3,MPI_FLOAT,i,tag,MPI_COMM_WORLD);

}

area = 0.;

for (i = 1;i<size;i++) {

MPI_Recv(&seg,1,MPI_FLOAT,i,tag,MPI_COMM_WORLD,&sts);

area = area + seg;

}

printf("The area under the function is %f\n",area);

}

else { /* slave, accept work */

MPI_Recv(expr,40,MPI_CHAR,0,tag,MPI_COMM_WORLD,&sts);

MPI_Recv(limits,3,MPI_FLOAT,0,tag,MPI_COMM_WORLD,&sts);

myrange = limits[1] - limits[0];

eachseg = myrange/(size-1);

mystart = limits[0] + (rank-1)*eachseg;

mystop = mystart + eachseg;

area = 0.0;

for (f=mystart;f<mystop;f=f+eachseg/limits[2]) {

area = area + eachseg/limits[2] * evaluate(expr,f);

}

MPI_Send(&area,1,MPI_FLOAT,0,tag,MPI_COMM_WORLD);

}

retval = MPI_Finalize();

}

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

* evaluate - figure out value of given

* RPN function at given point

* WARNING - this sucker does NO error

* checking! expression MUST be right!

* code is mine, but concept is from

* Weiss text, page 72.

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

float evaluate (char *expr, float x) {

float stack[30];

int ptr=0,i;

for (i = 0; i<(strlen(expr));i++) {

if (expr[i] == ' ') {

/* ignore for now */

}

if (expr[i] == 'x') {

/* move current val onto stack */

stack[ptr] = x;

ptr++;

}

if ((expr[i] >= '0') && (expr[i] <='9')) {

/* is digit, stack it as value */

stack[ptr] = (int)expr[i] - 48;

ptr++;

}

if (expr[i] == '+') {

/* is add, add two vals on stack */

stack[ptr-2]=stack[ptr-2]+stack[ptr-1];

ptr = ptr -1;

}

if (expr[i] == '-') {

/* is minus, subtract two vals on stack */

stack[ptr-2]=stack[ptr-2]-stack[ptr-1];

ptr = ptr -1;

}

if (expr[i] == '*') {

/* is asterisk, multiply two vals on stack */

stack[ptr-2]=stack[ptr-2]*stack[ptr-1];

ptr = ptr -1;

}

if (expr[i] == '/') {

/* is slash, divide two vals on stack */

stack[ptr-2]=stack[ptr-2]/stack[ptr-1];

ptr = ptr -1;

}

}

if (ptr != 1) {

printf("Evaluate - stack failure!\n");

exit();

}

return(stack[0]);

}

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

* alg - infix->postfix converter -

* this damn routine was harder than the MPI!

* the code is mine, but the process comes

* from Weiss pg. 74.

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

void alg(char *expr) {

char expr2[40];

char stack[20];

int i,sptr = 0,eptr = 0,val,done = 0,sval;

for (i = 0; i<(strlen(expr));i++) {

val = 0;

if (expr[i] == ' ') {

/* ignore for now */

}

if (expr[i] == 'x') {

expr2[eptr] = 'x';

eptr++;

}

if ((expr[i] >= '0') && (expr[i] <='9')) {

expr2[eptr++] = expr[i];

}

if (expr[i] == '(') {

stack[sptr++]=expr[i];

}

if (expr[i] == ')') {

/* pop until left found */

while ((sptr > 0) && (stack[sptr-1] != '(')) {

expr2[eptr++]=stack[sptr-1];

sptr--;

}

sptr--; /* get rid of ( */

}

if (expr[i] == '+')

val = 1;

if (expr[i] == '-')

val = 1;

if (expr[i] == '*')

val = 2;

if (expr[i] == '/')

val = 2;

if (val > 0) {

done = 0;

while (done == 0) {

if (sptr == 0) { /* stack empty */

stack [sptr++] = expr[i];

done = 1;

}

else {

/* check for ( */

if (stack[sptr-1] == '(') {

stack[sptr++] = expr[i];

done = 1;

}

else {

if (stack[sptr-1] == '+')

sval = 1;

if (stack[sptr-1] == '-')

sval = 1;

if (stack[sptr-1] == '*')

sval = 2;

if (stack[sptr-1] == '/')

sval = 2;

/* pop til LWR stck val fnd */

if (sval<val) {

stack[sptr++]=expr[i];

done = 1;

}

else {

expr2[eptr++]=stack[sptr-1];

sptr--;

}

}

}

}

}

}

while (sptr>0) {

/* pop last of stack */

expr2[eptr++]=stack[sptr-1];

sptr--;

}

expr2[eptr]='\0';

strcpy(expr,expr2);

}

- Chris Kelly
**Posts:**5**Joined:**Fri Feb 09, 2001 11:25 am**Location:**USA

5 posts • Page **1** of **1**

Users browsing this forum: No registered users and 3 guests