Решаем задачи Абрамян на Паскале. Recur16

Recur16. Вывести значение целочисленного выражения, заданного в виде строки $$S$$. Выражение определяется следующим образом:
<выражение>::= <терм>| <выражение>+<терм>| <выражение>- <терм>
<терм>::= <элемент>| <терм>* <элемент>
<элемент>::= <цифра>| (<выражение>)

Решение:

program Recur16;

function LenExpression(S:String):integer;
var len:integer;
begin
 if length(S)<=0 then Result:=0
 else
  case s[length(S)] of
   ')':
    begin
     delete(S,length(S),1);
     len:=LenExpression(S);
     delete(S,length(S)-len+1,len);
     Result:=len+LenExpression(S)+1;
    end;
   '(': Result:=1
   else
    begin
     delete(S,length(S),1);
     Result:=1+LenExpression(S);
    end;
  end;
end;

function Expression(S:String):integer;
var
 Res,len:integer;
begin
 Res:=0;
 if length(S)>0 then
  begin
   case s[length(S)] of
    ')': begin 
          delete(S,length(S),1);
          len:=LenExpression(S);
          Res:=Expression(S);
          delete(S,length(S)-len+1,len);
         end;
    '0'..'9': begin
               Res:=(ord(S[length(S)])-48);
               delete(S,length(S),1);
              end;
   end;
   if length(S)>0 then
    Case s[length(S)] of
     '-': begin
           delete(S,length(S),1);
           Result:=Expression(S)-Res;
          end;
     '+': begin
           delete(S,length(S),1);
           Result:=Expression(S)+Res;
          end;
     '*': begin
           delete(S,length(S),1);
           Result:=Expression(S)*Res;
          end;
     '(': Result:=Res;
    end
   else Result:=Res; 
  end
  else Writeln('!!error!!');
end;

var
 S:String;
begin
 Write('S: ');
 Readln(S);
 S:='('+S+')';
 Writeln('Exp: ',Expression(S));
end.

program Recur16;

function LenExpression(S:String):integer;

var len:integer;

begin

if length(S)<=0 then Result:=0

else

case s[length(S)] of

')':

begin

delete(S,length(S),1);

len:=LenExpression(S);

delete(S,length(S)-len+1,len);

Result:=len+LenExpression(S)+1;

end;

'(': Result:=1

else

begin

delete(S,length(S),1);

Result:=1+LenExpression(S);

end;

function Expression(S:String):integer;

var

Res,len:integer;

begin

Res:=0;

if length(S)>0 then

begin

case s[length(S)] of

')': begin

delete(S,length(S),1);

len:=LenExpression(S);

Res:=Expression(S);

delete(S,length(S)-len+1,len);

end;

'0'..'9': begin

Res:=(ord(S[length(S)])-48);

delete(S,length(S),1);

end;

if length(S)>0 then

Case s[length(S)] of

'-': begin

delete(S,length(S),1);

Result:=Expression(S)-Res;

end;

'+': begin

delete(S,length(S),1);

Result:=Expression(S)+Res;

end;

'*': begin

delete(S,length(S),1);

Result:=Expression(S)*Res;

end;

'(': Result:=Res;

end

else Result:=Res;

end

else Writeln('!!error!!');

end;

var

S:String;

begin

Write('S: ');

Readln(S);

S:='('+S+')';

Writeln('Exp: ',Expression(S));

end.

Другие задачи из раздела Recur можно посмотреть здесь.

Комментарии 1

program Recur16; //pabc.net

// uses PT4;

function isSign(self: char): boolean; extensionmethod;
begin
  Result := self in ['+', '-']
end;

function Foo(s: string; k, n: integer): integer; forward;

function Elem(s: string; k, n: integer): integer;
begin
  if k = n then Result := s[k].ToDigit
  else Result := Foo(s, k + 1, n - 1)
end;

function Term(s: string; k, n: integer): integer;
begin
  var l := n;
  var (Right, Left) := (0, 0); // счетчики правой и левой скобок
  while (l > k) and not ((s[l] = '*') and (Right = Left)) do
  begin
    if s[l] = ')' then Right += 1
    else if s[l] = '(' then Left += 1;
    dec(l)
  end;
  if l > k then
    Result := Term(s, k, l - 1) * Elem(s, l + 1, n)
  else
    Result := Elem(s, k, n)
end;

function Foo(s: string; k, n: integer): integer;
begin
  var l := n;
  var (Right, Left) := (0, 0);
  while (l > k) and not (s[l].isSign and (Right = Left)) do
  begin
    if s[l] = ')' then Right += 1
    else if s[l] = '(' then Left += 1;
    dec(l)
  end;
  if l > k then
  begin
    if s[l] = '+' then
      Result := Foo(s, k, l - 1) + Term(s, l + 1, n)
    else if s[l] = '-' then
      Result := Foo(s, k, l - 1) - Term(s, l + 1, n)
  end
  else
    Result := Term(s, k, n)
end;

begin
  // Task('Recur16');
  var s := ReadlnString(); // 6*(8*8+(2-3+8*8))*8
  Write(Foo(s, 1, s.Length)) // 6096
end.

program Recur16; //pabc.net

// uses PT4;

function isSign(self: char): boolean; extensionmethod;

begin

Result := self in ['+', '-']

end;

function Foo(s: string; k, n: integer): integer; forward;

function Elem(s: string; k, n: integer): integer;

begin

if k = n then Result := s[k].ToDigit

else Result := Foo(s, k + 1, n - 1)

end;

function Term(s: string; k, n: integer): integer;

begin

var l := n;

var (Right, Left) := (0, 0); // счетчики правой и левой скобок

while (l > k) and not ((s[l] = '*') and (Right = Left)) do

begin

if s[l] = ')' then Right += 1

else if s[l] = '(' then Left += 1;

dec(l)

end;

if l > k then

Result := Term(s, k, l - 1) * Elem(s, l + 1, n)

else

Result := Elem(s, k, n)

end;

function Foo(s: string; k, n: integer): integer;

begin

var l := n;

var (Right, Left) := (0, 0);

while (l > k) and not (s[l].isSign and (Right = Left)) do

begin

if s[l] = ')' then Right += 1

else if s[l] = '(' then Left += 1;

dec(l)

end;

if l > k then

begin

if s[l] = '+' then

Result := Foo(s, k, l - 1) + Term(s, l + 1, n)

else if s[l] = '-' then

Result := Foo(s, k, l - 1) - Term(s, l + 1, n)

end

else

Result := Term(s, k, n)

end;

begin

// Task('Recur16');

var s := ReadlnString(); // 6*(8*8+(2-3+8*8))*8

Write(Foo(s, 1, s.Length)) // 6096

end.

Алгоритм. В Foo ищем в выражении справа налево индекс l первого оператора «+» или «-» , который находится вне скобок. Если нашли — результат равен Foo(s, k, l-1) (+/-) Term(s, l+1, n). Иначе результат равен Term(s, k, n). В Term аналогично, но для оператора «*». В Elem результат или цифра, или выражение в скобках. Чтобы его посчитать нужно кинуть строку без крайних скобок в Foo.

Ответить

Решаем задачи Абрамян на Паскале. Recur16

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

Комментарии 1

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