На сайте ведутся работы 11. "Стоп, дети" и не только... | ТРИЗ - РТВ - ТРТЛ | Бизнес-форум TRIZ-RI
9737
СОГЛАСЕН С ОБРАБОТКОЙ ЛИЧНЫХ ДАННЫХ
Все категории » ТРИЗ - РТВ - ТРТЛ » С.В. Сычев, К.А. Лебедев "Не только про калькулятор"

11. "Стоп, дети" и не только...

Ваши данные (просмотреть)
в избранные темы
Политика конфиденциальности

Обсуждения-аналоги

Скрыть / Показать Сортировать по дате
Создать аналогичное обсуждение...

Авторы

Скрыть / Показать
2010-01-22 15:07:20
Сычев С.В., Лебедев К.А. » Всем

11. "СТОП, ДЕТИ,.." И НЕ ТОЛЬКО...

 

И, наконец, рассмотрим функцию BreakNow. Задача этой функции - определить условие выхода из цикла. Поскольку эта функция используется в паре с функцией NeedPop, то, скорее всего, она должна работать с ней синхронно. Например, когда NeedPop возвращает true, BreakNow должна возвращать false. И, наоборот, когда NeedPop возвращает false, BreakNow должна возвращать true.


В самом деле, это достаточно логично. Если функция NeedPop возвращает true, то токен будет вытолкнут из стека. Это означает, что на вершине стека окажется другой токен. Вероятно, его нужно будет сравнить с текущим токеном. А для этого не нужно выходить из цикла. Т.е. BreakNow должна вернуть false.


Исходя из этого, можно сделать вывод, что реализация функции BreakNow будет практически идентичной реализации функции NeedPop.


В идеале, это должен быть один и тот же код, выполняющий две функции. (Вновь вспомним требования к идеальной программе).

Посмотрим, возможно ли это?


См. код на языке C++:


bool BreakNow(const TToken & rToken1, const TToken & rToken2)
{
    assert(rToken1.GetType() < eTokenTypeCount);
    assert(rToken2.GetType() < eTokenTypeCount);

   
    return g_iPriorities[rToken1.GetType()][0] <=
g_iPriorities[rToken2.GetType()][1];
}


Отличие приведённой реализации от правильной должно заключаться только в одном: правильная реализация функции BreakNow должна по-другому (особым образом) обрабатывать ситуацию, когда на вершине стека находится открывающая скобка, а текущий токен - это скобка закрывающая.


Функция NeedPop в этой ситуации должна дать команду "вытолкнуть токен из стека". Это означает, что приоритет токена "открывающая скобка" должен быть больше приоритета "закрывающей скобки".


А вот функция BreakNow должна поступить по-другому. Она должна дать команду на выход из цикла. Это означает, что приоритет токена "открывающая скобка" (в той же ситуации) должен совпадать с приоритетом токена "закрывающая скобка".


Если мы хотим использовать (а мы хотим) один и тот же код для выполнения двух функций, мы должны решить Противоречие 5:


Должно быть так:


 КтоПриоритет
 Конец последовательности INT_MIN
 Закрывающая скобка- 1
 Открывающая скобка0
+1
-2
*3
/4
 ОперандINT_MAX

И должно быть так:


 КтоПриоритет
 Конец последовательности INT_MIN
 Закрывающая скобка 0
 Открывающая скобка 0
+1
-2
*3
/4
 ОперандINT_MAX

Единственное отличие этих таблиц (от таблиц для функции NeedPop) заключается в приоритете для закрывающей скобки (см. выделенное).


Перейдем к следующей надсистеме. Вероятно, надо поступить вот так:


Кто

Делаю "NeedPop"Делаю "BreakNow"
Приоритет
(для 1-го параметра)		Приоритет
(для 2-го параметра)		Приоритет
(для 1-го параметра)		Приоритет
 (для 2-го параметра)
 Конец последовательности INT_MININT_MININT_MININT_MIN
 Закрывающая скобка- 1- 100
+1111
-2222
*3333
/4444
 Открывающая скобка0505
 ОперандINT_MAXINT_MAXINT_MAXINT_MAX

В коде на языке C++ решение будет выглядеть:


int g_iPriorities[eTokenTypeCount][4] = // Учитываем приоритеты
{

{INT_MAX,INT_MAX,INT_MAX,INT_MAX},// приоритет операнда
{1,1,1,1},// приоритет сложения
{2,2,2,2},// приоритет вычитания
{ 3,3,3,3},// приоритет умножения
{4,4,4,4},// приоритет деления
{0,5,0,5},// приоритет открывающей скобки
{-1,-1,0,0},// приоритет закрывающей скобки
{ INT_MIN, INT_MIN, INT_MIN, INT_MIN}// приоритет конца последовательности

};


bool NeedPop(const TToken & rToken1, const TToken & rToken2)
{
      assert(rToken1.GetType() < eTokenTypeCount);
      assert(rToken2.GetType() < eTokenTypeCount);

      return g_iPriorities[rToken1.GetType()][0] >
g_iPriorities[rToken2.GetType()][1];
}

bool BreakNow(const TToken & rToken1, const TToken & rToken2)
{
      assert(rToken1.GetType() < eTokenTypeCount);
      assert(rToken2.GetType() < eTokenTypeCount);

      return g_iPriorities[rToken1.GetType()][2] <=
g_iPriorities[rToken2.GetType()][3];
}

Далее...
[Нет ответов на это сообщение]


Яндекс.Метрика