Обратный польский калькулятор / RPN Calculator

Дисклеймер. Хотелось бы поделиться с людьми, которые не особо знают английский, задачками с довольно интересного сайта Programming Praxis. Готовых переводов задач я не нашёл, а потому буду потихоньку сам их тут выкладывать. Задачки простые, но для того, чтобы не терять навыки программирования — самое то.

Programming Praxis, 19.02.2009

Реализовать обратный польский калькулятор, принимающий выражения вида «19 2.14 + 4.5 2 4.3 / - *», которое обычно вычисляется как «(19 + 2.14) * (4.5 - 2 / 4.3)» и соответствует 85.2974. Программа должна читать выражение со стандартного входа и выводить вершину стека с символом конца строки в стандартный вывод. Программа должна сохранять состояние стека операндов между выражениями.


Решение.
Единственная сложность заключается в обработке новой строки, которая в Scheme трактуется как пробел. Функция (op token) преобразует знак, из символа, полученного со входа, в оператор, который может быть использован для вычислений. Формат первой строки программы специфичен для Chez Scheme, но большинство реализаций Scheme предоставляют что-то подобное.

#! /usr/bin/scheme –script
(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))))))

Моё решение.

#!/usr/bin/env python
#-*- coding:utf-8 -*-

from sys import stdin, stdout

def calc():
    stack = []
    result = None
    while True:
        line = yield result
        for token in line.split():
            try:
                number = float(token)
                stack[:0] = [number]
                result = number
            except ValueError:
                try:
                    result = {
                        '+': lambda x, y: x + y,
                        '-': lambda x, y: x - y,
                        '*': lambda x, y: x * y,
                        '/': lambda x, y: x / y
                    }[token](stack[1], stack[0])
                    stack[0:2] = [result]
                except IndexError:
                    raise ValueError, 'Stack is empty'
                except KeyError:
                    raise ValueError, 'Unknown operation'
c = calc()
c.next()

for line in stdin.xreadlines():
    print >> stdout, c.send(line)

Тут есть несколько необычных для новичка моментов.

line = yield result

— это «вывернутый наизнанку» вызов функции, который позволяет разбить цикл обработки на две части: работу со стеком и получение строк со стандартного ввода. Команда yield возвращает значение подобно return, но функция при этом не завершается и будет продолжена при вызове метода send снаружи. причём, аргумент send будет передан через yield внутрь функции. Звучит запутанно, но генераторы — это действительно очень мощная и гибкая штука.

Другая необычность — использование индексирования словаря. Это позволяет ввести конструкцию, аналогичную, например, switch в C, без использования if—elif. Так код выглядит чище, хотя, конечно, тратятся ресурсы на создание анонимного словаря и поиск ключа в нём.

Странные индексы списка stack с двоеточиями — это сечения (slices). Тоже довольно удобная штука. Они есть также в MatLab и Fortran, где без них программирование заметно усложнилось бы.