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

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

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

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

Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10
Алфавит знаков содержит четыре элемент: {+,-,/,*}.
Количество позиций в размещении(количество знаков ? в выражении): 2
Общее количество размещений: 4²=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, значит общее количество генерируемых размещений будет 4¹⁰=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) : * , /

Поэтому изначально можно сгенерировать до 2¹⁰=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}    {-,+}       {/,*,/}

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

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

Получение номера по размещению с повторениями

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

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Ранее мы научились генерировать размещение с повторениями по номеру. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему.

Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке.
20221112₃=2*2187+0*729+2*243+2*81+1*27+1*9+1*3+2*1=4374+486+162+27+9+3+2=5063₁₀.

Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064.

1. typedef unsigned long long ULL;
2. ULL get_num_by_placement_rep(const vector<int> &cur, int n, int k) {
3.   ULL num = 0;
4.   ULL step = 1;
5.   for (int i=cur.size()-1;i>=0;--i) {
6.     num += cur[i] * step;
7.     step *= k;
8.   }
9.   return num;
10. }

* This source code was highlighted with Source Code Highlighter.

Генерация размещения с повторениями по номеру

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

Теория: Окулов. Дискретная математика. 2008
Практика: [82. Все строки длины n из k различных символов]

Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке.
Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания.
Проверим наше утверждение на размещении “31”: 31₄=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0.
Данная логика отображена в следующей функции:

1. typedef unsigned long long ULL;
2. void gen_placement_rep_by_num(vector<int> &cur, ULL num, int n, int k) {
3.   cur.assign(n,0);
4.   int pos = n - 1;
5.   while (num) {
6.     cur[pos--] = num % k;
7.     num /= k;
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.

Генерация следующего и предыдущего размещения с повторениями

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

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке.

R_i = {1, 5, 6, 4, 6}; n = 5; k = 7
R_i+1 = {1, 5, 6, 5, 0}

Для генерации следующего размещения будем пользоваться простым правилом:
Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.

1. bool next_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos>=0 && r) {
5.     cur[pos]++;
6.     r = cur[pos] == k;
7.     if (r) cur[pos] = 0;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация предыдущего размещения делается по аналогичной схеме:

1. bool prev_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos >=0 && r) {
5.     cur[pos]--;
6.     r = cur[pos] == -1;
7.     if (r) cur[pos] = k-1;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Генерация всех размещений с повторениями рекурсивным способом

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

Теория: Окулов. Дискретная математика. 2008
Практика: Все строки длины n из k различных символов

Пусть задан алфавит из K первых цифр, начиная с 0. Необходимо сгенерировать все размещения с повторениями длины N для элементов данного алфавита. Другими словами для N = 2 и K = 4 получаем:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Генерация такой последовательности не должно составить большого труда:

1. void gen(int pos) {
2.   if (pos == n) {
3.     for (int i=0;i<n;++i)
4.       printf("%d",cur[i]);
5.     printf("\n");
6.     return;
7.   }
8.   for (int i=0;i<k;++i) {
9.     cur[pos] = i;
10.     gen(pos+1);
11.   }
12. }

* This source code was highlighted with Source Code Highlighter.

Изначально функция gen запускается с параметром 0.
Полное решение: здесь