flat assembler
Message board for the users of flat assembler.

flat assembler > Main > simple expression parser

Author
Thread Post new topic Reply to topic
decard



Joined: 11 Sep 2003
Posts: 1095
Location: Poland
Here's a simple expression parser that uses RPN (reverse polish notation) calculator. It can parse expressions such as:

(34+12/4545-45*(343+12)) - 1

It will correctly resolve braces and take care of operator precedense. This is first realese, so it don't handle invalid expressions, and it supports only 4 operators: +, -. * and /.

Algorithm is very simple; expression is converted to RPN format and then calculated. Implementation is stack based, here you can find details: http://www.codeproject.com/cpp/rpnexpressionevaluator.asp

And I have a small but annoying problem: when you enter an expression you can't put spaces between numbers and operators. My code can handle them, but it is a problem with scanf function from crtdll.dll library. I use followin code to read user's input:

Code:
szScanStr db '%s', 0

(...)

cinvoke scanf, szScanStr,szExpr    

if user types "1 + 2", scanf returns only "1". Do you have any idea how to make it read whole string? Confused


Description:
Download
Filename: expressions.zip
Filesize: 6.27 KB
Downloaded: 255 Time(s)



Last edited by decard on 01 Aug 2005, 18:11; edited 1 time in total
Post 01 Aug 2005, 14:56
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
Try using gets instead of scanf. gets reads a line, I assume that you are looking for
Post 01 Aug 2005, 15:04
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
This is from a C book:

char *gets(char *s)
gets reads the next input line into the array s; it replaces the terminating newline with '\0'. It returns s, or NULL if end of file or error occurs.

char *fgets(char *s, int n, FILE *stream)
fgets reads at most the next n-1 characters into the array s, stopping if a newline is encountered; the newline is included in the array, which is terminated by '\0'. fgets returns s, or NULL if end of file or error occurs.

In the case of fgets I don't remember well but if you pass as stream 1 you read from standard input (stdin).

Example: cinvoke fgets, szExpr, bufferSize, 1

I hope this will help you
Post 01 Aug 2005, 15:22
View user's profile Send private message Reply with quote
decard



Joined: 11 Sep 2003
Posts: 1095
Location: Poland
Thanks Smile I uploaded fixed version.
Post 01 Aug 2005, 18:09
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Same problem as described on codeproject forums:
Code:
C:\WINDOWS\Desktop>expressions
enter expression: ((( -1 + 1) + 1) + 1)
number: 4202981

C:\WINDOWS\Desktop>expressions
enter expression: (((-1+1)+1)+1)
number: 4202981
    
Post 02 Aug 2005, 06:45
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7108
Location: Slovakia
you've heard it doesn't support unary operators (unery "-", as negation not as subtration), so this is invalid expresion (which it cannot detect too)
Post 02 Aug 2005, 08:14
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Couldn't it just push 0 to the stack when it encounters unary ± signs because they are add/sub instructions - just without visible zero.
Ok, while I understand that unary is a thorn I really don't see the need to support both RPN and "regular" notation. This gets it confused Smile
Code:
enter expression: (2 5+)-2*(1 4-5+)-4
number: 7
    

it pushes 2 and 5 on the stack and adds them, btw you can't unbalance the operators in the brackets because it hangs. Moving forward it does nothing. It doesn't do anything anymore. Strange! I'll take a shovel and start digging until I find a solution to this problem...
Post 03 Aug 2005, 22:30
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
decard wrote:
Here's a simple expression parser that uses RPN (reverse polish notation) calculator. It can parse expressions such as:

(34+12/4545-45*(343+12)) - 1

It will correctly resolve braces and take care of operator precedense. This is first realese, so it don't handle invalid expressions, and it supports only 4 operators: +, -. * and /.

Algorithm is very simple; expression is converted to RPN format and then calculated. Implementation is stack based, here you can find details: http://www.codeproject.com/cpp/rpnexpressionevaluator.asp

And I have a small but annoying problem: when you enter an expression you can't put spaces between numbers and operators. My code can handle them, but it is a problem with scanf function from crtdll.dll library. I use followin code to read user's input:

Code:
szScanStr db '%s', 0

(...)

cinvoke scanf, szScanStr,szExpr    

if user types "1 + 2", scanf returns only "1". Do you have any idea how to make it read whole string? Confused


Hello Decard,
my idea is, if you first parse your input string before it is aanalysed, without spaces, you can get it work.

Code:
mov esi,inbuf
mov edi,outbuf
call spaceless
...


spaceless: ; copies string without spaces
mov al,[esi]
inc esi
cmp al,' '
je .skip_space
mov [edi],al
inc edi
.skip_space:
or al,al
jnz spaceless
ret

    

as for the negative number i whould make a proc "getnumber" that whould get number and if it gets ('-1'+'1' it should get '-1' as negative

hmm and this case is i think invalid expression:
Code:
enter expression: (2 5+)-2*(1 4-5+)-4 
    

operators have to be followed by a valid number
Post 04 Aug 2005, 10:47
View user's profile Send private message Visit poster's website Reply with quote
decard



Joined: 11 Sep 2003
Posts: 1095
Location: Poland
Well, I warned you that it was first version without any error checking. Wink

I don't know how exactely my code should distinguish between unary and binary operators, but I have some idea and now I'm going to implement it.

Matrix: my code takes care about the spaces (not exactely in the way you suggested it, but it does the same thing). It was only CRTDLL function that I was using. And now it is fixed, above attachement works OK.
Post 04 Aug 2005, 12:41
View user's profile Send private message Visit poster's website Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1277
Location: countryside
Nice efford decard.
Later are you planning to add comparison operators?
Post 28 Oct 2007, 21:22
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7108
Location: Slovakia
i am afraid decard isn't going to add anything... look at date of his last post...
Post 28 Oct 2007, 21:52
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1277
Location: countryside
oh i guess you're right vid. I didn't notice that at all Surprised
Post 28 Oct 2007, 22:10
View user's profile Send private message Reply with quote
wht36



Joined: 18 Sep 2005
Posts: 106
If anyone still interested, here is a good post from http://www.strchr.com/expression_evaluator. I've converted his cpp source to fasm as well (see attached).


Description:
Download
Filename: expr_eval.zip
Filesize: 3.31 KB
Downloaded: 148 Time(s)

Post 25 Oct 2009, 19:44
View user's profile Send private message Reply with quote
windwakr



Joined: 30 Jun 2004
Posts: 827
Location: Michigan, USA
wht36 wrote:
If anyone still interested, here is a good post from http://www.strchr.com/expression_evaluator. I've converted his cpp source to fasm as well (see attached).



Neat! Also, thanks for the link. I was just looking at expression evaluating earlier today.

But there seems to be a bug in it(see attached picture).

I typed "2*(5+3)" then pressed enter, and then enter again.

Offset given under more info is 104Ch in expr_eval.exe, if that is any help.


EDIT: Is it just me, or is there A LOT of recursion going on? Is there any simpler way to do it?


Description:
Filesize: 17.19 KB
Viewed: 4117 Time(s)

expreval_bug.PNG



_________________
----> * <---- My star, won HERE
Post 25 Oct 2009, 23:36
View user's profile Send private message Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 754
Location: Massachusetts, USA
HeHe, i see you are good friends with the kernel Smile
He has protected me on several occasions in the past.
Post 26 Oct 2009, 09:35
View user's profile Send private message Reply with quote
wht36



Joined: 18 Sep 2005
Posts: 106
windwakr wrote:
wht36 wrote:
If anyone still interested, here is a good post from http://www.strchr.com/expression_evaluator. I've converted his cpp source to fasm as well (see attached).



Neat! Also, thanks for the link. I was just looking at expression evaluating earlier today.

But there seems to be a bug in it(see attached picture).

I typed "2*(5+3)" then pressed enter, and then enter again.

Offset given under more info is 104Ch in expr_eval.exe, if that is any help.


EDIT: Is it just me, or is there A LOT of recursion going on? Is there any simpler way to do it?


Oops, fixed. I was using jmp ExitProcess instead of invoke ExitProcess,0 for the return. That's why it gave an error.

I'm not very clued up about expressions, I'm afraid. I think converting to postfix notation (decard) will use much less recursion, but will need an extra conversion step, so that may not be a simpler way, but perhaps people who are used to postfix notations will find it simpler.


Description:
Download
Filename: expr_eval.zip
Filesize: 3.31 KB
Downloaded: 147 Time(s)

Post 02 Nov 2009, 08:15
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.