guys expression evaluator

[anushhprabu]

can any one give me idea to evaluate an string experssion.. (3+2-(4*3/5)+2 and so on.. it shld also check for the operator precedence...

i finished this code using infix,postfix notations.. but searching for any more ideas (simplest method..) ..

???? :)
thank you..

[D_C]

Use a stack. Then, when you get to something like (3+2), you pop all of those characters and push the equivalent value, 5.

[anushhprabu]

but my trainer told me that there is way to evaluate the expression without using any extra memory.. but only few temp variables are enough...
any idea???

[D_C]

In that case, you can pick two numbers on the same level of parenthesis, and overwrite the numbers. Be sure to multiply and divide first. Here's a run through on the expression you provided.

(3+2-(4*3/5)+2)
( 5 -(4*3/5)+2)
( 5 -( 12/5)+2)
( 5 -   2   +2)
(    3      +2)
         5

3+2 are in the same parenthesis level, and since - follows 2, 3+2 can be calculated because + and - have the same priority. Then, 3+2 is replaced by 5. Since 5 and (...) and (...) + 2 are on different parenthesis levels, the parenthesis must be evaluated.

4*3/5 has * and /, which have the same precedence. Therefore, evaluate left to right. 4*3 is 12, so replace 4*3 by 12. Then, 12/5 is 2, in integer division. The equation then would be (5-(2)+2).

Since there are no more operands in the parenthesis, they can be removed. We get (5-2+2). Since - and + have the same precedence, evaluate left to right. 5-2 is 3, so switch those two. Then (3+2) remains, do that calculation, and shed the parenthesis, and that's your result.

[gasfusion]

why not use pointers and read the expression char by char. you would record all signs and () and evaluate them with if statements within your pointer loop.

[anushhprabu]

guys if the expression contains only single digit numbers no prob, in case of teo or three digit numbers???
also i have to compute the float numbers too...
???
pls soon man..

[anushhprabu]

guys help me ya.. i'm waiting for you.. any idea to evaluate an expression.. it shld be received from user as string, may contain 1 or 2 or 3 digit or more digits.. also for decimal points...

also checks operator preceedence..

pls

[X~coder]

here's the part that checks that the operations are ligal and puts the expretion in a tex file


// david 2.cpp : Defines the entry point for the console application.
//
#include <iostream.h>
#include <conio.h>
#include "math.h"
#include "stdafx.h"
#include "david 2.h"
#include <fstream>



#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// The one and only application object

CWinApp theApp;

using namespace std;

char expresie[1000];

int lungime_expresie;
int contin=1;
int putere_repetata=0;
int impartire_repetata=0;
ofstream expresie_1("expresie_1");

int intrare_gresita(int tip_eroare,char read_var_func)
{
int lungime_mesaj,retur;
retur=6;

switch(tip_eroare)
{case 0:{cout<<" ecuatia nu poate incepe cu "<<read_var_func<<" continuati? Y/N ";
lungime_mesaj=47;//cout<< lungime_mesaj;
break;
}
case 1:{cout<<" nu pot aparea 2 semne consecutiv "<<"' "<<read_var_func<<read_var_func<<" ' continuati? Y/N ";
lungime_mesaj=58;
break;
}
case 2:{cout<<" dupa '(' nu poate aparea ' "<<read_var_func<<" ' continuati? Y/N ";
lungime_mesaj=48;
break;
}
case 3:{cout<<" exprimare ambigua. folositi parantezele continuti? Y/N ";
lungime_mesaj=56;
break;
}
case 4:{cout<<" nu ati inchis toate parantezele continuati? Y/N ";
lungime_mesaj=49;
break;
}
case 5:{cout<<" "<<read_var_func<<" nu e recunoscut ca numar sau ca operatie continuati? Y/N ";
lungime_mesaj=60;
break;
}
case 6:{cout<<" ' ( ) ' nu se efectueaza nici o operatie continuati? Y/N ";
lungime_mesaj=59;
break;
}
case 7:{cout<<"dupa o operatie nu poate urma ')' continuati? Y/N ";
lungime_mesaj=50;
break;
}
case 8:{cout<<"nu exista nici o paranteza dechisa corespunzatoare continuati? Y/N ";
lungime_mesaj=67;
break;
}
}
//cout<<"\b\b\b\b";
char ch;
while(1){
ch = tolower(_gettch());
switch(ch)
{case 'y':{for(int u=lungime_mesaj;u>0;u--)
{cout<<"\b";}
for(int u=lungime_mesaj;u>0;u--)
{cout<<" ";}
for(int u=lungime_mesaj;u>0;u--)
{cout<<"\b";}
retur=1;
break;
}

case 'n':{retur=0;
break;
}

default:{1;}
}
if(retur!=6){return retur; break;}

}
}


int test_erori(char read_var_te,int nr_paranteze,int putere_repetata)
{int eroare_break=1;
if(!(strchr("0123456789+-*/^=()",read_var_te)) )
{if(!(read_var_te=(char)8))
{eroare_break=0;contin= intrare_gresita(5,read_var_te);//cout<<" eroare 5"; ///PRIMUL IF VERIFICA DACA CARACTERUL
}
}
if( (lungime_expresie==1) && (!(strchr("0123456789(",read_var_te)))) ///DACA ESTE PRIMUL CARACTER SI NU E CIFRA SAU
{eroare_break=0;contin = intrare_gresita(0,read_var_te);//cout<<"eroare 0";
}


if (lungime_expresie!=1)

{////////////////////////////

if( (strchr("+-*/^",read_var_te)) && (strchr("+-*/^",expresie[lungime_expresie-1])) )
{eroare_break=0;contin= intrare_gresita(1,read_var_te);/*cout<<" eroare 1";*/}
if( (expresie[lungime_expresie-1]=='(')&&(read_var_te==')') )
{eroare_break=0;contin=intrare_gresita(6,read_var_ te);/*cout<<" eroare 6";*/}
if( (expresie[lungime_expresie-1]=='(') && (strchr("*/^",read_var_te)) )
{eroare_break=0;contin=intrare_gresita(2,read_var_ te);/*cout<<" eroare 2";*/}
if ( (read_var_te=='=') && (nr_paranteze!=0) )
{eroare_break=0;contin=(intrare_gresita(4,read_var _te));/*cout<<" eroare 4";*/}
if( (read_var_te=='^') && (putere_repetata==1) )
{eroare_break=0;contin=intrare_gresita(3,read_var_ te);/*cout<<" eroare 3";*/}
if( (strchr("+-*/^",expresie[lungime_expresie-1]))&&(read_var_te==')') )
{eroare_break=0;contin=intrare_gresita(7,read_var_ te);/*cout<<" eroare 7";*/}
if( (nr_paranteze==0)&& (read_var_te==')'))
{eroare_break=0;contin=intrare_gresita(8,read_var_ te);/*cout<<" eroare 8";*/}
if( (read_var_te=='/')&& (impartire_repetata==1))
{eroare_break=0;contin=intrare_gresita(3,read_var_ te);/*cout<<" eroare 3";*/}
}
return eroare_break;
}


int citire_puteri(char read_var)
{ //cout<<" ggg "<<read_var<<" dss "<<putere_repetata<<" cc ";
if( (read_var=='^') && (putere_repetata==0) )
{putere_repetata=1;
expresie[lungime_expresie]='^'; expresie_1<<'^';
lungime_expresie++;cout<<"^";
return 1;
}
if( (!strchr("0123456789",read_var)) && (putere_repetata==1) )
{putere_repetata=0;return 0;
}
return 0;
}


int citire_impartire(char read_var)
{ //cout<<" ggg "<<read_var<<" dss "<<putere_repetata<<" cc ";
if( (read_var=='/') && (impartire_repetata==0) )
{impartire_repetata=1;
expresie[lungime_expresie]='/'; expresie_1<<'/';
lungime_expresie++;cout<<"/";
return 1;
}
if( (!strchr("0123456789",read_var)) && (impartire_repetata==1) )
{impartire_repetata=0;return 0;
}
return 0;
}


int read_function(void)
{ expresie[0]='(';lungime_expresie=1; expresie_1<<(char)38<<" (";
//int eroare_break=1;
int nr_paranteze=0;
int retur=1;
//int putere_repetata=0;
char read_var;

while(2)
{//cout<<" "<<putere_repetata<<" ";
read_var=_gettch(); //CITESTE CARACTERUL INTRAODUS ////FARA ECOU

if(test_erori(read_var,nr_paranteze,putere_repetat a))
{
if( !citire_puteri(read_var))
{
if( !citire_impartire(read_var))
{

if(read_var=='='){expresie[lungime_expresie]=')';expresie_1<<")="<<endl;expresie[lungime_expresie+1]='=';lungime_expresie+=2;cout<<"=";return 1;break;}
else{
if(read_var==(char)8){cout<<"\b \b";lungime_expresie--;}
else{
expresie[lungime_expresie]=read_var;
expresie_1<<read_var;
if(read_var=='('){nr_paranteze++;}
if(read_var==')'){nr_paranteze--;}
cout<<expresie[lungime_expresie];
lungime_expresie++;
}}
}}}
else { if(!contin) {break;}}
}return 1;
}








int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
int nRetCode = 0;

// initialize MFC and print and error on failure
if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
{
// TODO: change error code to suit your needs
_tprintf(_T("Fatal Error: MFC initialization failed\n"));
nRetCode = 1;
}
else
{int b;
cout<<"hg \n";
read_function();
cout<<"\n a iesit din functie";
for(int i=0;i<=lungime_expresie;i++)
cout<<expresie[i];

//expresie_1<<;
expresie_1.close();
cin>>b;
// TODO: code your application's behavior here.
}

return nRetCode;
}

[X~coder]

now that you have the ecuation in the text file you should try to solve it step by step

i'm using in this ex things like for(int i=........) witch are for reference only
you can use them but you have to go to the right position in the file
or you can use a stack


SORY FOR ALL MY MISSPELINGS :)

ex:

1) search for the most iner "( " somthing like
int poz_(_=1,c=1,poz_)_=1;
char v;
file>>v;
while(v!=')')
{if (x=='(') poz_(_=c;
c++;
file>>v;
poz_)_++;
}

when it exits the loop you should have the position of the most iner "("

(33+44*32-(43-43/(43-9)))
123456...........16...21 ------> (=16 && )=21

2) go to the first digit or sign after the "(" and to the ")" you just found
search for the first operation you have to do for ex:

int poz_op=0,gra=1;


for(int x=poz_(_;i<=poz_)_;++i)
{file>>v;
if(v=='^'){poz_op=i;break;}
if((v=='*')&&(v='/'))poz_op=i;
if(((v=='+')||(v='-'))&&(gra==1))poz_op=i;
}
now you shoud have the position of the operator you have to solve.
after you solve this you have to repet the proses until there are no mare operators inside
the "( ) "

now find the adress of the operator brfor it ( so you know the position of the first number you
have to operate)

int poz_op_2=0

for(int x=poz_(_;i<=poz_op;++i)
{file>>v;
if(!isdigit(v))poz_op_2=i;
}


if it is a "+" ignor it, if it's a "-" stor it in some variable or you have to stor
that your number is <0
your number starts from the adress "poz_op_2 + 1" -----> int poz_first_digit=poz_op_2+1;

int poz_decimal=0;

go on and try to find a decimal
point "." or "," if you find it stor it's adress in poz_decimal

now take an int first_number_int=0, decimal_part=0;
float first_number_float=0;

if the first number is an int then stor it in first_number_int , else stor it in first_number_float

you know where this number starts ( poz_first_digit ) and were it ends ( if you have a decimal point you
have to stop at it and the start again ( you'll see) until poz_op-1 else you'll stop @ poz_op-1)

if (poz_decimal!=0)
{
for(int i= poz_first_digit;i<poz_decimal;++i)
{file>>v;
first_number_int=first_number_int*10+v ; // i'm not shoure about the cast
}
for(int i= poz_decimal+1;i<poz_op;++i)
{file>>v;
decimal_part=decimal_part*10+v; // i'm not shoure about the cast
}
decimal_part=decimal_part/pow(10,n); //wher n is how many digits are in the decimal part you haveto count them
first_number_float=first_number_int+decimal_part;
}
else
{ for(int i= poz_first_digit;i<poz_op;++i)
{file>>v;
first_number_float=first_number_float*10+v ; // i'm not shoure about the cast
}
}

you have to do the same thing with the second number

now that you have bouth numbers and operator yo can comput it and stor the resalt in
float or int depending on your resalt XXX resalt= numb1 op numb ;
you have to use a switch to find what operation to do corponding to your op
and dont forget your numbers can be "<0" or ">0"

when you have the resalt you have to put it back strating with the position of the first digit of the first number
and delet the remening characters until the next operator.

then repet this proses

[anushhprabu]

thanks a lot man... :)

[anushhprabu]

any other new idea to implement the expression evaluator using one single memory space or may be some other new idea to manipulate other than infix to postfix..

i did i two diferent forms but the code is too large.. over 150 line(without checking for unary operators.. or expression errors)..
my spec is::::

1. expression will be a string.. (ie., the input)
2. it would have floating numbers too..
3. need to check for operator precedence.. along with brackets..


help me guys

[anushhprabu]

plssssss help me up yaar...