flat assembler
Message board for the users of flat assembler.

 Index > Main > Not understand post fix math expression.
Author
Roman

Joined: 21 Apr 2012
Posts: 1710
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:
```         +
/ \
*   \
/ \   \
a   b   \
*
/ \
c   *
/ \
d   -
/ \
g   f    ```
20 Apr 2023, 16:28
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20179
revolution 20 Apr 2023, 18:43
Aka: Reverse Polish Notation. RPN.
20 Apr 2023, 18:43
Roman

Joined: 21 Apr 2012
Posts: 1710
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
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
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: 8346
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: 20179
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: 8346
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: 8346
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: 1710
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: 20179
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: 1710
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: 20179
revolution 28 Apr 2023, 10:18
28 Apr 2023, 10:18
bitRAKE

Joined: 21 Jul 2003
Posts: 3962
Location: vpcmipstrm
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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

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