Not understand post fix math expression.

Index > Main > Not understand post fix math expression.

Author

Thread

Roman

Joined: 21 Apr 2012
Posts: 1769

Roman 20 Apr 2023, 16:28

I want understand how work post fix notation algorithm\idea.
For example:

Code:

txt db "3*-(40+(-2+3)*-4/2)+2",0

How separate numbers and -+*/() ?
And variant separate math to nodes.
For example, given an expression a*b+c*(d*(g-f)) the correct tree would be:

Code:

20 Apr 2023, 16:28

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20303
Location: In your JS exploiting you and your system

revolution 20 Apr 2023, 18:43

Aka: Reverse Polish Notation. RPN.

20 Apr 2023, 18:43

Roman

Joined: 21 Apr 2012
Posts: 1769

Roman 20 Apr 2023, 22:08

My idea split on levels.

Code:

txt db "3*-(40+(-2+3)*-4/2)+2",0

L1: 3*-,.,+2
L2: 40+,.,*-4/2
L3: -2+3

;than start calculating from l3, then l2, then l1

Code:

SECTION '.data' DATA READABLE WRITEABLE executable
        ;txt db "3*-(60-(2+3*(5-1))*4/2)+7",0 ;split this on levels L1,L2,L3
;L1: 3*-,.,+2
;L2: 40+,.,*-4/2
;L3: -2+3
;than start calculating from l3, then l2, then l1
        txt db "3*-((200+3*4)*(4/2+3)*(5-3))+7",0
        tmp dd 20 dup(0)
        buf db 128*10 dup(0)

section '.code' code readable writeable executable
macro up { local .kk
        mov  edi,[ecx]
.kk:    inc  edi
        cmp  byte [edi],0
        jnz  .kk
      }
Start:  sub     rsp,8
        mov  edi,buf
        mov  esi,txt
        mov  ecx,tmp
.l0:    cmp  dword [ecx],0
        jnz  .lla
        mov  [ecx],edi
        jmp  .ll
.lla:   up
        mov  byte [edi],';'
        inc  edi
.ll:
        mov  al,[esi]
        test al,al
        jz   .1
        inc  esi
        cmp  al,"("
        jz   .l1
        cmp  al,")"
        jz   .l2
        mov  [edi],al

        inc  edi
        jnz  .ll
.l1:    mov  byte [edi],"_"
        inc  edi
        mov  byte [edi],0
        add  edi,60
        add  ecx,4
        jmp  .l0
.l2:    sub  ecx,4
        up
        jmp .ll
;show levels
.1:           
               mov     esi,tmp
.2:            mov     eax,[esi]
               invoke  MessageBox,0,eax,0,0
               add     esi,4
               cmp     dword [esi],0
               jnz     .2

Last edited by Roman on 21 Apr 2023, 10:15; edited 4 times in total

20 Apr 2023, 22:08

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 21 Apr 2023, 08:02

In fasm I've been using a very simple algorithm that converts an expression into RPN.

Basic idea is: read tokens, expecting numbers and operators to alternate. When you read a number, place it at the end of converted expression. When you read an operator, store it on the stack, but first check if on the top of the stack you have any operators that are not of higher precedence - if yes, place them all at the end of expression, and only then store your new one on the stack. If you find an operator at the time when you expect a number, then this must be an unary operator, place it on the stack and keep looking for number. When you reach the end of expression, flush any remaining operators on the stack.

If you encounter brackets (only allowed when you're looking for a number), you can store a special marker on the stack - you cannot flush operators past this marker until it is removed by reaching the closing bracket.

Let's try it on your example. For the purpose of this exercise I'm assuming that unary operators have the highest precedence (even though in case of fasm it is not the case).

Code:

Input: 3*-(40+(-2+3)*-4/2)+2
Stack:
Output:

First step, expecting a number, and just placing it in the output:

Code:

Input: *-(40+(-2+3)*-4/2)+2
Stack:
Output: 3

Second step, expecting an operator, placing it on the stack:

Code:

Input: -(40+(-2+3)*-4/2)+2
Stack: *
Output: 3

Third step, expecting a number, but encountered an operator:

Code:

Input: (40+(-2+3)*-4/2)+2
Stack: * unary-
Output: 3

Fourth step, still looking for a number, found a bracket.

Code:

Input: 40+(-2+3)*-4/2)+2
Stack: * unary- (
Output: 3

Keep processing, still looking for a number, and there finally is one.

Code:

Input: +(-2+3)*-4/2)+2
Stack: * unary- (
Output: 3 40

Now operator as expected.

Code:

Input: (-2+3)*-4/2)+2
Stack: * unary- ( +
Output: 3 40

Code:

Input: -2+3)*-4/2)+2
Stack: * unary- ( + (
Output: 3 40

Code:

Input: 2+3)*-4/2)+2
Stack: * unary- ( + ( unary-
Output: 3 40

Code:

Input: +3)*-4/2)+2
Stack: * unary- ( + ( unary-
Output: 3 40 2

Flush the operator from the stack before placing the new one, to avoid placing a lower precedence operator on top of the higher one (this should never happen).

Code:

Input: 3)*-4/2)+2
Stack: * unary- ( + ( +
Output: 3 40 2 unary-

Code:

Input: )*-4/2)+2
Stack: * unary- ( + ( +
Output: 3 40 2 unary- 3

Closing bracket makes us flush everything from the stack until we remove the bracket marker.

Code:

Input: *-4/2)+2
Stack: * unary- ( +
Output: 3 40 2 unary- 3 +

We compare precedence with the operator on the stack. Because * has higher precedence, we do not flush anything, just place it on the top.

Code:

Input: -4/2)+2
Stack: * unary- ( + *
Output: 3 40 2 unary- 3 +

Code:

Input: 4/2)+2
Stack: * unary- ( + * unary-
Output: 3 40 2 unary- 3 +

Code:

Input: /2)+2
Stack: * unary- ( + * unary-
Output: 3 40 2 unary- 3 + 4

Unary minus has a higher precedence, flush it from the stack before storing division there. Multiplication usually has the same precedence as division, flush it too:

Code:

Input: 2)+2
Stack: * unary- ( + /
Output: 3 40 2 unary- 3 + 4 unary- *

Code:

Input: )+2
Stack: * unary- ( + /
Output: 3 40 2 unary- 3 + 4 unary- * 2

Closing bracket, flush the operators.

Code:

Input: +2
Stack: * unary-
Output: 3 40 2 unary- 3 + 4 unary- * 2 / +

We expected the operator now, and there it is. Flush the unary operator first, and also the multiplication that has higher precedence.

Code:

Input: 2
Stack: +
Output: 3 40 2 unary- 3 + 4 unary- * 2 / + unary- *

Code:

Input:
Stack: +
Output: 3 40 2 unary- 3 + 4 unary- * 2 / + unary- * 2

We reached the end of expression, time to flush all the remaining operators:

Code:

Input:
Stack:
Output: 3 40 2 unary- 3 + 4 unary- * 2 / + unary- * 2 +

21 Apr 2023, 08:02

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20303
Location: In your JS exploiting you and your system

revolution 21 Apr 2023, 09:05

Tomasz's algorithm appears to be a subset of the shunting yard algorithm. If you add the exponent operator with opposite associativity order then you have the full version of the shunting yard algorithm.

There is a WP page dedicated to it:
https://en.wikipedia.org/wiki/Shunting_yard_algorithm?useskin=vector

21 Apr 2023, 09:05

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 21 Apr 2023, 09:17

revolution wrote:

Tomasz's algorithm appears to be a subset of the shunting yard algorithm. If you add the exponent operator with opposite associativity order then you have the full version of the shunting yard algorithm.

I did not mention associativity to not introduce too many things at once, but fasmg's implementation does incorporate it, and it is a very simple alteration.

The basic rule that an operator placed on the stack can never be put on top of an operator with higher precedence becomes "never on top of an operator with higher or equal precedence" for left-associative operators, but only "never on top of an operator with strictly higher precedence" for right-associative ones.

In case of fasm 1 all operators were left-associative.

21 Apr 2023, 09:17

DimonSoft

Joined: 03 Mar 2010
Posts: 1228
Location: Belarus

DimonSoft 27 Apr 2023, 14:44

So, maybe Tomasz can become the one who finally explains me what’s the use of the postfix notation as compared to either directly calculating an expression without ever storing its postfix version or storing the expression in a syntax tree? I mean, whenever one stores the postfix version of an expression as a string, the tokenizing part has to be done again later (and it might be even trickier than for the original infix expression). If one stores it as a sequence of tokens, they are going to be used for either calculations or code generation later anyway. So, what’s the point?

27 Apr 2023, 14:44

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 27 Apr 2023, 15:35

In fasm, the tokenization is done by preprocessor, and conversion of an expression into binary-coded RPN is done by the parser (which is another distinct stage before the actual assembly). The assembler then performs multiple passes on this parsed source, and these passes can be fast, because the source is already in a VM-like binary code form, and it has all the expressions in RPN format.

This scenario can be summarized as: parse once, evaluate many times. Something similar happens in fasmg with CALM pre-compiled expression, and there the difference may be even more pronounced, as an expression converted into RPN bytecode might get evaluated thousands of times.

27 Apr 2023, 15:35

Roman

Joined: 21 Apr 2012
Posts: 1769

Roman 28 Apr 2023, 09:26

Fasmg can calculated this?
Mov eax, 3.45*0.5 +2.2

28 Apr 2023, 09:26

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20303
Location: In your JS exploiting you and your system

revolution 28 Apr 2023, 09:40

Roman wrote:

Fasmg can calculated this?
Mov eax, 3.45*0.5 +2.2

Did you try it?

28 Apr 2023, 09:40

Roman

Joined: 21 Apr 2012
Posts: 1769

Roman 28 Apr 2023, 10:15

No.
I not using fasmg.

28 Apr 2023, 10:15

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20303
Location: In your JS exploiting you and your system

revolution 28 Apr 2023, 10:18

It is only one download away.

28 Apr 2023, 10:18

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 29 Apr 2023, 01:04

Roman wrote:

Fasmg can calculated this?
Mov eax, 3.45*0.5 +2.2

Just looking at the source code ...
https://github.com/tgrysztar/fasmg/blob/master/core/source/floats.inc
... we can see that fasmg supports 128-bits of precision for the mantissa and a signed dword for the exponent.

If you want the exact function that does the multiplication of float * float,
https://github.com/tgrysztar/fasmg/blob/708097133e86a9b98efaf59a011c3ae754cdf514/core/source/floats.inc#L508

... all intermediate calculations support this internal type for floats. The MOV instruction definition also supports the reduction of floats to an immediate 16/32/64-bit value.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

29 Apr 2023, 01:04

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum