I needed to test out an idea for opening inner brackets sequentially on bracketed maths formulas so i wrote up a test piece for it.

The code sequentially finds the first pair of inner brackets, copies the contents to a buffer and then replaces the copied area with a variable. It continues to do this until all of the brackets have been opened. The result is displayed in a message box which is each bracketed pair with contents assigned to a return value.

What I envisage when I get a bit more time is to do the calculations in process in 80 bit floating point maths and store each result in the return value displayed in the message box and sequentially perform the calculations until a final result is calculated.

The demo currently displays a default formula which can be changed and reparsed. The formula requires complete bracketing including enclosing the complete formula. It tests for non matching brackets but it will not catch errors from missing bracket pairs.

Regards,

hutc@movsd.com
Posted on 2003-02-22 01:03:01 by hutch--
Nice. I did something somewhat similar once. I had intended to write a full DAL (Direct Algebraic Logic) Calculator. But like most things I never finished it :) .

Unfortunatly It doesn't prase text but rather I suppose a form of byte code, so it ain't as useful. Here it is anyway.

Left click and it will display the Equation, result plus a full print out of the steps it went through in reducing the equation.
Posted on 2003-02-22 09:58:16 by Eóin
I did a similar thing a while ago that converted a C expression to an intermediate assembler type of language. It did optimizations also, it removed subexpressions that was calculated more than once and optimized register usage. It was going to be a real compiler but I never finished it since it got too complicated. I am going to restart that project and write a real compiler some time. I have to learn a little more first.
Posted on 2003-02-23 12:13:58 by gliptic

As obvious as it may seem, split it in as many modules as possible, organize them well.. and it will retain its simplicity, even if it grows a lot as a whole.
My first compiler (for the Amiga) grew as a big mess because the concept of modularity wasn't yet carved in my mind. The mess limits the quality of the final work a lot.
Nowadays not only my PC compiler is modular, but all of my code is (I've my big set of routines (an OS, in practice.. either it runs under Win32, DOS, or native) that I reuse for all of my programs).
Posted on 2003-02-23 13:15:22 by Maverick
I am just playing with the next step which is to do the calculations on the fly so there are no dual conversions from FP to string and back again.

I am working in 80 bit floating point as there is no reason to use smaller and I have just rediscovered how rusty my FP coding is, wasted a couple of hours last night debugging an addressing error that followed from not handling the extra level of indirection for the array of REAL10 variables.

What I am interested in is if there is any variation in precision depending on which way you parse the arguments for each pair of inner brackets. This one parses left to right but I wonder if changing the order of calculation from right to left would effect the precision either way.

Regards,

hutch@movsd.com
Posted on 2003-02-23 14:12:32 by hutch--
Once you follow the whole BOMDAS operator order the weither you go left or right shouldn't affect things.

That said there could still be problems, maybe. if you have x1 + x2 + x3 where both x2 & x3 are so much smaller than x1 that adding either to x1 on their own would see them lost due to a lack of precision. However the number (x2 + x3) may be just big enough to not get lost.

Then the answer going left to right (x1 + x2) + x3 would be different to x1 + (x2 + x3).

I don't know if this is really the case though. I would suggest going from left to right and leave it to the user to make correct use of brackets to maintain the highest precision.
Posted on 2003-02-24 06:10:02 by Eóin

I am just playing with the next step which is to do the calculations on the fly so there are no dual conversions from FP to string and back again.


What I am interested in is if there is any variation in precision depending on which way you parse the arguments for each pair of inner brackets. This one parses left to right but I wonder if changing the order of calculation from right to left would effect the precision either way.

Regards,

hutch@movsd.com


It won't change the precision, but it will certainly change the accuracy.
Actually, left to right vs. right to left are only two combinations.
In fact, just about any ordering you should (middle outwards, for example)
can affect the accuracy of the result. As an extreme example, consider
the following 32-bit calculation:

X*Y/Z

If you compute t1=X*Y
and then t2=t1/Z
you get a decidely different answer than
t1=Y/Z
t2=X*t1

We've all come to accept this out of integer arithmetic,
but the same principle holds for floating point arithmetic, too.

Indeed, one of the main reasons for doing FP math in assembly
these days is exactly because few languages guarantee the
order of evaluation and if you must ensure that a calculation
takes place in a certain order, assembly is the only way to go.
Posted on 2003-02-25 14:37:51 by rhyde
Steve,
why doesn't it handle members out of parences?
For example like 2*(x/y)*z ?
Posted on 2003-02-28 18:27:52 by The Svin
Another way way is to use the forth stack concept (or the HP scientific calculators ...same concept)

Push the operators and the numbers on a stack and then execute them in reverse order leaving results on stack for the next operators ... it is simple or should be simple

that is the real reason why the FPU was originally designed with a stack registers concept...

Just implement a real stack not a circular one :)
Posted on 2003-02-28 18:55:03 by BogdanOntanu
Randy,

Thanks for you comments here, my maths have just about dropped to finger counting levels so I need some input on this one.

It actually does inner to outer but where formula can be written with multiple nested bracketing, it does the left side first then the next left until it opens all bracket pairs.

Alex,

At this stage it is a bracket opening parser so it will perform each operation based on the bracket pair count. What I have in mind with it is to evaluate each pair of numerical expressions on the basis of the arithmetic operator and keep performing the calculation until there are no operators left. This will handle formula that has outer values that are not enclosed in brackets without any problems.

I don't personally see the point of allowing more than two operators between brackets as bracketing makes the entire operation unambiguous.

Bogdan,

A coded stack is an interesting idea, what I had been playing with is an array of 80 bit FP values that match the parsing order and it involves converting a notation that indicates a value in a variable rather than an immediate value. I think the conversion from a string value #1 or similar to the array index "1" is probably fast enough not to worry about. The dedicated parser for evaluating the contents of each bracket pair is simple enough I think, I was going to use a table that only allowed numbers, operators and the variable notation to deliver the first value, the operator and the second value.

Regards,

hutch@movsd.com
Posted on 2003-03-06 04:55:28 by hutch--
Hutch,

IMHO, your thinking in the right lines of thought... your hinting at a binary tree structure. Where each parent node is an operator, and only at the end 'leafs' of the tree is actual numeric data. The tree is built by parsing for brackets/operators/data and is evaluated from the bottom up to one final numeric result. The evalutation is recursive: Left leaf :: Parent Node operator :: Right leaf, untill there is no more parent nodes.

Here is your example layed out as such:
Posted on 2003-03-27 23:04:22 by NaN
I sence this topic has gone dead... too bad i guess.
Posted on 2003-04-03 23:26:43 by NaN
Nan,

I tested what I needed in the algo and that was opening brackets, getting the contents and stacking them in what you describe as a tree so it has done for the moment what I was after.

I have just got my development box back after a trashed power supply so i can play again with a few ideas but the next attempt will be more dedicated to code style functions which is more parsing than maths.

I think the existing version of this algo will do the job on interger maths fine but I need to brush up on my FP coding to do a proper FP version.

Regards,

hutch@movsd.com
Posted on 2003-04-04 02:20:03 by hutch--
I'm currently working on a 100% LL solution... currently trying to decide between BODMAS and BOMDAS math protocols - I was taught BODMAS but I understand BOMDAS is more popular among modern academics..
Yeah, the topic is a worthy one and I'll post my code eventually...

Anyone else interested in this stuff?

When I originally began coding this stuff some 6 months ago (yes I have a lot of concurrent projects underway), I called it a Bracket Tree. The code was originally to have been part of my giant binary math lib.
I'm rewriting it to perform optimized on-the-fly calculations which support algebraic paraphrasing. This time it is to be part of my "game hierarchy editor" where I wish to apply complex formulae to the attributes of objects in a similar way to that used by the Maya 3d suite.
The idea is that you can create associations based on formulae between the attributes of objects, such that those values are constantly updated (when an input parameter has changed, we'll recalc).
This can be used in so many ways:
implementing game enemy ai,
as an aide in automating animation of in-game objects,
as a method of soft-coding much of the general game logic,
in fact, with a little thought, this stuff allows us to softcode MUCH of what is traditionally hard-coded... this makes it relatively simple to update the client software without requiring us to patch binary files.
It also means that my hierarchy editor blows out into a fully-fledged GAME editor.
cya.
Posted on 2003-04-04 23:26:05 by Homer
Kool!

I decided to write my own version tonight... im 85% finished.. i have the tree evaluation routines working.. (OOP Asm makes this very simple with recursion). Im currently 50% finished the parsing engine that will build the binary tree. I plan to be done tomorrow.. would be interested in seing your spin on the same idea... the BEMDAS may have some merit to it (i didnt stop to think about this)...

Perhaps a 'checkbox' item to toggle between...?

:alright:
NaN
Posted on 2003-04-05 00:12:36 by NaN
Here is a small taste of the Parsing engine... I dont have it linked with the calculation routine yet (as im hung up on converting ascii to doubles at the moment). I know i can use CRTDLL.DLL to do this, but i would rather have my own version (with source).

WHen you run it, you'll get the evalation output as it checks and parses the equation into pieces.

A "pure" expression is like " ( 3 * 5 ) "
Not Pure would be " 3 * 5 "
Numbers are self explanitory.. Suports both int and doubles..
It will strip unecessisary bracketing too like "( (3 ) * 5 )"

Every time you see "V----Balanced-----V" it would represent another node on the binary tree...

Oh ya, operation codes are: 1 (add) 2 (sub) 3 (div) 4 (mul)

This should be done soon... I hope to make it produce code when its done...


:alright:
NaN
Posted on 2003-04-05 19:25:39 by NaN
Well Its up and running now. It generates a Listbox with assembly of the various steps.. It would be helpfull for complex algorithms that do not require opomization. (I didnt wast too much time on making it optimal).

It will however work with BIG calculations, well over the stack depth of the FPU. To do so, there are a few steps taking place

    [*]Parse the origional string, and make sure its complete, and balanced brackets
    [*]If good, Parse again creating objects off the heap, and linking into a Binary Tree style linked list. This tree will be unbalanced, since its a function of the text you provide.
    [*]Once parsed, and memory is alloctaed, assigned, and linked. There is a Conditioning step, that will evaluate the generated binary tree, and determine where the deepest 'leaves' start, assigning each node a ranking number.
    [*]The Calculate method then follows to the furthest leaves (as indicated by each branch #) and generate the math onto the list box, as well as do internal calculations.
    [*]The result shows the final answer from the numbers you give. As well the list box will have the assembly it has performed along the way in order.


    Perhaps later on i will write in a button to save this assembly to disk, but for now its only on the list box.

    Everything is totally recursion (Parse, Condition, Calculate). Its mildly documented, but should be readable.

    Lastly, it supports integers and floats, but for integers you need to do (0-3) for minus 3. Apparently "atodw" doesnt support signs properly.

    Hope you like, im sure there is alot in there for "opomization" if your looking for a challenge ;)

    Let me know what you think ;)

    :alright:
    NaN
Posted on 2003-04-13 23:13:46 by NaN