воскресенье, 25 марта 2012 г.

Расстановка знаков в арифметическом выражении

[Все темы по размещениям]

Задача: 155. Дешифровка выражения(contester.tsure.ru) [Условие]
Предварительные темы:    [Генерация всех размещений с повторениями рекурсивным способом]
                         [Генерация следующего размещения с повторениями]
                         [Подсчет арифметического выражения(обратная польская нотация)]
Дополнительная практика: Задачи для подсчета арифметического выражения (см. занятие 4 - архив)

Итак, имеется корректное арифметическое выражение вида (9?8)?(0?3)?2=-25, вместо знаков ? необходимо поставить одну из 4 операций +,-,*,/ так, чтобы выражение стало правильным. Если такого сделать нельзя, то нужно вывести “No solution.”. Для удобства гарантируется, что в левой части выражения все числа являются цифрами и отсутствуют унарные знаки. В правой же части может быть любое число по модулю не превышающее 1015.

Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10
Алфавит знаков содержит четыре элемент: {+,-,/,*}.
Количество позиций в размещении(количество знаков ? в выражении): 2
Общее количество размещений: 42=16

Сгенерируем все размещения с повторениями рекурсивным способом и получим все возможные комбинации исходного арифметического выражения:

  1. 2+(3+4)=9
  2. 2+(3-4)=1
  3. 2+(3*4)=14
  4. 2+(3/4)=2
  5. 2-(3+4)=-5
  6. 2-(3-4)=3
  7. 2-(3*4)=-10
  8. 2-(3/4)=2
  9. 2*(3+4)=14
  10. 2*(3-4)=-2
  11. 2*(3*4)=24
  12. 2*(3/4)=0
  13. 2/(3+4)=0
  14. 2/(3-4)=-2
  15. 2/(3*4)=0
  16. 2/(3/4)=NAN
* This source code was highlighted with Source Code Highlighter.

Значение NAN обозначает, что в выражении присутствует деление на ноль. Сам подсчет будем делать с помощью перевода в обратную польскую запись, подсчетом значения на лету.
Подсчет значения на лету можно сделать так:

  1. string opers = "+-*/";
  2. bool calc(INT &f, INT &s, char op, INT &res) {
  3.   switch(op) {
  4.     case '+' : res = f + s; return true;
  5.     case '-' : res = f - s; return true;
  6.     case '*' : res = f * s; return true;
  7.     case '/' : if (s != 0) {
  8.             res = f / s;
  9.             return true;
  10.           }
  11.           return false;
  12.   }
  13.   return false;
  14. }
  15. bool calc_last (stack<INT> &val, stack<char> &oper) {
  16.   INT s = val.top(); val.pop();
  17.   INT f = val.top(); val.pop();
  18.   INT r = -1;
  19.   if (calc(f,s,oper.top(),r)) {
  20.     val.push(r);
  21.     oper.pop();
  22.     return true;
  23.   }
  24.   return false;
  25. }
  26. int prior(char op) {
  27.   switch(op) {
  28.     case '+':
  29.     case '-': return 0;
  30.     case '*':
  31.     case '/': return 1;
  32.   }
  33.   return -1;
  34. }
  35. bool is_num(char c) {
  36.   return '0' <= c && c <= '9';
  37. }
  38. bool calc(const string &expr, INT &res) {
  39.   stack<INT> val;
  40.   stack<char> oper;
  41.   for (int i=0;i<expr.size();++i) {
  42.     if (is_num(expr[i]))
  43.       val.push(expr[i] - '0');
  44.     else if (expr[i] =='(')
  45.       oper.push(expr[i]);
  46.     else if (expr[i] == ')') {
  47.       while (oper.top() != '(') {
  48.         if (!calc_last(val, oper))
  49.           return false;
  50.       }
  51.       oper.pop();
  52.     }
  53.     else { // expr[i] - операция
  54.       while (!oper.empty()) {
  55.         if (prior(oper.top()) >= prior(expr[i])) {
  56.           if (!calc_last(val, oper))
  57.             return false;
  58.         }
  59.         else break;
  60.       }
  61.       oper.push(expr[i]);
  62.     }
  63.   }
  64.   while (!oper.empty()) {
  65.     if (!calc_last(val,oper))
  66.       return false;
  67.   }
  68.   res = val.top();
  69.   return true;
  70. }
* This source code was highlighted with Source Code Highlighter.

Исходный код: здесь

Отправляем в систему проверки на contester.tsure.ru и получаем вердикт: TLE9. =))
В худшем случае количество операций равно 10, значит общее количество генерируемых размещений будет 410=1048576. Получается, что приведенный фрагмент кода подсчета значения выражения на лету будет запускаться более 1 млн. раз. Т.к. в данной задаче нам придется генерировать все размещения, то естественным путем оптимизации исходного решения – минимизировать количество построений обратной польской записи.
Рассмотрим несколько выражений и их обратные польские записи.

Номер     Выражение           Обратная польская запись
1         5*2+3-(7+2)/2       5 2 * 3 + 7 2 + 2 / -
2         5/2-3+(7-2)*2       5 2 / 3 – 7 2 – 2 * +
 
3         5+2*3/(7*2)-2       5 2 3 * 7 2 * / + 2 -
4         5-2/3*(7/2)+2       5 2 3 / 7 2 / * – 2 +

Подсчет выражения по обратной польской записи осуществляется за 1 проход.
Т.к. соответствующие операции в выражениях 1 и 2 имеют одинаковые приоритеты, то для них получаются две обратные польские записи, которые можно считать подобными. Тоже самое можно наблюдать для выражений 3 и 4.
Две обратные польские записи назовем подобными, если соответствующие операции имеют одинаковый приоритет.
Все операции можно разбить на две группы:
1. С меньшим приоритетом(0) : + , -
2. С большим приоритетом(1) : * , /

Поэтому изначально можно сгенерировать до 210=1024 размещений из приоритетов [0 и 1]. При этом, если на место операции выпадает 0 в размещении это говорит о том, что на ее место будут последовательно поставлены операции с нулевым приоритетом, т.е + или –.
Для выражений с одинаковыми размещениями приоритетов получаются подобные обратные польские записи.

Рассмотрим выражение:              5?2?3?(7?2)?2
Текущее размещение из приоритетов: {1, 0, 0, 0, 1} 
Обратная польская запись:          5 2 [1] 3 [0] 7 2 [0] 2 [1] [0], где [x] – операция с приоритетом x
Как можно заметить, текущая обратная польская запись соответствует 1 и 2 выражению из таблицы.

Далее подумаем, как можно перебрать конкретные знаки, с уже расставленными приоритетами операций.
Для текущего размещения R можно поставить в соответствие два размещения F и S.
При этом длина F равна количеству нулей в размещении R, а длина S – количеству единиц.
Элементы множества F будут состоять из операций с нулевым приоритетом, а S – из элементом с единичным приоритетом.

Номер   Выражение        R              F           S
1       5*2+3-(7+2)/2    {1,0,0,0,1}    {+,-,+}     {*,/}
2       5/2-3+(7-2)*2    {1,0,0,0,1}    {-,+,-}     {/,*}
3       5+2*3/(7*2)-2    {0,1,1,1,0}    {+,-}       {*,/,*}
4       5-2/3*(7/2)+2    {0,1,1,1,0}    {-,+}       {/,*,/}

Все вышеизложенную идею можно описать так. При этом получается, что в худшем случае придется генерировать 210=1024 обратных польских записей вместо 410=1048576. Благодаря этим преобразованием последнее решение уложилось в 1.5 секунды на сервере проверки.

В целях рефакторинга второй реализации можно скрестить генерацию размещений R и {F,S}.

Комментариев нет:

Отправить комментарий