RPN 
Author Message
 RPN

Does anyone know the implementation of rpn (reverse polish notation) in
scheme.
The program should be able to calculate an equation of the form 2 3 + 5
/ but should be rpn implementation.


Thu, 16 May 2002 03:00:00 GMT  
 RPN
+---------------
| Does anyone know the implementation of rpn (reverse polish notation) in
| scheme.  The program should be able to calculate an equation of the form
| 2 3 + 5 / but should be rpn implementation.
+---------------

        > (eval (tree-reverse '((2 3 +) 5 /)))
        1
        >

[Writing "tree-reverse" is left as an exercise for the student...]

-Rob

p.s. Hint:

        > (tree-reverse '((2 3 +) 5 /))
        (/ 5 (+ 3 2))
        >

-----

Applied Networking              http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.          Phone: 650-933-1673
1600 Amphitheatre Pkwy.         FAX: 650-933-0511
Mountain View, CA  94043        PP-ASEL-IA



Sat, 18 May 2002 03:00:00 GMT  
 RPN

Quote:

> +---------------
> | Does anyone know the implementation of rpn (reverse polish notation) in
> | scheme.  The program should be able to calculate an equation of the form
> | 2 3 + 5 / but should be rpn implementation.
> +---------------

>    > (eval (tree-reverse '((2 3 +) 5 /)))
>    1

> [Writing "tree-reverse" is left as an exercise for the student...]

> -Rob

> p.s. Hint:

>    > (tree-reverse '((2 3 +) 5 /))
>    (/ 5 (+ 3 2))

Ah, but what if the RPN is of the form?

        (2 3 + 5 /)

__Jason



Sat, 18 May 2002 03:00:00 GMT  
 RPN

Quote:


> +---------------
> | Does anyone know the implementation of rpn (reverse polish notation) in
> | scheme.  The program should be able to calculate an equation of the form
> | 2 3 + 5 / but should be rpn implementation.
> +---------------

>         > (eval (tree-reverse '((2 3 +) 5 /)))
>         1

> [Writing "tree-reverse" is left as an exercise for the student...]

> -Rob

> p.s. Hint:

>         > (tree-reverse '((2 3 +) 5 /))
>         (/ 5 (+ 3 2))

what about (tree-reverse '((2 3 -) 5 /))
(/ 5 (- 3 2))

not the same I would think let's see
2 3 - = 2 - 3 /= 3 - 2

So wasn't the right tip I would think. But if one does not care about
correctness it's quite ok ;-)

Regards
Friedrich



Sat, 18 May 2002 03:00:00 GMT  
 RPN

Quote:

> So wasn't the right tip I would think. But if one does not care about
> correctness it's quite ok ;-)

> Regards
> Friedrich

Well, then, it would be quite ok for many students that I've had...

Jay



Sat, 18 May 2002 03:00:00 GMT  
 RPN

Quote:

> Ah, but what if the RPN is of the form?

>    (2 3 + 5 /)

Then obviously you'll need something external that tells you the arity
of what you're currently looking at:

number -> arity 0
constant (e.g. pi) -> arity 0
"+/-" -> arity 1
"+" -> arity 2

Then you just chop off the list as many operands as required --
recursively, of course :-)

Regards,
        Jorg Hohle
Telekom Research Center -- SW-Reliability



Sat, 18 May 2002 03:00:00 GMT  
 RPN

Quote:

>> Ah, but what if the RPN is of the form?

>>        (2 3 + 5 /)
>Then obviously you'll need something external that tells you the arity
>of what you're currently looking at:

>number -> arity 0
>constant (e.g. pi) -> arity 0
>"+/-" -> arity 1
>"+" -> arity 2

>Then you just chop off the list as many operands as required --
>recursively, of course :-)

That was my first thought, and I did write a short and very simple function
that did exactly that. I intended to post it, but then it occured to me that
the arguments don't really have to be in the right order. For instance, you
might have (1 2 3 * +) = 7. A stack based approach would handle it easily,
the list chopping method would croak.

--
- t



Tue, 21 May 2002 03:00:00 GMT  
 RPN

Quote:


> >> Ah, but what if the RPN is of the form?

> >>   (2 3 + 5 /)

> >Then obviously you'll need something external that tells you the arity
> >of what you're currently looking at:

> >number -> arity 0
> >constant (e.g. pi) -> arity 0
> >"+/-" -> arity 1
> >"+" -> arity 2

> >Then you just chop off the list as many operands as required --
> >recursively, of course :-)

> That was my first thought, and I did write a short and very simple function
> that did exactly that. I intended to post it, but then it occured to me that
> the arguments don't really have to be in the right order. For instance, you
> might have (1 2 3 * +) = 7. A stack based approach would handle it easily,
> the list chopping method would croak.

You thought of the list chopping method because you were thinking like
a human and not like a computer.  IOW, you were looking at your
potential data set, in this case

 (1 2 3 * +)

and saw it all at once on the screen.  A computer doesn't see things
in a gestalt form though, it sees them as individual datums, one at a
time.

[(]  [1]  [2]  [3]  [*]  [+]  [)]

If you teach yourself to think like this more often you'll find that
your original solutions are much closer to the optimal way of doing
things on a computer.  This took me a couple of years to notice long,
long ago, but since then the idea of seeing things only one datum at a
time has served me well.

Keep two temporary variables for storage, then pop numbers off the
stack into them.  Then pop an operator off.  If the first two things
you pop aren't numbers then you error (unless you want a sign
operation).  Calculate the result of the operator on the two temp
vars, then store the result in the *second* temp var (order is
important for - and / remember).  Repeat until stack is empty or you
get bored.

I'd write the code for this but I'm in a hurry to get to a meeting...
Sorry.

'james



Tue, 21 May 2002 03:00:00 GMT  
 RPN

Quote:
>> >> Ah, but what if the RPN is of the form?

>> >>       (2 3 + 5 /)
>> >Then obviously you'll need something external that tells you the arity
>> >of what you're currently looking at:

>> >number -> arity 0
>> >constant (e.g. pi) -> arity 0
>> >"+/-" -> arity 1
>> >"+" -> arity 2

>> >Then you just chop off the list as many operands as required --
>> >recursively, of course :-)
>> That was my first thought, and I did write a short and very simple function
>> that did exactly that. I intended to post it, but then it occured to me that
>> the arguments don't really have to be in the right order. For instance, you
>> might have (1 2 3 * +) = 7. A stack based approach would handle it easily,
>> the list chopping method would croak.
>You thought of the list chopping method because you were thinking like
>a human and not like a computer.  IOW, you were looking at your
>potential data set, in this case

> (1 2 3 * +)

>and saw it all at once on the screen.  A computer doesn't see things
>in a gestalt form though, it sees them as individual datums, one at a
>time.

>[(]  [1]  [2]  [3]  [*]  [+]  [)]

>If you teach yourself to think like this more often you'll find that
>your original solutions are much closer to the optimal way of doing
>things on a computer.  This took me a couple of years to notice long,
>long ago, but since then the idea of seeing things only one datum at a
>time has served me well.

I hope this wasn't meant for me? I have been programming for 11 years, and I
think I would know fairly well by now how to reason about how the computer
interprets data.

Quote:
>Keep two temporary variables for storage, then pop numbers off the
>stack into them.  Then pop an operator off.

This won't work for precisely the reason I mentioned. You may not have an
operator immediately following two numbers. You have to go through the list
and push every number on the stack. When you get to an operator you pop the
two last numbers off the stack, apply the operator, and push the result back
on and continue going through the list.

If you want to assume that all operators are binary and that two numbers are
always followed by an operator you can make a quick and dirty solution:

(define (rpn expr)
  (if (null? (cdr expr))
    (car expr)
    (rpn (cons (eval `(,(caddr expr)
                       ,(car expr)
                       ,(cadr expr)))
               (cdddr expr)))
   )
 )

Quote:
> (rpn '(1 2 + 3 + 4 *))
24
> (rpn '(1 2 / 50 *))
25

--
- t


Tue, 21 May 2002 03:00:00 GMT  
 RPN

Quote:
>> Keep two temporary variables for storage, then pop numbers off the
>> stack into them.  Then pop an operator off.  If the first two things
>> you pop aren't numbers then you error (unless you want a sign
>> operation).  Calculate the result of the operator on the two temp
>> vars, then store the result in the *second* temp var (order is
>> important for - and / remember).  Repeat until stack is empty or you
>> get bored.
>This can't possibly work.  Apart from the confused notation (you seem
>to be thinking of the input stream as a stack?), you can have any
>number of non-operators, operators with any arity & so on.

As for operators with any arity, are you sure you would want to allow that?
How would you determine the arity of an operator?

Example: (1 2 3 + -)

Does + take three arguments, and - one, or does + take two and - two?

--
- t



Wed, 22 May 2002 03:00:00 GMT  
 RPN

Quote:
> As for operators with any arity, are you sure you would want to allow that?
> How would you determine the arity of an operator?

The arity of an operator is part of its definition.  So in your case +
and - would be arity 2.

A real stack-machine implementation would probably have the arity of
an operator implicit in its code -- all operators just get handed the
stack and should do whatever pushing and popping they want, so the
code of + would be:

        (push (+ (pop stack) (pop stack)) stack)

I find it convenient to define some syntax on this raw thing, so I can
say (in CL not scheme):

        (define-rpn-operator + 2 #'+) ; 2 is arity

which arranges life so that the + operator calls #'+ with 2 args.
Specifying arity 0 passes the stack to the operator-function.  You
need that for variable-arity things like a typical RPN SUM which the
top of the stack then that many args and sums them:

        1 2 3 3 sum

leaves 6 on the stack.

--tim



Wed, 22 May 2002 03:00:00 GMT  
 
 [ 11 post ] 

 Relevant Pages 

1. ANN: A new RPN Calculator

2. Maximum RPN stack depth.

3. MS now using stack and RPN

4. RPN to Forth Converter

5. Reverse-polish-fot[h]ified Maplism (RPN symbolic math Q)

6. Who invented RPN?

7. Who invented RPN ?

8. Who invented RPN?

9. Atari 8-bit FIG Forth; proper RPN

10. RPN Germanic Languages

11. RPN (???) Germanic Languages

12. Prefix, Infix, RPN

 

 
Powered by phpBB® Forum Software