Solving expressions

[RuiLoureiro]

I want to write a set of procedures to solve
any integer expression with Sub (-), Add (+),
Mul (*), Div (/) or Remainder (\).

Any integer from -4 294 967 295 to 4 294 967 295

The procedures must be as simple as possible
and it must solve any expressions like:

    a)  12 - 3*5 +23 + 5 / 2                                 (=22)
   
    b) (-2 + (-2 * ( 12 - 3*5)+23) + 5) - 15                 (=17)

    c) (-10 - (-2 * ( 12 - 3*5 +23 + 5 / 2) + 20) + 5) - 15   (=4)
    ...

Do you have any ideas ? Tell me

To start i need to solve expressions like a)
and then like b) or c)

[fearless]

http://en.wikipedia.org/wiki/Shunting_yard_algorithm and http://en.wikipedia.org/wiki/Reverse_Polish_notation are probably worth looking at in relation to this.

[jj2007]

There are several threads dealing with this, e.g. Simple formula parser and Floating point Math.

Unfortunately it is not trivial - the macros that solve the formulas below are easy to use (Let MyRes=68.16122-G2*(f1+3*1.8**2.2)+G2*f1) but have about 400 lines. And I never finished it because it was buggy :toothy

Code Select Expand

G1=12.34, G2=43.21 (both global REAL10)
f1=11.11, f2=22.22 (both local REAL10)

Calculating 68.16122-G2*(f1+3*1.8**2.2)+G2*f1 :
Expected value is       -404.2335
Calculated value is     -404.2335
-- Second operand is smaller

Calculating 4-G1*(f2-3.4)+G2*f1 :
Expected value is       251.8243
Calculated value is     251.8243
** Operands are equal or almost equal at 8 digits precision

Calculating 4-G2*(f1+34+3)+G2*f1+2000 :
Expected value is       405.23
Calculated value is     405.23
** Operands are equal or almost equal at 8 digits precision

Calculating 4+5-G2*(f1+34*3)+G2*f1+2000 :
Expected value is       -2398.42
Calculated value is     -2398.42
** Operands are equal or almost equal at 8 digits precision

Calculating 4+5-G2*(f1+(34/3))+G2*f1+2000 :
Expected value is       1519.287
Calculated value is     1519.287
** Operands are equal or almost equal at 8 digits precision

Calculating 4+5-G2*(f1+34*3)-G2*f1+2000 :
Expected value is       -3358.546
Calculated value is     -3358.546
** Operands are equal or almost equal at 8 digits precision

[dedndave]

-4 294 967 295 to 4 294 967 295

33 bits ?
will get you: -4 294 967 296 to 4 294 967 295

i will add this link to the pile   :P

http://en.wikipedia.org/wiki/Order_of_operations

[RuiLoureiro]

fearless,
            shunting-yard algorithm is a method for parsing ...
           
            it seems to be complex.
            I think i dont need to do it and i can solve the problem
            i think we can use a table to solve it and it is more simple
jj,
            Thanks but i want only 32 bit integers
            Simple formula parser is complex

dave,
            33 bits ? why ? 32 bits: sign plus 0 to FFFFFFFFh
            so
            Any integer from -4 294 967 295 to 4 294 967 295

    To solve this:
            b) (-2 + (-2 * ( 12 - 3*5)+23) + 5) - 15

           we need to solve 1-   12 - 3*5   =X
                                    2-   -2*X+23    =Y
                                   3-   -2 + Y + 5 =Z
                                   4-    Z - 15    = result     no ?

            so we need to parse 12 - 3 * 5 and solve and then ...
            its a linear method no ?

[qWord]

And I never finished it because it was buggy

are you interested in further developing? - I've some macros (non- recursively,masm & jwasm) , that are ready to use ...  however, the documentation is currently very bad.

qWord

[oex]

32 bits has 4,294,967,296 range total not -4,294,967,296 to 4,294,967,296.... 256*256*256*256.... The 33rd bit would be the sign for this range

[dedndave]

i think Hutch mentioned this in another thread...
one problem is - the minus sign is both an operator and a modifier
it takes a little logic to sort it out

Rui,
for 33 bits, the signed range is -4 294 967 296 to +4 294 967 295

[MichaelW]

Rui,

Will the expressions be created at runtime from user inputs, or is this something that could be done with the preprocessor? The MASM preprocessor can solve your example expressions, but you must use MOD instead of "\" and the results will be limited to 32 bits.

[jj2007]

And I never finished it because it was buggy

are you interested in further developing? - I've some macros (non- recursively,masm & jwasm) , that are ready to use ...  however, the documentation is currently very bad.

qWord

Hi qWord,

Thanks for the generous offer (not your first one - check MasmBasic.inc, cStyle$ macro :wink).
I've put this a bit on ice, partly because of lack of time, partly because I had some higher priorities for MasmBasic, and partly because it is so bloody complex to get something like Let MyResult=68.92972-GlobTb2*(LocFlt1+3*1.8**2.2)+GlobTb1*LocFlt2+1276 to work properly - you certainly know the problem.
The ambition here is that Let should behave as if it was BASIC. And indeed the statement above works:

Code Select Expand

GlobTb1=12.34, GlobTb2=43.21 (both global REAL10)
LocFlt1=11.11, LocFlt2=22.22 (both local REAL10)

Calculating 68.92972-GlobTb2*(LocFlt1+3*1.8**2.2)+GlobTb1*LocFlt2+1276 :
Expected value is       666.6667
Calculated value is     666.6667
** Operands are equal or almost equal at 8 digits precision

... but I haven't included it in MasmBasic simply because there are only slightly different cases where it misbehaves, and that is not acceptable for a Basic dialect. A second problem is that the simple Let above disassembles to over 80 lines of mostly FPU instructions - and there might be a way to do it with less.

Maybe we could PM each other to exchange ideas and sources?

[tenkey]

I normally use recursive descent method to roll my own parser. But that uses recursive procedure calls.

The operator precedence method doesn't use recursion, but it does require one or two explicit stacks (not the automatic stack used by ESP). It is fundamentally the "railyard shunt" algorithm. The brackets require special precedence rules unless you use "double precedence", where there is a "left side precedence" and a "right side precedence".

The minus sign vs. subtraction operator is solved by allowing the negation operator, and always treating "-" as an operator. You determine the difference between negation and subtraction by noting if the "-" was at the beginning, or if the symbol to the left of the "-" was an operator or a value. (A left bracket is an "operator", a right bracket is the end of a value.)

[jj2007]

just for fun... sequences like fld st(1) ... fst st(1) show that there is a lot of room for improvement; the macro has currently 400 lines, though.

CPU Disasm for Let MyRes=68.92972-GlobTb2*(LocFlt1+3*1.8**2.2)+GlobTb1*LocFlt2+1276
fst st(2)
ffree st
fincstp
fld tbyte ptr [GlobTb2] ; float 43.210000000000000850
fst st(3)
ffree st
fincstp
fld tbyte ptr [ebp-38]
fst st(4)
ffree st
fincstp
push 3
fild dword ptr [esp]
pop eax
fst st(5)
ffree st
fincstp
push 12
fild dword ptr [esp]
pop eax
push 0A
fidiv dword ptr [esp]
pop eax
fst st(6)
ffree st
fincstp
push 16
fild dword ptr [esp]
pop eax
push 0A
fidiv dword ptr [esp]
pop eax
fld st(6)
call X2Exp
fst st(6)
ffree st
fincstp
fld st(5)
fmul st, st(5)
fst st(5)
ffree st
fincstp
fld st(4)
fadd st, st(4)
fst st(4)
ffree st
fincstp
fld st(3)
fmul st, st(3)
fst st(3)
ffree st
fincstp
fld st(2)
fsubr st, st(2)
fst st(2)
ffree st
fincstp
fld tbyte ptr [GlobTb1]          ; float 12.339999999999999860
fst st(3)
ffree st
fincstp
fld tbyte ptr [ebp-2C]
fmul st, st(3)
fst st(3)
ffree st
fincstp
fld st(2)
fadd st, st(2)
fst st(2)
ffree st
fincstp
push 4FC
fild dword ptr [esp]
pop eax
fadd st, st(2)
fst st(2)
ffree st
fincstp
fld st(1)
fst st(1)
ffree st   ; float 666.66670278498440780
fincstp
wait
fstsw ax

[RuiLoureiro]

        Thanks all
Dave,
        «for 33 bits, the signed range is -4 294 967 296 to +4 294 967 295»

        i want 32 bits dword plus sign + or -
        If you type - 4 294 967 295:   sign = - and value=0FFFFFFFFh
       
MichaelW,
        «Will the expressions be created at runtime from user inputs...»

        YES
;***---
        My first try is Calcula12. It uses my own linear method
         
        Try it. Is there a bug ? Tell me please
         
        It seems to work, but it is under test

[dedndave]

hi Rui,

not for 33-bit two's compliment ;)

1FFFFFFFFh is -1
10000000h is -4294967296

[qWord]

Maybe we could PM each other to exchange ideas and sources?

:thumbu, check your PMs