9737
@ Подписаться
Сотни бизнес-методик. Тысячи кейсов. Обновления.

сегодня 13841 Подписчиков


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

Скрыть / Показать Сортировать по дате
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[] (приоритеты токенов).


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


Далее...

Уважаемые Коллеги!

Если Вам нравится наш Форум, Вы можете поддержать его, отправив любую сумму (тогда выберите опцию "Спасибо за Форум").

Вы также можете поддержать конкретное обсуждение и получить гарантированный ответ от наших специалистов (тогда выберите опцию "Прошу эксперта ответить в этой теме").
Задайте Ваш вопрос здесь.

Большое Спасибо!


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