НА КУХНЕ У СИДОРОВА

урок 13 | Перевозчик | Плюсик

В уроке рассмотрены два приложения.

Первое из них (Перевозчик) — очень простое. Читателю не составит труда самостоятельно разобраться в работе этой программы по ее исходным текстам (они подробно закомментированы).

Второе приложение (Плюсик) — достаточно сложное и объемное. Именно ему в уроке уделено основное место. Автор на примере построения Плюсика показывает весь процесс проектирования и отладки, начиная с составления технического задания, заканчивая мелкими шлифовками готового кода и интерфейса.

урок 14: роботландская мозаика

• Перевозчик
• Плюсик

Перевозчик

Изучение исполнителей в Роботландии начинается с задачи про перевоз волка, козы и капусты через реку. Вот условие этой задачи.

Задача: перевести животных на правый берег.
Козу нельзя оставлять с капустой!
Волка нельзя оставлять с козой!
В лодке, кроме перевозчика, помещается только одно животное или капуста.

Иван написал на JavaScript эту роботландскую программу. Вот что у него получилось.

Этот вариант работает только в Internet Explorer: ./sidorov/river.htm

Этот вариант работает в Internet Explorer и Netscape Navigator: ./sidorov/rivernn.htm

Плюсик

Вторая программа, которая вдохновила Сидорова, была посвящена стековому вычислителю. В Роботландии он называется Плюсиком.

Плюсик — это модель стекового калькулятора. Среда исполнителя состоит из стека и вычислителя.

Стек служит для хранения чисел. Числа помещаются в стек по одному, подобно тому, как кольца детской пирамидки нанизываются на стержень. За один раз взять из стека можно только одно число с вершины числовой пирамиды. Копия числа в стеке не сохраняется, зато становится доступным следующее число, расположенное “ниже” взятого.

система команд Плюсика

ЗАПОМНИ число

СЛОЖИ
ВЫЧТИ
УМНОЖЬ
ДЕЛИ

примеры программ Плюсика

ЗАПОМНИ 125.67
ЗАПОМНИ 82
УМНОЖЬ

ЗАПОМНИ 7253
ЗАПОМНИ 2.356
ЗАПОМНИ 23.78
СЛОЖИ
ВЫЧТИ

алгоритм написания программ для Плюсика

Для преобразования обычного выражения в программу для Плюсика можно просматривать выражение последовательно слева направо, записывая команды ЗАПОМНИ число.

Если после очередной записи команды ЗАПОМНИ выяснится, что над последними двумя числами в стеке можно выполнить арифметическую операцию, то записывается соответствующая команда.

Техническое задание на Плюсика

Верный принципам структурного проектирования, Сидоров начал разработку Плюсика с построения технического задания.

Пусть, решил Сидоров, среда исполнителя будет выглядеть так:

Стек Программа Команда

программирование стека

Программирование Сидоров начал с построения стека. Он описал на JavaScript такой объект:

//-- Файл stack.js --
//-- Начало описания объекта Stack.
// Конструктор
function Stack()
{
 // Свойства.
 this.stack = new Array(); // Массив stack - модель стека.
 this.top   = 0; // Индекс "заверхушки" стека (свободного места
                 // в массиве) или - число элементов в стеке.
 // Основные методы.
 this.Put = _Stack_Put;          // Положить на стек.
 this.Pop = _Stack_Pop;          // Взять со стека.
 // Вспомогательные методы
 this.Cls     = _Stack_Cls;      // Очистка стека.
 this.Element = _Stack_Element;  // Копия элемента в стеке с
                                 // номером i от верхушки.
}
//-- Описание методов объекта.
// Положить элемент на стек.
// Элемент element располагается на свободном месте
// массива, а индекс "заверхушки" наращивается на 1.
function _Stack_Put(element)
{
  this.stack[this.top++] = element;
}
// Взять элемент со стека.
// Если стек не пуст, возвращается верхний элемент,
// а индекс свободного места уменьшается на 1.
// Если стек пуст, возвращается аварийное значение null.
function _Stack_Pop()
{
  var ret = null;
  if(this.top) ret = this.stack[--this.top];
  return ret;
}
// Очистка стека.
function _Stack_Cls()
{
  this.top = 0;
}
// Копия элемента в стеке с номером i от верхушки.
// Если элемента нет, возвращается null.
function _Stack_Element(i)
{
  return (i <= this.top) ? this.stack[this.top - i -1] : null;
}
//-- Конец описания объекта Stack

комментарии кода объекта Stack

1. Стек моделируется при помощи массива stack. Переменная top указывает на свободное место в массиве. Эту переменную можно рассматривать как число элементов в массиве или как указатель на место, которое будет занимать верхушка стека после добавления очередного элемента. В этом смысле top — “заверхушка” стека.
   
   
2. Основные методы объекта Put и Pop реализуют возможные операции над стеком: “положить на стек элемент”, “извлечь из стека элемент”.
   
   
3. Дополнительные методы Cls и Element реализуют “сервисные” функции объекта, которые не имеют отношения к операциям над стеком, как над информационной структурой, но удобны для нашей программистской “кухни”: сброса среды в исходное состояние и отображения стека на экране.

Для отладки объекта, Иван соорудил испытательный стенд ./sidorov/stack.htm.

испытательный стенд для отладки объекта Stack

комментарии к коду отладочного стенда

1. Функции Ini, Put и Pop являются обработчиками события click на кнопках Сброс, В стек и Из стека соответственно. Эти функции сначала выполняют нужную работу над экземпляром stack объекта Stack, а затем вызывают функцию Draw, которая перерисовыва экранное изображение стека.
   
   
2. Функция Put проверяет на “пусто” элемент, который нужно положить на стек. Если элемент — пустая строка — выдается сообщение “Не понимаю”.
   
   
3. Функция Pop проверяет, не пуст ли стек. Если стек пуст, выдается сообщение “Не могу”.
   
   
4. Функция Draw отображает содержимое стека на экране, очищает строку ввода и выводит значение свойства top.

протокол, откатка, накатка

После отладки стека Иван решил написать и отладить поле протокола, откатку и накатку. Фактически он создал в программных кодах всю среду Плюсика. Правда, построенный Плюсик получился очень “ленивый”: все команды он выполняет одинаково — помещает их как текст на свой стек. При этом исполнитель совершенно не задумывается о том, что же написано в этих “командах”.

Следует отметить, что Сидоров поступил очень мудро! Ведь он решил заняться откаткой и накаткой, отладить эти операции, а только затем приступить к программированию кодов, ответственных за выполнение команд Плюсика.

А пока выполнение команды Иван выделил в отдельную функцию ExecuteCom. Эта функция должна получать в качестве аргумента ввод пользователя, а в качестве результата выдавать значение одной из трех переменных:

Заметьте, что Сидоров использует переменные со значениями, которые никогда не меняются в программе. Фактически это — константы. Но специального типа “константа” нет в JavaScript, поэтому приходится константы “замуровывать” в обычные переменные.

Можно, конечно, не заводить переменных, а прямо в нужном месте кода записывать текст “Ok” вместо переменной Ok, “Не понимаю” вместо BadData и “Не могу” вместо CantDo. Но такое программирование не для Сидорова! Представьте, что через некоторое время тексты сообщений нужно будет поменять (изменились, например, условия использования Плюсика или язык его интерфейса). Если константы не занесены в переменные (один раз в начале программы!), то придется искать их употребление по всему исходному тексту. Морока! Да и легко допустить ошибку при такой замене.

Для начала вместо реальной функции ExecuteCom, Иван поставил “заглушку”:

function ExecuteCom(str)
{
  stack.Put(str);
  return Ok;
}

Заглушка просто размещает ввод пользователя на стек и возвращает значение переменной Ok.

протокол

Для поддержки поля протокола Плюсика Сидоров написал такой объект:

//-- Начало описания объекта Program.
// Конструктор.
function Program()
{
  // Свойства.
  this.program = new Array(); // Массив строк протокола.
  this.len     = 0;           // Длина протокола.
  this.maxlen  = 0; // Максимальная длина протокола.
  // Методы.
  this.Add   = _Program_Add;       // Добавить строку.
  this.Undo  = _Program_Undo;      // Откатка.
  this.Redo  = _Program_Redo;      // Накатка.
  this.Cls   = _Program_Cls;       // Сброс протокола.
  this.Element = _Program_Element; // i-ая строка протокола.
}
//-- Описание методов объекта.
// Добавить строку.
function _Program_Add(str)
{
  this.program[this.len++] = str;
  this.maxlen = this.len;
}
// Откатка
function _Program_Undo()
{
  var ret = false;
  if(this.len) {this.len--; ret = true;}
  return ret;
}
// Накатка
function _Program_Redo()
{
  var ret = false;
  if(this.len < this.maxlen) {this.len++; ret = true;}
  return ret;
}
// Сброс протокола
function _Program_Cls()
{
  this.len = this.maxlen = 0;
}
// Возвращается i-строка протокола.
// Если строки нет, возвращается null.
function _Program_Element(i)
{
  var ret = null;
  if(0 <= i && i < this.len) ret = this.program[i];
  return ret;
}
//-- Конец описания объекта Program.

Обратите внимание: значение переменной len совпадает со значением переменной maxlen до тех пор, пока не работает откатка. После откатки len содержит длину протокола с учетом откатки, а maxlen является “упором” для накатки.

откатка

Откатку Иван реализовал при помощи функции Undo:

// Пользователь нажал кнопку "<--"
// program - рабочий экземпляр объекта Program.
// stack   - рабочий экземпляр объекта Stack.
function Undo()
{
  if(program.Undo())
  {
    stack.Cls();
    // Выполнить заново все команды до this.len.
    for(var i=0; i<program.len; i++)
      ExecuteCom(program.Element(i));
    // Отрисовать экран.
    Draw();
  }
}

Алгоритм работы функции Undo:

• Откатка протокола: program.Undo()
• Если откатка протокола выполнена:
  • Сбросить стек: stack.Cls()
  • Выполнить заново все команды протокола:

    for(var i=0; i<program.len; i++) ExecuteCom(program.Element(i));

  • Отрисовать экран: Draw()

накатка

Накатка реализована при помощи функции Redo:

// Пользователь нажал кнопку "-->"
// program - рабочий экземпляр объекта Program.
function Redo()
{
  if(program.Redo())
  {
    // Выполнить команду.
    ExecuteCom(program.Element(program.len-1));
    // Отрисовать экран.
    Draw();
  }
}

Алгоритм накатки:

• Накатка протокола: program.Redo()
• Если накатка протокола выполнена:
  • Выполнить команду, которая появилась в протоколе после накатки:

    ExecuteCom(program.Element(program.len-1));

  • Отрисовать экран: Draw()

выполнение команды пользователя

Для упрощения ввода команд их имена в СКИ (системе команд исполнителя) сокращены до одной буквы: СКИ Плюсика

“Заглушку” ExecuteCom Иван заменил такой функцией:

var DoCommand = new Array(DoSave,DoSub,DoAdd,DoMul,DoDiv);
// Выполнение команды пользователя.
function ExecuteCom(str)
{
  // Анализ ввода пользователя.
  var ret = Parse(str);
  // Переключение на выполнение команды.
  if(ret == Ok) ret = DoCommand[command]();
  return ret;
}

Сначала вызывается функция Parse. Задача этой функции — провести анализ строки, которую ввел пользователь.

Если в строке ошибок нет, функция Parse возвращает значение переменной Ok, если ошибки есть — значение переменной BadData.

В случае удачного анализа функция Parse заносит в глобальные переменные command и number нужные значения. В переменную command — одно из чисел 0, 1, 2, 3, 4, соответствующих номеру команды из СКИ Плюсика (глобальный массив ski). В переменную number — заносит число — параметр команды з.

Если функция Parse вернула значение Ok, вызывается одна из функций:

Реализации этих функций весьма просты. Ниже приводятся соответствующие коды:

// stack - рабочий экземпляр объекта Stack.
// Команда "з".
function DoSave()
{
  stack.Put(number);
  return Ok;
}
// Команда "в"
function DoSub()
{
  var ret= CantDo;
  if(stack.top > 1)
  {
    var a = stack.Pop();
    var b = stack.Pop();
    stack.Put(b-a);
    ret = Ok;
  }
  return ret;
}
// Команда "с"
function DoAdd()
{
  var ret= CantDo;
  if(stack.top > 1)
  {
    var a = stack.Pop();
    var b = stack.Pop();
    // Используем функцию parseFloat
    // чтобы работала операция сложения
    // чисел, а не конкатенация двух строк.
    stack.Put(parseFloat(b)+parseFloat(a));
    ret= Ok;
  }
  return ret;
}
// Команда "у"
function DoMul()
{
  var ret= CantDo;
  if(stack.top > 1)
  {
    var a = stack.Pop();
    var b = stack.Pop();
    stack.Put(b*a);
    ret= Ok;
  }
  return ret;
}
// Команда "д"
function DoDiv()
{
  var ret= CantDo;
  if(stack.top > 1)
  {
    var a = stack.Pop();
    if(a == 0) stack.Put(a);
    else
    {
      var b = stack.Pop();
      stack.Put(b/a);
      ret= Ok;
    }
  }
  return ret;
}

анализатор Parse

Функция Parse проверяет строку, введенную пользователем, на правильность. Проверка выполняется в процессе “расщепления” строки на составляющие: “имя команды” и возможный параметр (число — для команды з). Вот код этой функции:

// Анализ ввода пользователя.
function Parse(str)
{
  var ret = Ok;               // Возвращаемое значение.
  var words = new Words(str); // "Извлекатель слов" из строки.
  var word = "";              // Очередное слово из str.
  // Первое слово из str - имя команды.
  word = words.GetWord();
  if(word == "") ret = BadData;
  else
  {
    // Определим имя команды.
    for(command=0; command<ski.length; command++)
      if(word.toLowerCase() == ski[command]) break;
    if(command >= ski.length) ret = BadData;
    else
    {
      // Если это первая команда ("з"),
      // то должен быть параметр - число.
      if(command==0)
      {
        word = words.GetWord();
        if(!word || isNaN(word)) ret = BadData;
        else number = word;
      }
      if(ret == Ok)
      {
        // За командой не должно быть ничего лишнего.
        word = words.GetWord();
        if(word != "") ret = BadData;
      }
    }
  }
  return ret;
}

Функция Parse использует в своей работе экземпляр объекта Words, который Сидоров придумал и написал специально для разбора строки на элементы (слова), отделенные друг от друга пробелами.

“Разбираемая” на составные части строка передается экземпляру объекта при его создании как аргумент конструктора. Единственный метод объекта GetWord позволяет при каждом новом запуске возвращать очередное слово строки (последовательность символов, не содержащую пробелы).

Если слов в строке больше нет, метод GetWord возвращает пустую строку.

Коды объекта Words приводятся ниже:

//-- Начало описания объекта Words.
// Объект позволяет извлекать из переданной ему строки
// слова, то есть последовательности символов от пробела
// (начала строки) до пробела (конца строки).
// Конструктор
// Аргумент конструктора - строка.
function Words(str)
{
  // Свойства.
  this.str   = str; // Анализируемая строка.
  this.begin = 0;   // Индекс начала слова в строке.
  this.end   = 0;   // Индекс "законца" слова в строке.
  // Методы
  this.GetWord = _Words_GetWord // Очередное слово строки.
}
//-- Описание методов объекта
// Получить очередное слово строки.
function _Words_GetWord()
{
  var word="";
  // Началом разбора строки является
  // предыдущий "законец" слова.
  // Пропустим первые пробелы.
  for(this.begin=this.end;
      this.begin<this.str.length; this.begin++)
    if(this.str.charAt(this.begin) != " ") break;
  // Если остаток строки не пуст.
  if(this.begin < this.str.length)
  {
    // Найдем первый пробел за концом
    // слова или конец строки.
    for(this.end=this.begin+1; this.end <
                            this.str.length; this.end++)
      if(this.str.charAt(this.end) == " ") break;
    // Копируем в word найденное слово.
    word = this.str.substring(this.begin, this.end);
  }
  // Возвращаем найденное слово.
  return word;
}
//-- Конец описания объекта Words

Анализатор Parse можно упростить, если использовать для “расщепления” строки на “слова” метод split объекта String и механизм регулярных выражений JavaScript:

// Анализ ввода пользователя.
function Parse(str)
{
  var ret = Ok;
  // Преобразование строки в массив.
  // Строка расщепляется на слова
  // (разделитель слов - цепочка пробелов),
  // которые заносятся в массив setwords.
  var setwords = str.split(/ +/);

  // Первое слово из str - имя команды.
  if(!setwords.length || setwords[0] == "") ret = BadData;
  else
  {
    // Определим имя команды.
    for(command=0; command<ski.length; command++)
      if(setwords[0].toLowerCase() == ski[command]) break;
    if(command >= ski.length) ret = BadData;
    else
    {
      // Если это первая команда ("з"),
      // то должен быть параметр - число.
      if(!command)
      {
        if(setwords.length!=2||isNaN(setwords[1])) ret=BadData;
        else number = setwords[1];
      }
      else
      {
        if(setwords.length != 1) ret = BadData;
      }
    }
  }
  return ret;
}

В этом варианте функции Parse объект Words уже не нужен.

Регулярное выражение / +/ задает в качестве разделителя элементов для функции split один или несколько пробелов (свойство метасимвола “+”). Вариант str.split(" ") в качестве замены str.split(/ +/) не годится — в нем разделителем является одиночный пробел, что приведет к нежелательному для нас преобразованию в массив, например, такой строки: "з 1". Первый элемент массива будет содержать букву “з”, а второй — пустую строку.

Подробное рассмотрение регулярных выражений выходит за рамки этой книги.

Плюсик работает!

Ленивый Иван нагрузил клавиши Enter и F1 в строке ввода функциями экранных кнопок Вып и ?, а аккорды Ctrl+Z и Ctrl+Y закрепил за операциями “откатка” и “накатка”. Теперь стало возможно работать с Плюсиком, отложив мышку в сторону.

Иван провел тщательное тестирование своей программы, после чего пошел пить чай с сухариками — программирование всегда вызывало у него жажду. И он не давал себе засохнуть!

Это Плюсик: ./sidorov/plus.htm