Решение №9 из главы 17.Задана последовательность символов, имеющая следующий вид: p1q1p2q2p3...qn–1pn , где pi — цифра, а qi — з

Задача №9 из главы 17

Задана последовательность символов, имеющая следующий вид: p1q1p2q2p3...qn–1pn , где pi — цифра, а qi — знак арифметического действия из набора {+, –, *}. Вычислите значение выражения, предполагая, что действия выполняются согласно правилам арифметики.
Входные данные: На вход программе подается строка указанного вида, состоящая не более чем из 9 цифр, разделенных символами арифметических операций.
Выходные данные: Выведите значение арифметического выражения.
Примеры:

Входные данные   Результат 
5+2               7
1-2*5+2          -7
5*6+7-3*2+11      42
5*6+7-3*2*3+11    30
program pascal_expression_sum_delete;
type mas_str = array [1..10] of string; // секция обьявления типов

{ процедура заполнения двух массивов }
procedure fill_mmas_array( s: string; var arr_str, arr_int: mas_str; var fix_sign,fix_int,sign_mult: integer );
var i, k, n : integer;
  symbol, acc_str : string;
begin // начало тела процедуры
  i := 1;
  k := 1;
  n := 1;
  while( i <= length( s ) ) do // пока истинно условие выполняем
  begin
    acc_str := ' ' ; // пустая строка
    symbol := s[i]; // первый символ строки
    while( symbol >= '0' ) and ( symbol <= '9' ) do
    begin
      acc_str += symbol; // прибавляем в переменную элемент строки  
      i += 1;
      if( i <= length( s ) ) then // если не вышли за длинну строки
        symbol := s[i] // символ равен символу строки с индексом i
      else
        break; // иначе завершаем
    end;
    if( symbol = '+' ) or ( symbol = '-' ) or ( symbol = '*' ) then
    begin
        arr_str[n] := symbol; // первый массив
        n += 1; // увеличиваем индекс
        fix_sign += 1; // считаем кол-во знаков
        if( symbol = '*' ) then
            sign_mult += 1;
    end;
    if ( acc_str <> ' ' ) then // если строка не пуста
    begin
       arr_int[k] := acc_str; // второй  массив
       k += 1; // увеличиваем индекс массива
       fix_int += 1; // считаем кол-во чисел
    end;
    i += 1;
  end;
end; // завершение тела процедуры

{ функция сдвига массива }
function change_arr( arr : mas_str; len_fix, number, number2 : integer ) : mas_str;
   var i : integer;
begin // начало тела функции
    for i := number to ( len_fix - 1 - number2 ) do
        arr[i] := arr[i+1];
    arr[len_fix - number2 ] := '';
    change_arr := arr; // возврат функции
end; //завершение тела функции

{ процедура подсчета и вывода результата }
procedure get_print_arr(  in_str, in_int: mas_str; sign_fix, int_fix, in_mult: integer );
   var  l, count, lab, value_arr1, value_arr2, sign_mult, code, f : integer;
     str_value : string;
begin // начало тела процедуры
  l := 1; // начальный индекс массива
  count := 0; // счетчик цикла
  lab := 0;
  f := 0; // кол-во сдвигов массивов для уменьшения обхода в цикле
  sign_mult := 0;
  while( count < sign_fix ) do
  begin
      if( in_str[l] = '*' ) then
      begin
        val( in_int[l], value_arr1, code );
        val( in_int[l + 1], value_arr2, code );
        value_arr1 := value_arr1 * value_arr2;
        str( value_arr1, str_value );
        in_int[l] := str_value;
        in_int := change_arr( in_int, int_fix, l + 1, f );
        in_str := change_arr( in_str, sign_fix, l, f );
        sign_mult += 1; // cчитает кол-во умножений
        f += 1;
        lab += 1;
        count += 1;
      end
      else
      begin  
          if( in_str[l] = '+' ) and ( sign_mult = in_mult ) then
          begin
              val( in_int[l], value_arr1, code );
              val( in_int[l + 1], value_arr2, code );
              value_arr1 := value_arr1 + value_arr2;
              str( value_arr1, str_value );
              in_int[l] := str_value;
              in_int := change_arr( in_int, int_fix, l + 1, f );
              in_str := change_arr( in_str, sign_fix, l, f );
              f += 1;
              lab += 1;
              count += 1;
          end
          else
              if( in_str[l] = '-' ) and ( sign_mult = in_mult ) then
              begin
                  val( in_int[l], value_arr1, code );
                  val( in_int[l + 1], value_arr2, code );
                  value_arr1 := value_arr1 - value_arr2;
                  str( value_arr1, str_value );
                  in_int[l] := str_value;
                  in_int := change_arr( in_int, int_fix, l + 1, f );
                  in_str := change_arr( in_str, sign_fix, l, f );
                  f += 1;
                  lab += 1;
                  count += 1;
              end;
      end;
      if( lab = 1 ) then
      begin
          l := 1;
          lab := 0;
      end
      else
         l += 1;
  end;
  writeln( in_int[1] );
end; // завершение тела процедуры

var str : string;
    str_arr : mas_str;
    int_arr : mas_str;
    fix_number_sign, fix_number_int, mult_sign : integer;
begin // начало тела основной программы
  fix_number_sign := 0;
  fix_number_int := 0;
  mult_sign := 0;
  writeln( 'input expression :' );
  readln( str );
  fill_mmas_array( str, str_arr, int_arr, fix_number_sign, fix_number_int, mult_sign );
  get_print_arr( str_arr, int_arr, fix_number_sign, fix_number_int, mult_sign );
  readln();
end. //завершение тела основной программы

vedro-compota's picture

Рекомендации:

  1. Если общее число интераций то же самое, то при прочих равных лучше использовать очевидный код, в частности здесь обходить массивы два раза (со сдвигами), один раз выполнив все умножения, а потом все +/-

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

провести сравнение с решением: http://fkn.ktu10.com/?q=node/11652

Как это сделать:

  • 1) Упаковать свой код в одну функцию, которая может использовать другие.
  • 2) Протестить решение с использованием с использованием случайной строки (см. задачу 11: http://fkn.ktu10.com/?q=node/8614) 12 + 5 - 6 *8 + 7

_____________
матфак вгу и остальная классика =)

program sum_and_difference_multiplication_new;
type mas_str = array [1..10] of string; // секция обьявления типов

{ функция сдвига массива }
function change_arr( arr : mas_str; len_fix, number, number2 : integer ) : mas_str;
   var i : integer;
begin // начало тела функции
    for i := number to ( len_fix - 1 - number2 ) do
        arr[i] := arr[i+1];
    arr[len_fix - number2 ] := '';
    change_arr := arr; // возврат функции
end; //завершение тела функции

{ процедура заполнения и вывода результата }
procedure get_print_arr( s: string );
var i, k, n, l,f,count,lab,value_arr1,value_arr2,sign_mult,code,fix_sign,fix_int,mult_sign: integer;
  symbol, acc_str, str_value: string;
  sign_arr : mas_str;
  int_arr : mas_str;
begin // начало тела процедуры
  i := 1;
  k := 1;
  n := 1;
  l := 1; // начальный индекс массива
  count := 0; // счетчик цикла
  lab := 0;
  f := 0; // кол-во сдвигов массивов для уменьшения обхода в цикле
  sign_mult := 0;
  fix_sign := 0;
  fix_int := 0;
  mult_sign := 0;
  while( i <= length( s ) ) do // пока истинно условие выполняем
  begin
    acc_str := ' ' ; // пустая строка
    symbol := s[i]; // первый символ строки
    while( symbol >= '0' ) and ( symbol <= '9' ) do
    begin
      acc_str += symbol; // прибавляем в переменную элемент строки
      i += 1;
      if( i <= length( s ) ) then // если не вышли за длинну строки
        symbol := s[i] // символ равен символу строки с индексом i
      else
        break; // иначе завершаем
    end;
    if( symbol = '+' ) or ( symbol = '-' ) or ( symbol = '*' ) then
    begin
        sign_arr[n] := symbol; // первый массив
        n += 1; // увеличиваем индекс
        fix_sign += 1; // считаем кол-во знаков
        if( symbol = '*' ) then
            mult_sign += 1;
    end;
    if ( acc_str <> ' ' ) then // если строка не пуста
    begin
       int_arr[k] := acc_str; // второй  массив
       k += 1; // увеличиваем индекс массива
       fix_int += 1; // считаем кол-во чисел
    end;
    i += 1;
  end;
  //writeln( int_arr[1], int_arr[2] );
  while( count < fix_sign ) do
  begin
      if( sign_arr[l] = '*' ) then
      begin
        val( int_arr[l], value_arr1, code );
        val( int_arr[l + 1], value_arr2, code );
        value_arr1 := value_arr1 * value_arr2;
        str( value_arr1, str_value );
        int_arr[l] := str_value;
        int_arr := change_arr( int_arr, fix_int, l + 1, f );
        sign_arr := change_arr( sign_arr, fix_sign, l, f );
        sign_mult += 1; // cчитает кол-во умножений
        f += 1;
        lab += 1;
        count += 1;
      end
      else
      begin
          if( sign_arr[l] = '+' ) and ( sign_mult = mult_sign ) then
          begin
              val( int_arr[l], value_arr1, code );
              val( int_arr[l + 1], value_arr2, code );
              value_arr1 := value_arr1 + value_arr2;
              str( value_arr1, str_value );
              int_arr[l] := str_value;
              int_arr := change_arr( int_arr, fix_int, l + 1, f );
              sign_arr := change_arr( sign_arr, fix_sign, l, f );
              f += 1;
              lab += 1;
              count += 1;
          end
          else
              if( sign_arr[l] = '-' ) and ( sign_mult = mult_sign ) then
              begin
                  val( int_arr[l], value_arr1, code );
                  val( int_arr[l + 1], value_arr2, code );
                  value_arr1 := value_arr1 - value_arr2;
                  str( value_arr1, str_value );
                  int_arr[l] := str_value;
                  int_arr := change_arr( int_arr, fix_int, l + 1, f );
                  sign_arr := change_arr( sign_arr, fix_sign, l, f );
                  f += 1;
                  lab += 1;
                  count += 1;
              end;
      end;
      if( lab = 1 ) then
      begin
          l := 1;
          lab := 0;
      end
      else
         l += 1;
  end;
  writeln( int_arr[1] );
end; // завершение тела процедуры

var str : string;
begin // начало тела основной программы
  writeln( 'input expression :' );
  readln( str );
  get_print_arr( str );
  readln();
end. //завершение тела основной программы

program sum_and_difference_multiplication_new2;
type mas_str = array [1..10] of string; // секция обьявления типов

{ функция сдвига массива }
  {
function change_arr( arr : mas_str; len_fix, number, number2 : integer ) : mas_str;
   var i : integer;
begin // начало тела функции
    for i := number to ( len_fix - 1 - number2 ) do
        arr[i] := arr[i+1];
    arr[len_fix - number2 ] := '';
    change_arr := arr; // возврат функции
end; //завершение тела функции
}

{ процедура заполнения и вывода результата }
procedure get_print_arr( s: string );
var i, k, n, l,f,count,lab,value_arr1,value_arr2,sign_mult,code,fix_sign,fix_int,mult_sign: integer;
  symbol, acc_str, str_value: string;
  sign_arr : mas_str;
  int_arr : mas_str;
begin // начало тела процедуры
  i := 1;
  k := 1;
  n := 1;
  l := 1; // начальный индекс массива
  count := 0; // счетчик цикла
  lab := 0;
  f := 0; // кол-во сдвигов массивов для уменьшения обхода в цикле
  sign_mult := 0;
  fix_sign := 0;
  fix_int := 0;
  mult_sign := 0;
  while( i <= length( s ) ) do // пока истинно условие выполняем
  begin
    acc_str := ' ' ; // пустая строка
    symbol := s[i]; // первый символ строки
    while( symbol >= '0' ) and ( symbol <= '9' ) do
    begin
      acc_str += symbol; // прибавляем в переменную элемент строки
      i += 1;
      if( i <= length( s ) ) then // если не вышли за длинну строки
        symbol := s[i] // символ равен символу строки с индексом i
      else
        break; // иначе завершаем
    end;
    if( symbol = '+' ) or ( symbol = '-' ) or ( symbol = '*' ) then
    begin
        sign_arr[n] := symbol; // первый массив
        n += 1; // увеличиваем индекс
        fix_sign += 1; // считаем кол-во знаков
        if( symbol = '*' ) then
            mult_sign += 1;
    end;
    if ( acc_str <> ' ' ) then // если строка не пуста
    begin
       int_arr[k] := acc_str; // второй  массив
       k += 1; // увеличиваем индекс массива
       fix_int += 1; // считаем кол-во чисел
    end;
    i += 1;
  end;
  //writeln( int_arr[1], int_arr[2] );
  while( count < fix_sign ) do
  begin
      if( sign_arr[l] = '*' ) then
      begin
        val( int_arr[l], value_arr1, code );
        val( int_arr[l + 1], value_arr2, code );
        value_arr1 := value_arr1 * value_arr2;
        str( value_arr1, str_value );
        int_arr[l] := str_value;
        for i := l + 1 to ( fix_int - 1 - f ) do
           int_arr[i] := int_arr[i+1];
        int_arr[fix_int - f] := '';
        for i := l to ( fix_sign - 1 - f ) do
           sign_arr[i] := sign_arr[i+1];
        sign_arr[fix_sign - f ] := '';
        sign_mult += 1;
        f += 1;
        lab += 1;
        count += 1;
      end
      else
      begin
          if( sign_arr[l] = '+' ) and ( sign_mult = mult_sign ) then
          begin
              val( int_arr[l], value_arr1, code );
              val( int_arr[l + 1], value_arr2, code );
              value_arr1 := value_arr1 + value_arr2;
              str( value_arr1, str_value );
              int_arr[l] := str_value;
              for i := l + 1 to ( fix_int - 1 - f ) do
                 int_arr[i] := int_arr[i+1];
              int_arr[fix_int - f] := '';
              for i := l to ( fix_sign - 1 - f ) do
                 sign_arr[i] := sign_arr[i+1];
              sign_arr[fix_sign - f ] := '';
              f += 1;
              lab += 1;
              count += 1;
          end
          else
              if( sign_arr[l] = '-' ) and ( sign_mult = mult_sign ) then
              begin
                  val( int_arr[l], value_arr1, code );
                  val( int_arr[l + 1], value_arr2, code );
                  value_arr1 := value_arr1 - value_arr2;
                  str( value_arr1, str_value );
                  int_arr[l] := str_value;
                  for i := l + 1 to ( fix_int - 1 - f ) do
                     int_arr[i] := int_arr[i+1];
                  int_arr[fix_int - f] := '';
                  for i := l to ( fix_sign - 1 - f ) do
                     sign_arr[i] := sign_arr[i+1];
                  sign_arr[fix_sign - f ] := '';
                  f += 1;
                  lab += 1;
                  count += 1;
              end;
      end;
      if( lab = 1 ) then
      begin
          l := 1;
          lab := 0;
      end
      else
         l += 1;
  end;
  writeln( int_arr[1], int_arr[2], int_arr[3] );
end; // завершение тела процедуры

var str : string;
begin // начало тела основной программы
  writeln( 'input expression :' );
  readln( str );
  get_print_arr( str );
  readln();
end. //завершение тела основной программы








vedro-compota's picture

обшая схема замера времени:

function countResult(str: string): integer
begin 
// ...
end.

str := // получаем длинную строку-выражение

FromTime := Now();
countResult(str);
ToTime := Now();

MilliSecondsDiff := MilliSecondsBetween(ToTime,FromTime);
writeln('Vremya: ', MilliSecondsDiff);

_____________
матфак вгу и остальная классика =)

Program MilliSecondsBetweenArr;
uses DateUtils, sysutils;
type ArrStr = array[1..29000] of string;

function GetRandExpr(int: integer): string;
var i, max, val: integer;
  some_str, conv, tmp: string;
  ArraySign: array[1..3] of string = ('+', '-', '*');
begin
  randomize();
  max := 100;
  val := 0;
  some_str := '';
  tmp := '';
  for i := 1 to int do
  begin
    if(i mod 2 = 0) then
      some_str += ArraySign[random(3) + 1]
    else
    begin
      val := random(max) + 1;
      str(val, conv);
      some_str += conv;
    end;
    if(int mod 2 = 0) and (i = int - 1) then
      break;
  end;
  result := some_str;
end;


function get_print_arr( s: string;  var int_arr : ArrStr  ): string;
var i, k, n, l,f,count,lab,value_arr1,value_arr2,sign_mult,code,fix_sign,fix_int,mult_sign: integer;
  symbol, acc_str, str_value: string;
  sign_arr : ArrStr;
begin // начало тела процедуры
  i := 1;
  k := 1;
  n := 1;
  l := 1; // начальный индекс массива
  count := 0; // счетчик цикла
  lab := 0;
  f := 0; // кол-во сдвигов массивов для уменьшения обхода в цикле
  sign_mult := 0;
  fix_sign := 0;
  fix_int := 0;
  mult_sign := 0;
  while( i <= length( s ) ) do // пока истинно условие выполняем
  begin
    acc_str := ' ' ; // пустая строка
    symbol := s[i]; // первый символ строки
    while( symbol >= '0' ) and ( symbol <= '9' ) do
    begin
      acc_str += symbol; // прибавляем в переменную элемент строки
      i += 1;
      if( i <= length( s ) ) then // если не вышли за длинну строки
        symbol := s[i] // символ равен символу строки с индексом i
      else
        break; // иначе завершаем
    end;
    if( symbol = '+' ) or ( symbol = '-' ) or ( symbol = '*' ) then
    begin
        sign_arr[n] := symbol; // первый массив
        n += 1; // увеличиваем индекс
        fix_sign += 1; // считаем кол-во знаков
        if( symbol = '*' ) then
            mult_sign += 1;
    end;
    if ( acc_str <> ' ' ) then // если строка не пуста
    begin
       int_arr[k] := acc_str; // второй  массив
       k += 1; // увеличиваем индекс массива
       fix_int += 1; // считаем кол-во чисел
    end;
    i += 1;
  end;
  //writeln( int_arr[1], int_arr[2] );
  while( count < fix_sign ) do
  begin
      if( sign_arr[l] = '*' ) then
      begin
        val( int_arr[l], value_arr1, code );
        val( int_arr[l + 1], value_arr2, code );
        value_arr1 := value_arr1 * value_arr2;
        str( value_arr1, str_value );
        int_arr[l] := str_value;
        for i := l + 1 to ( fix_int - 1 - f ) do
           int_arr[i] := int_arr[i+1];
        int_arr[fix_int - f] := '';
        for i := l to ( fix_sign - 1 - f ) do
           sign_arr[i] := sign_arr[i+1];
        sign_arr[fix_sign - f ] := '';
        sign_mult += 1;
        f += 1;
        lab += 1;
        count += 1;
      end
      else
      begin
          if( sign_arr[l] = '+' ) and ( sign_mult = mult_sign ) then
          begin
              val( int_arr[l], value_arr1, code );
              val( int_arr[l + 1], value_arr2, code );
              value_arr1 := value_arr1 + value_arr2;
              str( value_arr1, str_value );
              int_arr[l] := str_value;
              for i := l + 1 to ( fix_int - 1 - f ) do
                 int_arr[i] := int_arr[i+1];
              int_arr[fix_int - f] := '';
              for i := l to ( fix_sign - 1 - f ) do
                 sign_arr[i] := sign_arr[i+1];
              sign_arr[fix_sign - f ] := '';
              f += 1;
              lab += 1;
              count += 1;
          end
          else
              if( sign_arr[l] = '-' ) and ( sign_mult = mult_sign ) then
              begin
                  val( int_arr[l], value_arr1, code );
                  val( int_arr[l + 1], value_arr2, code );
                  value_arr1 := value_arr1 - value_arr2;
                  str( value_arr1, str_value );
                  int_arr[l] := str_value;
                  for i := l + 1 to ( fix_int - 1 - f ) do
                     int_arr[i] := int_arr[i+1];
                  int_arr[fix_int - f] := '';
                  for i := l to ( fix_sign - 1 - f ) do
                     sign_arr[i] := sign_arr[i+1];
                  sign_arr[fix_sign - f ] := '';
                  f += 1;
                  lab += 1;
                  count += 1;
              end;
      end;
      if( lab = 1 ) then
      begin
          l := 1;
          lab := 0;
      end
      else
         l += 1;
  end;
  get_print_arr := int_arr[1];
end; // завершение тела процедуры


var i, MilliSecondsDiff, iterCount: integer;
  str: string;
  FromTime, ToTime: TDateTime;
   int_arr : ArrStr;
begin
  str := GetRandExpr(29000);
  iterCount := 100;
  FromTime := Now();
  for i:=1 to iterCount do
      str := get_print_arr(str, int_arr);
  writeln( 'Result 2: ', str );
  ToTime := Now();
  MilliSecondsDiff := MilliSecondsBetween(ToTime,FromTime);
  writeln('Vremya2: ', MilliSecondsDiff);

  readln(); // Удержание консоль
end.// Завершение программы