This exercise comes from programming praxis.

I have written a normal arithmetic expression calculator in C before. It converts normal infix notation to a reversed polish notation, and then calculate its value.
You can find it here if you’re interested in C.

As I become more and more familiar with Scheme and Haskell, I decide to take all these exercise in Scheme, Haskell, or Python. When I say Scheme, it means a specific implementation: Racket.
My initial thought of solving this problem would be simulating those operations in the C code above.
As a functional programming language, Scheme has some sort of “pure” features which make it a little difficult to implement a real world stack. But thanks to Racket’s “mutable struct” type, it can be done effortlessly.

 
#lang racket
; Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3 / - *  
; which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds with 85.2974.  
; The program should read expressions from standard input and print the top of the stack  
; to standard output when a newline is encountered.  
; The program should retain the state of the operand stack between expressions. 
 
; a stack is either empty 
; or a (make-stack head tail) struct  
; where head is any/c and tail is a stack 
(define-struct stack (head tail) #:mutable)
 
; push : any/c stack -> stack 
; push consumes a any/c value and a stack, set stack's head to the new value 
; and set stack's tail to the original stack 
(define (push s st) 
  (define cur (make-stack (stack-head st) (stack-tail st)))
  (set-stack-tail! st cur)
  (set-stack-head! st s)
  st)
 
; pop : list -> any/c 
; pop consumes a stack, return its head and remove that head from the stack. 
; making the orginal stack's tail to be the new stack 
(define (pop st)
  (cond 
    [(empty? st) (error "empty stack")]
    [else (let ((next (stack-tail st))
                (curr (stack-head st))) 
            (cond [(empty? curr) (error "empty stack")]
                  [(empty? next)
                   (and (set-stack-tail! st empty) (set-stack-head! st empty))]
                  [else
                   (and (set-stack-tail! st (stack-tail next))
                        (set-stack-head! st (stack-head next)))])
            curr)]))
  
; rpn-cal : string stack port -> number 
; rpn-cal consumes a string, a stack and a port 
; it reads a reversed polish notation (aka RPN) arithmetic expression 
; from the port, calculate and return the expression's value 
(define (rpn-cal operand st input-port)
  (define char (read-char input-port))
  ; handle (open-input-string "1 2 +") as port
  (cond [(eof-object? char) (pop st)]
        ; handle (current-input-port)
        [else 
         (define s (string char))
         (cond 
           [(string=? "\n" s) (string->number operand)]
           [(string=? " " s) (rpn-cal "" (push (string->number operand) st) input-port)]
           [(string=? "+" s) (rpn-cal (number->string (+ (pop st) (pop st))) st input-port)]
           [(string=? "-" s) (let ((a (pop st))
                                   (b (pop st)))
                               (rpn-cal (number->string (- b a)) st input-port))]
           [(string=? "*" s) (rpn-cal (number->string (* (pop st) (pop st))) st input-port)]
           [(string=? "/" s) (let ((a (pop st))
                                   (b (pop st)))
                               (rpn-cal (number->string (/ b a)) st input-port))]
           [else (rpn-cal (string-append operand s) st input-port)])]))
 
; test 
(rpn-cal "" (make-stack empty empty) (current-input-port))
 

The process of maintain a custom stack makes code redundant and ugly. Let’s see the solution of programmingpraxis’s editor:

 
#lang racket
(define (next)
  (cond ((eof-object? (peek-char)) (exit))
        ((char=? (peek-char) #\space) (read-char) (next))
        ((char=? (peek-char) #\newline) (read-char) 'nl)
        (else (read))))
 
(define (op token) (case token ((+) +) ((-) -) ((*) *) ((/) /)))
 
(let rpn ((token (next)) (stack '()))
    (cond ((eq? 'nl token) (display (car stack)) (newline) (rpn (next) (cdr stack)))
          ((number? token) (rpn (next) (cons token stack)))
          (else (rpn (next) (cons ((op token) (cadr stack) (car stack)) (cddr stack))))))

You can use DrRacket’s debugger to clearly see the above code’s process.

Lesson 1: Always use built-in list and operator when possible;
Lesson 2: Scheme’s applicative-order evaluation can help you write combined functions (like (next) in the above code).

About these ads