Урок 17. Задача №9. Решение.

Урок 17. Задача №9.

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

Входные данные   Результат 
5+2               7
1-2*5+2          -7
5*6+7-3*2+11      42
type
  IntArr = array[1..6] of integer;
  ArrStr = array[1..5] of string;

function Check_tmp(s: string; mas: IntArr): IntArr;
var a, i: integer;
begin
  if(s <> '')then
  begin
    val(s, a);
    for i := 1 to length(mas) do
      if(mas[i] = 0) then
      begin
        mas[i] := a;
        break;
      end;
  end;
  result := mas;
end;

procedure parsingString(var otherArr: IntArr; var otherSig: ArrStr);
var str, tmp: string;
  key: boolean;
  i, j, k, conv: integer;
begin
  k := 1;
  readln(str);
  for i := 1 to length(str) do
  begin
    key := false;
    if(str[i] >= '0') and (str[i] <= '9') then
      tmp += str[i]
    else if(str[i] = '+') or (str[i] = '-') or (str[i] = '*') then
    begin
      otherSig[k] := str[i];
      k += 1;
      key := true;
    end;

    if(key = true) and (tmp <> '') then
    begin
      val(tmp, conv);
      j += 1;
      otherArr[j] := conv;
      tmp := '';
    end;
  end;
  otherArr := Check_tmp(tmp, otherArr);
end;

function RebuildArrSig(copy_arr_sig: ArrStr): ArrStr;
var i, j: integer;
  newarrSig: ArrStr;
begin
  j := 1;
  i := 1;
  while(i <= length(copy_arr_sig)) do
  begin
    if(copy_arr_sig[i] = '') then
      i += 1;
    newarrSig[j] := copy_arr_sig[i];
    j += 1;
    i += 1;
  end;
  result := newarrSig;
end;

function RebuildIntArr(copy_arr_int: IntArr): IntArr;
var i, j: integer;
  new_int_arr: IntArr;
begin
  j := 1;
  i := 1;
  while(i <= length(copy_arr_int)) do
  begin
    if(copy_arr_int[i] = 0) then
      i += 1;
    new_int_arr[j] := copy_arr_int[i];
    j += 1;
    i += 1;
  end;
  result := new_int_arr;
end;

function GetRes(arrInt: IntArr; arrStr: ArrStr): integer;
var i, x: integer;
begin
  x := arrInt[1];
  for i := 1 to length(arrStr) do
  begin
    if(arrStr[i] = '+') then
      x := x + arrInt[i + 1]
    else if(arrStr[i] = '-') then
      x := x - arrInt[i + 1];
  end;
  result := x;
end;

procedure multOperation(var otherArr: IntArr; var otherSig: ArrStr);
var i: integer;
begin
  for i := 1 to length(otherSig) do
  begin
    if(otherSig[i] = '') then
      break;
    if(otherSig[i] = '*') then
    begin
     otherSig[i] := '';
     otherArr[i] := otherArr[i] * otherArr[i + 1];
     otherArr[i + 1] := 0;
    end;
  end;
end;

var i, j: integer;
  arr, newarr: IntArr;
  arrSig: ArrStr;
begin
  writeln('Enter math operation string: ');
  parsingString(arr, arrSig);
  multOperation(arr, arrSig);
  arrSig := RebuildArrSig(arrSig);
  arr := RebuildIntArr(arr);
  writeln();
  writeln('Result = ', GetRes(arr, arrSig));

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

переделать к сравнению производительности:

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

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

Firons's picture

Переделал функцию:

Check_tmp();

т. к. в последней ячейке массива был мусор (такой->2311534234) и условие:

if(mas[i] = 0) then

не работало.
Также добавил:

mas[posArr] := a;

последнюю значившую позицию в массиве, для записи оставшегося числа, после разбора строки.
Переделал функцию:

multOperation();

если в выражении встречались подряд символы (*), то функция работала некорректно.
Добавил: вместо незначащего символа (0) в массиве целых чисел теперь символ (-1).

type
  IntArr = array[1..100] of integer;
  ArrStr = array[1..99] of string;

function Check_tmp(s: string; mas: IntArr; posArr: integer): IntArr;
var a, i: integer;
begin
  if(s <> '')then
  begin
    val(s, a);
    mas[posArr] := a;
  end;
  result := mas;
end;

procedure parsingString(str: string; var otherArr: IntArr; var otherSig: ArrStr);
var tmp: string;
  key: boolean;
  i, j, k, conv: integer;
begin
  k := 1;
  for i := 1 to length(str) do
  begin
    key := false;
    if(str[i] >= '0') and (str[i] <= '9') then
      tmp += str[i]
    else if(str[i] = '+') or (str[i] = '-') or (str[i] = '*') then
    begin
      otherSig[k] := str[i];
      k += 1;
      key := true;
    end;

    if(key = true) and (tmp <> '') then
    begin
      val(tmp, conv);
      j += 1;
      otherArr[j] := conv;
      tmp := '';
    end;
  end;
  j += 1;
  otherArr := Check_tmp(tmp, otherArr, j);
end;

function RebuildArrSig(copy_arr_sig: ArrStr): ArrStr;
var i, j: integer;
  newarrSig: ArrStr;
begin
  j := 1;
  i := 1;
  while(i < length(copy_arr_sig)) do
  begin
    if(copy_arr_sig[i] = '') then
      i += 1;
    newarrSig[j] := copy_arr_sig[i];
    j += 1;
    i += 1;
  end;
  result := newarrSig;
end;

function RebuildIntArr(copy_arr_int: IntArr): IntArr;
var i, j: integer;
  new_int_arr: IntArr;
begin
  j := 1;
  i := 1;
  while(i < length(copy_arr_int)) do
  begin
    if(copy_arr_int[i] = -1) then
      i += 1;
    new_int_arr[j] := copy_arr_int[i];
    j += 1;
    i += 1;
  end;
  result := new_int_arr;
end;

function GetRes(arrInt: IntArr; arrStr: ArrStr): integer;
var i, x: integer;
begin
  x := arrInt[1];
  for i := 1 to length(arrStr) do
  begin
    if(arrStr[i] = '+') then
      x := x + arrInt[i + 1]
    else if(arrStr[i] = '-') then
      x := x - arrInt[i + 1];
  end;
  result := x;
end;

procedure multOperation(var otherArr: IntArr; var otherSig: ArrStr);
var i: integer;
begin
  for i := 1 to length(otherSig) do
  begin
    if(otherSig[i] = '') then
      break;
    if(otherSig[i] = '*') then
    begin
      otherSig[i] := '';
      if(otherArr[i] = -1) then
      begin
        otherArr[i] := otherArr[i - 1] * otherArr[i + 1];
        otherArr[i - 1] := -1;
      end else
      begin
        otherArr[i] := otherArr[i] * otherArr[i + 1];
        otherArr[i + 1] := -1;
      end;
    end;
  end;
end;

function CompRandExp(some_str: string): integer;
var arr: IntArr;
  arrSig: ArrStr;
begin
  parsingString(some_str, arr, arrSig);
  multOperation(arr, arrSig);
  arrSig := RebuildArrSig(arrSig);
  arr := RebuildIntArr(arr);
  result := GetRes(arr, arrSig);
end;

var str: string;
begin
  writeln('Enter math operation string: ');
  readln(str);
  writeln();
  writeln('Result = ', CompRandExp(str));

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

Program LessonPascal;
uses DateUtils, sysutils;
type
  IntArr = array[1..30000] of integer;
  ArrStr = array[1..29999] 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 Check_tmp(s: string; var mas: IntArr; var posArr: integer): IntArr;
var a, i: integer;
begin
  if(s <> '')then
  begin
    val(s, a);
    mas[posArr] := a;
  end;
  result := mas;
end;

procedure parsingString(str: string; var otherArr: IntArr; var otherSig: ArrStr);
var tmp: string;
  key: boolean;
  i, j, k, conv: integer;
begin
  k := 1;
  for i := 1 to length(str) do
  begin
    key := false;
    if(str[i] >= '0') and (str[i] <= '9') then
      tmp += str[i]
    else if(str[i] = '+') or (str[i] = '-') or (str[i] = '*') then
    begin
      otherSig[k] := str[i];
      k += 1;
      key := true;
    end;

    if(key = true) and (tmp <> '') then
    begin
      val(tmp, conv);
      j += 1;
      otherArr[j] := conv;
      tmp := '';
    end;
  end;
  j += 1;
  Check_tmp(tmp, otherArr, j);
end;

function RebuildArrSig(copy_arr_sig: ArrStr): ArrStr;
var i, j: integer;
  newarrSig: ArrStr;
begin
  j := 1;
  i := 1;
  while(i < length(copy_arr_sig)) do
  begin
    if(copy_arr_sig[i] = '') then
      i += 1;
    newarrSig[j] := copy_arr_sig[i];
    j += 1;
    i += 1;
  end;
  result := newarrSig;
end;

function RebuildIntArr(copy_arr_int: IntArr): IntArr;
var i, j: integer;
  new_int_arr: IntArr;
begin
  j := 1;
  i := 1;
  while(i < length(copy_arr_int)) do
  begin
    if(copy_arr_int[i] = -1) then
      i += 1;
    new_int_arr[j] := copy_arr_int[i];
    j += 1;
    i += 1;
  end;
  result := new_int_arr;
end;

function GetRes(arrInt: IntArr; arrStr: ArrStr): integer;
var i, x: integer;
begin
  x := arrInt[1];
  for i := 1 to length(arrStr) do
  begin
    if(arrStr[i] = '+') then
      x := x + arrInt[i + 1]
    else if(arrStr[i] = '-') then
      x := x - arrInt[i + 1];
  end;
  result := x;
end;

procedure multOperation(var otherArr: IntArr; var otherSig: ArrStr);
var i: integer;
begin
  for i := 1 to length(otherSig) do
  begin
    if(otherSig[i] = '') then
      break;
    if(otherSig[i] = '*') then
    begin
      otherSig[i] := '';
      if(otherArr[i] = -1) then
      begin
        otherArr[i] := otherArr[i - 1] * otherArr[i + 1];
        otherArr[i - 1] := -1;
      end else
      begin
        otherArr[i] := otherArr[i] * otherArr[i + 1];
        otherArr[i + 1] := -1;
      end;
    end;
  end;
end;

function CompRandExp(some_str: string): integer;
var arr: IntArr;
  arrSig: ArrStr;
begin
  parsingString(some_str, arr, arrSig);
  multOperation(arr, arrSig);
  arrSig := RebuildArrSig(arrSig);
  arr := RebuildIntArr(arr);
  result := GetRes(arr, arrSig);
end;

var numb, MilliSecondsDiff: integer;
  str: string;
  FromTime, ToTime: TDateTime;
begin
  str := GetRandExpr(30000);
  writeln(str);
  FromTime := Now();
  numb := CompRandExp(str);
  writeln();
  writeln('Result = ', numb);
  ToTime := Now();
  MilliSecondsDiff := MilliSecondsBetween(ToTime,FromTime);
  writeln('Vremya: ', MilliSecondsDiff);

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