flat assembler
Message board for the users of flat assembler.
Index
> Main > Not understand post fix math expression. 
Author 

revolution 20 Apr 2023, 18:43
Aka: Reverse Polish Notation. RPN.


20 Apr 2023, 18:43 

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*(51))*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)*(53))+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 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: Code: Input: *(40+(2+3)*4/2)+2 Stack: Output: 3 Code: Input: (40+(2+3)*4/2)+2 Stack: * Output: 3 Code: Input: (40+(2+3)*4/2)+2 Stack: * unary Output: 3 Code: Input: 40+(2+3)*4/2)+2 Stack: * unary ( Output: 3 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 ( + ( 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 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 Code: Input: *4/2)+2 Stack: * unary ( + Output: 3 40 2 unary 3 + 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 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 Code: Input: +2 Stack: * unary Output: 3 40 2 unary 3 + 4 unary * 2 / + 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 Code: Input: Stack: Output: 3 40 2 unary 3 + 4 unary * 2 / + unary * 2 + 

21 Apr 2023, 08:02 

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 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. 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 leftassociative operators, but only "never on top of an operator with strictly higher precedence" for rightassociative ones. In case of fasm 1 all operators were leftassociative. 

21 Apr 2023, 09:17 

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 27 Apr 2023, 15:35
In fasm, the tokenization is done by preprocessor, and conversion of an expression into binarycoded 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 VMlike 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 precompiled 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 28 Apr 2023, 09:26
Fasmg can calculated this?
Mov eax, 3.45*0.5 +2.2 

28 Apr 2023, 09:26 

revolution 28 Apr 2023, 09:40
Roman wrote: Fasmg can calculated this? 

28 Apr 2023, 09:40 

Roman 28 Apr 2023, 10:15
No.
I not using fasmg. 

28 Apr 2023, 10:15 

revolution 28 Apr 2023, 10:18
It is only one download away.


28 Apr 2023, 10:18 

bitRAKE 29 Apr 2023, 01:04
Roman wrote: Fasmg can calculated this? https://github.com/tgrysztar/fasmg/blob/master/core/source/floats.inc ... we can see that fasmg supports 128bits 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/64bit value. _________________ ¯\(°_o)/¯ “languages are not safe  uses can be” Bjarne Stroustrup 

29 Apr 2023, 01:04 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.