Арифметические действия с цифрами числа

[Aspirisha]

Ребята, привет. Короче говоря, боюсь мне никто не ответит так как последний пост датируется годом ранее, но все таки. Короче задачку мне поставили недавно такую же, но условия несколько другие:
На вход подается 2 числа. Первое не более чем 100-значное, второе влезает в int.

1. Необходимо получить второе число вставив знаки операций между цифрами первого числа.
2. Скобки ставить не надо - то есть только + - * / или ничего.
Очевидно, простой перебор в худшем случае переживет нашу вселенную. Не говоря уже о том что становятся к тому же дорогими вычисления - нужна длинная арифметика.

Есть ли идеи как оптимизировать перебор до ~ 10^8 операций?

[Serge_Bliznykov]

1) не знаю. я вообще не представляю другого варианта решения, кроме как полный перебор... сорри..

2) стало любопытным. а что, при подборе ещё нужно учитывать приоритет операций?

вот, допустим, дано число 222
знаки расставили так:
2+2*2 = ?
сколько получается у Вас в этом случае?

[Aspirisha]

Serge, да, приоритет учитывается и поэтому 2 + 2 * 2 == 6. Ладно, еще подумаю, спасибо за ответ!

[Poma][a]

Серж, а Вы не могли бы прокоментировать форму вывода?
Вот

 3 1 + =      4

Понятно а

1 2   3 /+ 4   56 +* =      100

Не очень...
Это эквивалентно 1/2 + 3 + 4 * 56?

[Serge_Bliznykov]

Aspirisha, а Вы зря в двух темах одновременно одну и ту же проблему обсуждаете!
Но называете "КРОССПОСТИНГ" и является нарушением правил форума!

думаю, что правильным будет здесь обсуждение прекратить, а в созданной Вами теме продолжить.

Удачи и не нарушайте, плиз, больше!

Poma][a,
нет. смысл постфиксной записи, что она выполняется над двумя операндами в стеке и результат помещается тоже в стек.
1 2 3 /+ 4 56 +*

1 в стек
2 в стек
3 в стек
/ достаём два числа с вершины стека и делим одно на другое (т.е. 2 делим на 3). результат (число равное 2/3) в стек
+ добавляем к результату 1 - полученный результат (1+2/3) в стек
4 в стек
56 в стек
+ берём два числа из стека, суммируем. результат (60) в стек
* берём два числа из стека и перемножаем (60 * (1+2/3) = 60 + 40 = 100 ) результат (100) в стек

= результат достаём из стека (это число 100). Вычисления закончены.

[Poma][a]

Серж, огромное спасибо

[Serge_Bliznykov]

Сообщение от mario_xxx

мне нужно понять алгоритм перебора,что-то не получается,объясните пожалуйста

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

...
  for i:=1 to N-1 do begin
      L := Copy(s,1,i);
      R := Copy(s,i+1,N-i);
      NextVariant(Left,L,R+' ? '+Right);
  end;
...

посмотрим на примере.
для строки 12345 в результате данного цикла (с учётом рекурсии!!) будем получать следующие варианты рекурсивного вызова:

вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '2345 ? '
вызываем NextVariant с параметрами: Left = ''' S = '12' Right = '345 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '2 ? 345 ? '
вызываем NextVariant с параметрами: Left = ''' S = '123' Right = '45 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '23 ? 45 ? '
вызываем NextVariant с параметрами: Left = ''' S = '12' Right = '3 ? 45 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '2 ? 3 ? 45 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1234' Right = '5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '234 ? 5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '12' Right = '34 ? 5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '2 ? 34 ? 5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '123' Right = '4 ? 5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '23 ? 4 ? 5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '12' Right = '3 ? 4 ? 5 ? '
вызываем NextVariant с параметрами: Left = ''' S = '1' Right = '2 ? 3 ? 4 ? 5 ? '
'

кстати, как видим, параметр Left не используется и может (и должен быть выкинут из процедуры NextVariant) - это не нужный параметр, мой просчёт!

полученные строки передаются в процедуру OutEq. Все знаки вопросов последовательно заменяются на знаки операции.

Чтобы упростить алгоритм перебора знаков, используется т.н. польская форма записи выражения. Это когда идут сначала операнды, а потом уже сама операция. Преимущество этой записи в том, что она:
1) не использует скобки - они не имеют смысла в данной форме записи
2) все операции выполняются последовательно, все операции одного приоритета.
Например, обычное выражение (1+2)*3 будет в польской записи выглядеть как 1 2 + 3 *
а выражение 1+2*3 будет в польской записи выглядеть так 1 2 3 *+

процедура CheckAndShow вычисляет переданную ей строку с помощью функции Calculate (о вычислении выражения в польской записи см. мой пост #16 выше)

полученное (вычисленное) значение строки сверяется с заданным числом и если оно совпадает (или если задали target = 0) - то строка выдаётся как подходящее решение.

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


p.s. для разбора программ весьма рекомендую пошаговую отладку с контролем переменных. Очень помогает разобраться, что и где происходит..

p.p.s. если в результате моего рассказа какие-то детали остались невыясненными/непонятыми - спрашивайте конкретно, постараюсь ответить.

[mario_xxx]

Спасибо Serge_Bliznykov, разобрался, а не могли бы вы написать процедуру перевода в инфиксную форму?

[Serge_Bliznykov]

Сообщение от mario_xxx

Спасибо Serge_Bliznykov, разобрался, а не могли бы вы написать процедуру перевода в инфиксную форму?

ну, в чёрновом варианте (в первом приближении), такой перевод может выглядеть так:

....

var
  StackStr:array[1..MAXStack] of string;
  TopofStackStr:integer; {points to top of stask}

....


function ConvertPostFixToInFix(const s: string): string;

   procedure PushStr(s1:string);
   begin
     if TopofStackStr>=MAXStack then WriteLn('Stask full')
     else
     begin
       stackStr[TopofStackStr]:= s1;
       TopofStackStr := TopofStackStr + 1;
     end;
   end; { конец  процедуры  помещения объекта в стек}

   { выборка объекта из стека }
   function PopStr:string;
   begin
     TopofStackStr := TopofStackStr -1;
     if TopofStackStr<1 then
     begin
       WriteLn('Stack underflow');
       TopofStackStr := TopofStackStr + 1;
       PopStr:='';
     end
     else PopStr := stackStr[TopofStackStr];
   end; { конец функции выборки объекта из стека }

var
  i, i0  : integer;
  s0, s1, s2 : string;
begin
  TopofStackStr := 1;
  i:=1;
  while i<=Length(s) do begin
    i0 :=0;
    while ((i+i0)<=Length(s)) and (s[i+i0] in ['0'..'9']) do inc(i0);
    if i0>0 then {нашли число в строке. поместим его в стек} begin
      s0 := Copy(s,i,i0);
      PushStr(s0);
      inc(i, i0);
    end
    else begin
      case s[i] of
       ' ' : begin end;
       '+' : begin s1 := PopStr; s2 := PopStr;
                   PushStr( '(' +  s2 + ' + ' + s1 + ')' ); end;
       '-' : begin s1 := PopStr; s2 := PopStr;
                   PushStr( '(' +  s2 + ' - ' + s1 + ')' ); end;
       '*' : begin s1 := PopStr; s2 := PopStr;
                   PushStr( '(' +  s2 + ' * ' + s1 + ')' ); end;
       '/' : begin s1 := PopStr; s2 := PopStr;
                   PushStr( '(' +  s2 + ' / ' + s1 + ')' ); end;
      end;
      inc(i);
    end;
  end;

  {уберём обрамляющие (крайние) скобки}
  s1 := PopStr;
  if Length(s1)>3 then
    if ( s1[1]='(' ) and (s1[Length(s1)]=')')
        then s1 := Copy(s1, 2, Length(s1) - 2 );

  ConvertPostFixToInFix := s1;
end;

но данный метод выдаёт выражение с избыточными скобками.
например, для
1 2 * 3 * 4 * = 24 выражение в infix: ((1 * 2) * 3) * 4
очевидно, что скобки здесь избыточны..
Впрочем, ошибочным это выражение от избыточности не становится


p.s. полностью код PEREB_V3.PAS в архиве.

[SeaSnake]

Предлагаю вариант решения исходной задачи на С++ (аналог Perebor_2)