Velocity Reviews > Simple arithmetic parser example

# Simple arithmetic parser example

Francis Moreau
Guest
Posts: n/a

 12-08-2009
Hello,

I would be interested see some piece of C code that parses arithmetic
expressions.

For example, the parser could parse : "(2+3) / 10 - 4" (respecting the
precedence of each operators) and outputs the result.

I know I can simply use yacc/bison to achieve this goal, but I'm not
really interested in it.

Could anybody point out some code ?

Thanks

Eric Sosman
Guest
Posts: n/a

 12-08-2009
Francis Moreau wrote:
> Hello,
>
> I would be interested see some piece of C code that parses arithmetic
> expressions.
>
> For example, the parser could parse : "(2+3) / 10 - 4" (respecting the
> precedence of each operators) and outputs the result.
>
> I know I can simply use yacc/bison to achieve this goal, but I'm not
> really interested in it.
>
> Could anybody point out some code ?

You can find some algorithm explanations and code samples at:

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Nick Keighley
Guest
Posts: n/a

 12-08-2009
On 8 Dec, 12:31, Francis Moreau <(E-Mail Removed)> wrote:

> I would be interested see some piece of C code that parses arithmetic
> expressions.
>
> For example, the parser could parse : "(2+3) / 10 - 4" (respecting the
> precedence of each operators) and outputs the result.
>
> I know I can simply use yacc/bison to achieve this goal, but I'm not
> really interested in it.
>
> Could anybody point out some code ?

there was a long rambling thread recently on the conversion of infix
to postfix some of which used full-blown parsers to solve the problem.
Try "How to convert infix to postfix"; it *is* excessivly long but
does contain some code.

Ben Bacarisse
Guest
Posts: n/a

 12-08-2009
Francis Moreau <(E-Mail Removed)> writes:

> I would be interested see some piece of C code that parses arithmetic
> expressions.
>
> For example, the parser could parse : "(2+3) / 10 - 4" (respecting the
> precedence of each operators) and outputs the result.
>
> I know I can simply use yacc/bison to achieve this goal, but I'm not
> really interested in it.
>
> Could anybody point out some code ?

This came up quite recently in a huge thread called "How to convert
Infix notation to postfix notation". I posted an example of parsing
using operator precedence tables as did, if I recall, a poster called
Gene. If you can't find it, I'll post again.

[The old code get corrected by posting here. The string type should
have been called String.]

--
Ben.

Ben Bacarisse
Guest
Posts: n/a

 12-08-2009
Ben Bacarisse <(E-Mail Removed)> writes:

> This came up quite recently in a huge thread called "How to convert
> Infix notation to postfix notation". I posted an example of parsing
> using operator precedence tables as did, if I recall, a poster called
> Gene. If you can't find it, I'll post again.
>
> [The old code get corrected by posting here. The string type should
> have been called String.]

Message ID:
(E-Mail Removed)

--
Ben.

Edward A. Falk
Guest
Posts: n/a

 12-08-2009
In article <(E-Mail Removed)>,
Francis Moreau <(E-Mail Removed)> wrote:
>Hello,
>
>I would be interested see some piece of C code that parses arithmetic
>expressions.

First, read up on "recursive descent parsers". They're really easy
and fun to write, and can be used for a million things.

Here's a quick & dirty one I wrote some years ago. It handles the
four basic functions (plus mod). No variables, no functions. It
should do what you want, or at least get you started.

Since all the operators were a single character, it was trivial to
break the input into tokens with a simple regex.

It doesn't do error handling (e.g. divide by zero) and it stops
parsing on syntax error rather than reporting it. Adding these
features is left as an exercise for the reader.

#!/usr/bin/python

'''Evaluate expressions.'''
# Written by Ed Falk

import re

parse_re = re.compile('([-+*/%()])')

def expr(str):
'''Evaluate simple expression using the operators ()+-*/%'''
tokens = [x.strip() for x in parse_re.split(str) if x]
return __sum(tokens)

def __sum(tokens):
rval = __prod(tokens)
while tokens:
if tokens[0] == '+':
tokens.pop(0)
rval += __prod(tokens)
elif tokens[0] == '-':
tokens.pop(0)
rval -= __prod(tokens)
else: break;
return rval

def __prod(tokens):
rval = __val(tokens)
while tokens:
if tokens[0] == '*':
tokens.pop(0)
rval *= __val(tokens)
elif tokens[0] == '/':
tokens.pop(0)
rval /= __val(tokens)
elif tokens[0] == '%':
tokens.pop(0)
rval %= __val(tokens)
else: break;
return rval

def __val(tokens):
if tokens[0] == '(':
tokens.pop(0)
rval = __sum(tokens)
if tokens[0] != ')': raise ArithmeticError
tokens.pop(0)
return rval
elif tokens[0] == '-':
tokens.pop(0)
return -__val(tokens)
else:
return float(tokens.pop(0))

if __name__ == "__main__":
print expr("1")
print expr("2+2")
print expr("1+7/8")
print expr(".875*64")
print expr("1 + 2 * 3/1.5")
print expr("(1+2)*(3+4)")
print expr("-(1+2)*(3+4)")
print expr("(1+2)*-(3+4)")
print expr("22/7")
print expr("355/113")
--
-Ed Falk, (E-Mail Removed)
http://thespamdiaries.blogspot.com/

Phil Carmody
Guest
Posts: n/a

 12-08-2009
(E-Mail Removed) (Edward A. Falk) writes:
> In article <(E-Mail Removed)>,
> Francis Moreau <(E-Mail Removed)> wrote:
>>Hello,
>>
>>I would be interested see some piece of C code that parses arithmetic
>>expressions.

>
> First, read up on "recursive descent parsers". They're really easy
> and fun to write, and can be used for a million things.
>
> Here's a quick & dirty one I wrote some years ago. It handles the
> four basic functions (plus mod). No variables, no functions. It
> should do what you want, or at least get you started.
>
> Since all the operators were a single character, it was trivial to
> break the input into tokens with a simple regex.

Regular expressions aren't C. You'd need a 3rd-party library to do

> It doesn't do error handling (e.g. divide by zero) and it stops
> parsing on syntax error rather than reporting it. Adding these
> features is left as an exercise for the reader.
>
> #!/usr/bin/python

Well, I think we agreed that was legal C

> '''Evaluate expressions.'''

But that isn't.

> rval = __prod(tokens)
> if tokens[0] == '+':

I don't have many positive things to say about the white-space-
incontinent python, but am glad to see that other languages have
made the same 'mistake' as C when it comes to the length of the
assignment and equality-test operator tokens. I have never quite
understood the vehemence of those who take the contrary PoV.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Francis Moreau
Guest
Posts: n/a

 12-09-2009
On Dec 8, 3:00*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
> Ben Bacarisse <(E-Mail Removed)> writes:
> > This came up quite recently in a huge thread called "How to convert
> > Infix notation to postfix notation". *I posted an example of parsing
> > using operator precedence tables as did, if I recall, a poster called
> > Gene. *If you can't find it, I'll post again.

>
> > [The old code get corrected by posting here. *The string type should
> > have been called String.]

>
> Message ID:
> 0.9785fe9ae441464b914b.20091103000526GMT.87r5sgcw1 (E-Mail Removed)
>

Thank you Ben, I'll look into this code and the loooong thread you
pointed out.

Francis Moreau
Guest
Posts: n/a

 12-09-2009
On Dec 8, 10:02*pm, (E-Mail Removed) (Edward A. Falk) wrote:
> In article <(E-Mail Removed)..com>,
> Francis Moreau *<(E-Mail Removed)> wrote:
>
> >Hello,

>
> >I would be interested see some piece of C code that parses arithmetic
> >expressions.

>
> First, read up on "recursive descent parsers". *They're really easy
> and fun to write, and can be used for a million things.
>

Indeed, looks quite simple although the recursivity may be a bad idea
for long expressions.

> Here's a quick & dirty one I wrote some years ago. *It handles the
> four basic functions (plus mod). *No variables, no functions. *It
> should do what you want, or at least get you started.
>

Thanks

Nick Keighley
Guest
Posts: n/a

 12-09-2009
On 8 Dec, 23:59, Phil Carmody <(E-Mail Removed)> wrote:
> (E-Mail Removed) (Edward A. Falk) writes:
>
>
>
>
>
> > In article <(E-Mail Removed)>,
> > Francis Moreau *<(E-Mail Removed)> wrote:
> >>Hello,

>
> >>I would be interested see some piece of C code that parses arithmetic
> >>expressions.

>
> > First, read up on "recursive descent parsers". *They're really easy
> > and fun to write, and can be used for a million things.

>
> > Here's a quick & dirty one I wrote some years ago. *It handles the
> > four basic functions (plus mod). *No variables, no functions. *It
> > should do what you want, or at least get you started.

>
> > Since all the operators were a single character, it was trivial to
> > break the input into tokens with a simple regex.

>
> Regular expressions aren't C. You'd need a 3rd-party library to do
> that. (Or roll your own.)
>
> > It doesn't do error handling (e.g. divide by zero) and it stops
> > parsing on syntax error rather than reporting it. *Adding these
> > features is left as an exercise for the reader.

>
> > #!/usr/bin/python

>
> Well, I think we agreed that was legal C
>
> > '''Evaluate expressions.'''

>
> But that isn't.
>
> > * rval = __prod(tokens)
> > * * if tokens[0] == '+':

>
> I don't have many positive things to say about the white-space-
> incontinent python,

since it looks like my pseudo-code I quite like it. Though I'm pretty

> but am glad to see that other languages have
> made the same 'mistake' as C when it comes to the length of the
> assignment and equality-test operator tokens.

'cos python lifted all its operators from C. I've also thought making
the decision based on length was bizzare.

> I have never quite
> understood the vehemence of those who take the contrary PoV.

because the mathematics people have been using = as an equality
operator since Al-Khwarizmi was a lad (I exagerate to make a point).
Everyone knows assignment should be indicated <- (or, at a push, :=).
It took me ages to train my brain to the C-way of doing things.