simple expression parser

Index > Main > simple expression parser

Author

Thread

decard

Joined: 11 Sep 2003
Posts: 1092
Location: Poland

decard 01 Aug 2005, 14:56

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:	725 Time(s)

Last edited by decard on 01 Aug 2005, 18:11; edited 1 time in total

01 Aug 2005, 14:56

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4623
Location: Argentina

LocoDelAssembly 01 Aug 2005, 15:04

Try using gets instead of scanf. gets reads a line, I assume that you are looking for

01 Aug 2005, 15:04

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4623
Location: Argentina

LocoDelAssembly 01 Aug 2005, 15:22

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

01 Aug 2005, 15:22

decard

Joined: 11 Sep 2003
Posts: 1092
Location: Poland

decard 01 Aug 2005, 18:09

Thanks

I uploaded fixed version.

01 Aug 2005, 18:09

Madis731

Joined: 25 Sep 2003
Posts: 2138
Location: Estonia

Madis731 02 Aug 2005, 06:45

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

02 Aug 2005, 06:45

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7103
Location: Slovakia

vid 02 Aug 2005, 08:14

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)

02 Aug 2005, 08:14

Madis731

Joined: 25 Sep 2003
Posts: 2138
Location: Estonia

Madis731 03 Aug 2005, 22:30

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...

03 Aug 2005, 22:30

Matrix

Joined: 04 Sep 2004
Posts: 1164
Location: Overflow

Matrix 04 Aug 2005, 10:47

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?

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

04 Aug 2005, 10:47

decard

Joined: 11 Sep 2003
Posts: 1092
Location: Poland

decard 04 Aug 2005, 12:41

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.

04 Aug 2005, 12:41

Picnic

Joined: 05 May 2007
Posts: 1439
Location: Piraeus, Greece

Picnic 28 Oct 2007, 21:22

Nice efford decard.
Later are you planning to add comparison operators?

28 Oct 2007, 21:22

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7103
Location: Slovakia

vid 28 Oct 2007, 21:52

i am afraid decard isn't going to add anything... look at date of his last post...

28 Oct 2007, 21:52

Picnic

Joined: 05 May 2007
Posts: 1439
Location: Piraeus, Greece

Picnic 28 Oct 2007, 22:10

oh i guess you're right vid. I didn't notice that at all Surprised

_________________
⚡ Hobby BASIC Interpreter | Get Started | Showcase

28 Oct 2007, 22:10

wht36

Joined: 18 Sep 2005
Posts: 106

wht36 25 Oct 2009, 19:44

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:	572 Time(s)

25 Oct 2009, 19:44

windwakr

Joined: 30 Jun 2004
Posts: 827

windwakr 25 Oct 2009, 23:36

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:	13319 Time(s)

_________________
----> * <---- My star, won HERE

25 Oct 2009, 23:36

bitshifter

Joined: 04 Dec 2007
Posts: 796
Location: Massachusetts, USA

bitshifter 26 Oct 2009, 09:35

HeHe, i see you are good friends with the kernel Smile

He has protected me on several occasions in the past.

26 Oct 2009, 09:35

wht36

Joined: 18 Sep 2005
Posts: 106

wht36 02 Nov 2009, 08:15

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:	603 Time(s)

02 Nov 2009, 08:15

< 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