March 28, 2024, 04:12:09 PM

News:

Own IWBasic 2.x ? -----> Get your free upgrade to 3.x now.........


Expression Evaluation

Started by sapero, February 24, 2009, 02:19:14 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

sapero

February 24, 2009, 02:19:14 PM Last Edit: February 24, 2009, 04:35:24 PM by sapero
This is a class originaly designed for my current c-header converter, to resolve all enum constants without human interaction. It has implemented basic C operators:() ~ ! * / % + - << >> < > <= >= == != & ^ | && ||plus the conditional one: e1?e2:e3 (if ? then : else).
It is able to automaticaly evaluate after closing a parenthesis, or after appending a integer token if there is a negation, complement or not operator (-n ~n or !n).

The first method for entering data was the add() method:
add("2");
add("+");
add("6");
eval();

Later I have added a high level parse() method which takes a pointer to string with the whole expression:parse("10/(1+(2>1))+12/(1+3-(0<<1))+(-(1^2))");Parse returns the number of accepted bytes and calls eval() for you. To check for evaluation success you need to check if m_top==1 (number of tokens on the internal stack).

There are two example projects - demo1 is a small console demo showing 5 different expressions, demo2 is working like a calculator - has a dialog with edit control.
In the console demo you'll see that after calling parse(), it is evaluating even before the whole input expression string is parsed. The internal stack size is set to 64 tokens (a token is a integer or operator).

pistol350

February 24, 2009, 02:44:19 PM #1 Last Edit: February 24, 2009, 03:06:00 PM by pistol350
Thanks for fixing the error.
Great program.  8)

I almost thought the function could handle an "unlimited" number of arguments ... so i decided to test its limits.  :P
I ended up triggering the " ALU::push error: stack overflow " message
I am a nasty guy, i know  ::)

It seems that once the message appears, it does not leave even though you press the "OK" button
I guess it means that a first "bug" was discovered.
Or maybe i over fed the function with too many arguments....  ::)

EDIT :
Well, i managed to get the error message move after LEFT mouse clicking the "OK" button 53 times  ::)
At the 52nd click i have this message : "Invalid operator combination"  so i guess i put a mistake somewhere anyway.
Regards,

Peter B.

sapero

February 24, 2009, 03:32:06 PM #2 Last Edit: February 24, 2009, 03:35:14 PM by sapero
Hehe, it will show the overflow message until the parse() method has something to parse. Just Press Escape and wait :)
The stack is implemented as a static array of (count=STACK_SIZE) STACKNODE structures, it can be recoded to use dynamic, expandable stack. You know this is just a demo.
Please ignore all error messages but the first. Only the first one is accurate, there is no error reporting feedback yet.

Every STACKNODE structure stores a single operator or integer:
after parse("1+2+3"); the local stack is:

m_stack[4] = '3'; // m_stack[4].type = NTYPE_INTEGER; m_stack[4].value = 3
m_stack[3] = '+'; // m_stack[3].type = NTYPE_OPERATOR; m_stack[3].optype = Addition
m_stack[2] = '2';
m_stack[1] = '+';
m_stack[0] = '1';

I know STACK_SIZE=64 is small, but enough for enumerations from c-headers. The longest enum value I've found is CLUSTER_CHANGE_ALL, it has 125 tokens in total, but with alot of parentheses: (((a|b)|c)|d) - does not exceed 64 tokens, because every ')' evaluates a bit and pops '()' from the stack.

pistol350

Ok. i have a better view of how it works internally.

I purposedly added a lot of arguments just to see the consequences.
I do not expect anyone to use as many arguments as i did for a real calculation so nothing to worry about.

Thanks again  :)
Regards,

Peter B.

sapero

I have updated the attachment again. Before pm'ing you I have added division by zero check, and popped the value into the wrong variable (the first GetAt call in ALU::fnDivision), so the division was incorrect.

pistol350

Regards,

Peter B.

Haim

Great class.
Thanks for sharing this with us.

Haim

sapero

I have added variables support to this class - it will call the new, virtual GetVariableValue method if it detects at least one letter. It may call multple times for same variable, so keep your database open.
The demo2 example derieves new ALU2 class wiith GetVariableValue implementation, where the user is prompted to enter the value if the variable was not found in dictionary.

Now, on error you'll see only one messagebox (owned). The Parse method will quit on first failure, and the Eval will detect incomplete or empty parentheses.
Added also a method called DeleteGetDeleteDecGet, which performs some common tasks for most operators. See in ALU::fnMultiplication and later what it does.

pistol350

"DeleteGetDeleteDecGet"  :o

Which language is that word From ?  ;D
Good addition.
Regards,

Peter B.

sapero

February 26, 2009, 10:48:12 AM #9 Last Edit: February 27, 2009, 02:39:13 AM by sapero
I have renamed it to EvalPopParams.
The next version (1.2) implements user defined functions:
class ALU2 : ALU
{
declare virtual ExecuteFunction(string name, FUNCPARAMS *parameters, int *ppResult),BOOL
{
if ((name == "sqr") && (parameters->count == 1))
{
*ppResult = sqrt(parameters->param[0]);
return TRUE;
}
else if ((name == "abs") && (parameters->count == 1))
{
*ppResult = abs(parameters->param[0]);
return TRUE;
}
if ((name == "add") && (parameters->count == 2))
{
*ppResult = parameters->param[0] + parameters->param[1];
return TRUE;
}
return ALU!!ExecuteFunction(name, parameters, ppResult);
}
}


The initial expression has changed to add(3,2) + sqr(abs(-9))

EDIT: the internal stack is expandable, it will accept expressions of any lenght. On error you'll get the bad character index by calling GetError method.

Haim

Thanks for the update.
When I try to build demo2 I get "Error compilin resources.

Any idea why this is so?

Haim

n.b.
I am using Aurora RC3

sapero

February 27, 2009, 02:26:40 AM #11 Last Edit: March 25, 2009, 06:48:08 AM by sapero
I forgot to add the uni.ico to the archive. Please copy the icon from previous version, and I'll update the latest attachment in few minutes.
I have added two methods for error handling, and modified the Parse method to return success/failure and the resultant.

By the way, Aurora does not forward resource compiler error messages, so I always pick the .rc file and compile it from the command prompt:
cd "fullpath\aurora\bin"
gorc /r "full path to .rc file"
QuoteGoRC.Exe Version 0.90.2

Error!
Line 22 of Resource Script[...]
Could not find file:-
uni.ico

RES file not made

Haim


sapero

February 28, 2009, 04:47:09 AM #13 Last Edit: February 28, 2009, 06:07:36 PM by sapero
The third version comes with the ability to define custom functions at run time. The example has a list view with all defined functions, and buttons to create new, modify or remove existing.
New method DefineFunction parses the definition and appends it as a structure into internal list. If such function is found in your expression and you do not handle it in ExecuteFunction, a new derieved class will be llocated by the default ExecuteFunction handler to just evaluate the expression with private variables, if any.
DefineFunction("RGB(r,g,b)", "b<<16 | g<<8 | r");
The first string must be without spaces. Function and variable names are case sensitive.

The ALU2 class has a constructor which loads all the defined functions from the list view. ALU2::ExecuteFunction method handles SQR function only, because ADD and ABS are now defined as dynamic functions.

EDIT: added hexadecimal support and variables view.
EDIT: variable view->add did not save in the dictionary.


sapero

I have found a BUG in ALU::DeleteAt method - a missing condition for node->type before deleting node->FuncNameALU::DeleteAt(int position),BOOL
{
int index = m_top - position - 1;
if (index >= 0)
{
m_top--;
if (position)
{
STACKNODE *node = &*m_stack[index];
if ((node->optype > 65535) && (node->type == NTYPE_OPERATOR)) // missing node->type check
{
delete node->FuncName;
}
memcpy(node, &*node[1], sizeof(STACKNODE) * (m_top-index));
}
}
return (index >= 0);
}