Стековый калькулятор

Предыстория

Программа должна выполнять вычисления в соответствии с принятой в стековых калькуляторах (см. например, МК-52) моделью, хотя и существенно упрощенной. Работа данных калькуляторов основана на постфиксной записи выражений. Выпуск подобных калькуляторов продолжается до сих пор (в основном, научные программируемые калькуляторы), первым был "FRIDEN 130" (США, 1964, кроме того - первый транзисторный). Для справки см. статью в Википедии.

Операции стекового калькулятора

Ниже приведены операции, которые предлагается реализовать в стековом калькуляторе.
* - отрезок стека, содержание которого не важно, а иногда (кто догадается, когда - тому наградой знание) - умножение.
? - одиночный элемент, значение которого не важно.
Серым выделены изображения состояния стека.

Арифметические

Бинарные, где ψ - умножение, деление, сложение и вычитание

*, /, +, -
 *
 x
 y
 ψ
 *
 x ψ y

Унарные, φ - унарный минус, квадратный корень

u-, sqrt
 *
 x
 φ
 *
 φ x

Операции со стеком

Число - просто положить число на вершину стека
 *
 3.14159
 *
 3.14159
nop - снять с вершины стека элемент, не выполняя никаких действий
 *
 x
 nop
 *

dup - продублировать вершину стека
 *
 x
 dup
 *
 x
 x
copy - с одинм доп. параметром - скопировать i - й от вершины элемент стека (у вершины индекс 0) на вершину
 a
 b
 c
 1
 a
 b
 c
 1
 copy
 a
 b
 c
 b
exch - с одинм доп. параметром - поменять местами i - й от вершины элемент стека (у вершины индекс 0) с вершиной
 a
 b
 c
 1
 a
 b
 c
 1
 exch
 a
 c
 b
Пример
-sqrt(x2-y2)
Читать построчно слева направо.
 x
 y
 dup x
 y
 y
 * x
 y*y
 1 x
 y*y
 1
 exch y*y
 x
 dup y*y
 x
 x
 *
 y*y
 x*x
 -  y*y-x*x u- x*x-y*y sqrt sqrt(x*x-y*y) u- -sqrt(x*x-y*y)
 

Реализация калькулятора

Этот раздел содержит требования к программной реализации калькулятора и готовые фрагменты кода.

Требования

  • Калькулятор должен читать из файла или стандартного потока ввода (на Ваш выбор) числа и инструкции.
  • Интерпретация входных данных:
    • при подаче на вход операции (например +, sqrt, u-) она должна выполняться;
    • при подаче на вход числа оно должно помещаться в стек;
    • при подаче в качестве инструкции пустой строки или по достижении конца потока (EOF) калькулятор должен заканчивать работу.
  • После выполнения очередной инструкции калькулятор должен выдавать в стандартный поток вывода состояние стека.

Готовый код

В приложенном к странице архиве лежат исходные коды калькулятора, в которых тела функций намеренно оставлены пустыми. Вам предстоит их восстановить. Кроме того, в архиве лежит файл test.txt, который содержит приведенный выше пример (-sqrt(x2-y2)) для x=5 и y=4, в итоге должен получиться стек, содержащий -3.

Пользователям Windows

Переводы строк в файлах сделаны в формате Un*x ("\n", а не "\r\n", как в DOS и Windows), пользователи Windows могут проигнорировать появляющиеся в связи с этим сообщения текстовых редакторов, вменяемые редакторы (GVim, Far Manager, Visual Studio и т.д., главное, чтобы не "Блокнот") будут работать нормально.
Архив в формате .tar.bz2. Тем, кому вообще не известно, что это такое, следует прочесть статьи про tar и bzip2. Можете воспользоваться любым архиватором, поддерживающим этот формат, например, 7-zip (бесплатный, открытый) или WinRar (закрытый, сейчас стоит 29 долларов США).
ċ
stackcalc.tar.bz2
(1k)
Dmitry Luciv,
6 дек. 2008 г., 7:51
Comments