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

14. Проверка на "максимум потока"

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

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

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

Авторы

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

14. ПРОВЕРКА НА "МАКСИМУМ ПОТОКА"

Проверим решение на "прочность", сделаем поток требований максимальным и разнообразным. Предположим, в калькулятор нужно добавить поддержку различных функций: sin(x), cos(x), ln(x) и т.д.  Изменится ли код преобразования в ПОЛИЗ?


В польской инверсной записи все функции записываются в следующем формате: "аргументы  функция". Т.е.,

  • sin(x) будет записан: x sin,
  • cos(x) будет записан: x cos,
  • а натуральный логарифм ln(x): x ln
  • и т.д. ...

Если функция имеет несколько аргументов, то сначала записываются все её аргументы, а затем - название функции.


Например, функция pow (x, n) будет записана: x n pow

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


enum TTokenType //Справочник типов токенов
 
{
  eTokenOperand = 0,     // операнд
  eTokenPlus,            // операция сложение
  eTokenMinus,           // операция вычитание
  eTokenMultiply,        // операция умножение
  eTokenDivide,          // операция деление
  eTokenOpeningBracket,  // открывающая скобка
  eTokenClosingBracket,  // закрывающая скобка
  eTokenEndOfSequence,   // конец последовательности
  eTokenFunction,        // функция
  eTokenDelimiter,       // разделитель
  eTokenTypeCount        // количество значений токенов
};


Чтобы функция WhereToPut корректно обрабатывала "функцию" и "запятую", нам нужно расширить таблицу g_TokenPlaces[]:

int g_TokenPlaces[eTokenTypeCount] //Справочник "адресов" (куда токены направляются)
 
{
 eOutputSequence,   // операнд помещается в выходную последовательность
 eOperationStack,   // плюс помещается в стек
 eOperationStack,   // минус помещается в стек
 eOperationStack,   // умножение помещается в стек
 eOperationStack,   // деление помещается в стек
 eOperationStack,   // открывающая скобка помещаетсЯ в стек
 eNowhere,          // закрывающая скобка никуда не помещается
 eNowhere,          // конец последовательности никуда не помещается
 eOperationStack,   // функция помещается в стек
 eNowhere           // запятая никуда не помещается
};
    


Функция WhereToPut, определяющая, куда поместить токен, никак не меняется.

int WhereToPut(const TToken & rToken)

{

assert(rToken.GetType() < eTokenTypeCount);

return g_TokenPlaces[rToken.GetType()];

}


Новым типам токенов ("функции" и "запятой") нужно добавить приоритеты. И, соответственно, зарегистрировать их в таблице g_iPriorities[].

int g_iPriorities[eTokenTypeCount][eSituationCount] = //Cправочник приоритетов

{

{

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,6,0,6},  // приоритет открывающей скобки

{

-1,-1,0,0},  // приоритет закрывающей скобки

{

INT_MIN,INT_MIN,INT_MIN,INT_MIN},  // приоритет конца последовательности

{

5,5,5,5},  // приоритет функции

{

INT_MAX,INT_MAX,INT_MAX,INT_MAX}  // приоритет разделителя

};

При этом, количество столбцов в таблице не поменяется. Не поменяется и ключевая функция Pop_N_Break:


bool Pop_N_Break(const int x, const TToken & rToken1, const TToken & rToken2)

{

assert(rToken1.GetType() < eTokenTypeCount);

assert(rToken2.GetType() < eTokenTypeCount);

return g_iPriorities[rToken1.GetType()][х] >

g_iPriorities[rToken2.GetType()][x + 1];
}


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


А для функции назначим приоритет, выше, чем у любой из операций, но ниже, чем у открывающей скобки.


Подведём итоги. Новые сущности, которые теперь надо тоже поддерживать, просто зарегистрированы в трех таблицах:

1) в таблице TTokenType (тип токена);

2) в таблице g_TokenPlaces[] (местоположения токенов);

3) в таблице g_iPriorities[] (приоритеты токенов).


Сам код алгоритма преобразования выражения из инфиксной нотации в выражение в формате ПОЛИЗ не изменился.

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


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