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)
; 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)
    [(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))]
                   (and (set-stack-tail! st (stack-tail next))
                        (set-stack-head! st (stack-head next)))])
; 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)
         (define s (string char))
           [(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).


I have switched from slackware to arch recently. The installation process is handy for me. But when I’m using it, problems come:

The first issue is the X window.When I typed startx… arch doesn’t response to my keyboard or mouse any more. All I can do is hold down the power button doing a force power off… How can that be happen? I googled, but no correct answer given. Then I checked the X.log. Aha, seems like the keyboard and mouse driver is missing… Google again, problem was solved by

pacman -S xf86-input-keyboard xf86-input-mouse

truth be told, I really hate this way arch handles X packages. If I’m going to install X, how can you left keyboard and mouse driver apart, and let me get stuck when I’m using X? If I’m a newbie or a little impatient, I’ll certainly give up.

The second issue is getting ibus to work. I have used ibus-pinyin in Fedora, it works like a charm. I really appreciate Huang Peng’s work on that.(Note that in ubuntu 9.10, the default ibus pinyin input method is not ibus-pinyin, and that give ibus a bad name when used by newbies. I don’t know who made this package, It seems like ubuntu ruined everything in 9.10.)
As I choose English locale for desktop, getting Chinese input method to work needs some tricky hand crafts. After installing ibus and ibus-pinyin, it failed to start as expect. I changed LC_CTYPE to zh_CN.UTF-8, then ibus works now, but its icons and language panel do not display.

What’s wrong? It anoyed me two days when I finally decide to kill the ibus-daemon and start it seperately—It works fine after that. I recheck the process: ibus-daemon was initially started with a –xim option, seems like that’s why it can not work properly. I don’t know what’s wrong with the xim option, by fixing it in /etc/xdg/autostart/ibus.desktop seems OK(that is, just ibus-daemon, without the –xim option).

The third issue is ibus doesn’t work in emacs23. And I’m fixing it right now. I have tried to set the locale to zh_CN before invoking emacs, but failed unexpectly. It seems like ibus can’t correctly detect the emacs window. But I’ve no idea how to solve it right now. However, it doesn’t matter much.

I’ve learned a lot by solving issues like these since I began to use Linux.
But now I began to wonder if that’s the right way of playing with computers. Too much time was spend, but very few wealth was created.
Computers are just tools. What makes a great tools depends on how good work can be done with it, not customizing.

I’m feeling a little disappointing on arch.