Описание
Имеется таблица M×N, в каждой ячейке которой записано либо целое число, либо арифметическая формула. В формулах могут присутствовать целые числа, знаки "*", "/", "+", "-", "(", ")", пробелы и ссылки на значения из других ячеек таблицы, записываемые в виде {НомерСтроки, НомерСтолбца}, например {1,10}

Задание
Требуется вычислить значения во всех ячейках заданной таблицы


Входные данные
В первой строке входного файла записаны целые числа М и N (1≤M,N≤20). В каждой из последующих М строк содержится описание очередной строки таблицы. Описание состоит из целых чисел и арифметических формул, разделенных символами "|" (ASCII-код 124). Все числа принадлежат диапазону [-32768, 32767], а длина каждой формулы не превышает 100 символов

Выходные данные
Выведите в выходной файл значения всех ячеек таблицы. Значения ячеек каждой строки таблицы должны быть записаны через пробел в отдельной строке выходного файла. Все значения следует выводить с точностью до двух знаков после десятичной точки. Если значение ячейки вычислить невозможно, вместо него следует вывести символ "-" (ASCII-код 45)


Например:

SPSHEET.IN
2 3
  1   | {1,1}*10  +3 | -{1,2}/{2,2}
{2,3} |   0          |      {2,1}

SPSHEET.OUT
1.0 13.00 –
- 0.00 -
Идеи
Синтаксический анализ, обход в глубину, динамическое программирование

Комментарии
Каждая ячейка в описываемом ниже процессе вычислений будет иметь один из следующих статусов: "еще не вычислялась", "вычисляется", "уже вычислялась, значение не может быть вычислено" и "уже вычислялась, значение известно"

Пусть нам требуется узнать значение какой-либо из ячеек, имеющей статус "еще не вычислялась". Меняем ее статус на "вычисляется" и производим синтаксический разбор формулы, записанной в ней. Для этого можно использовать метод рекурсивного спуска [Шень 95, гл.13]. Если мы встретим ссылку на ячейку, имеющую статус "значение известно", то используем это значение. Если мы встретим ссылку на ячейку, имеющую статус "значение не может быть вычислено", то значение в анализируемой ячейке также не может быть вычислено и мы для нее устанавливаем тот же самый статус и заканчиваем разбор. Встретив ссылку на ячейку, значение которой еще не вычислялось, рекурсивно переходим к нахождению ее значения

Рассмотрим, наконец, случай ссылки на ячейку со статусом «вычисляется». В этой ситуации мы обнаружили цикл из ссылок, который не может быть разрешен. Меняем статус анализируемой ячейки на "значение не может быть вычислено" и заканчиваем разбор.

В случае, когда значения всех ячеек, на которые ссылается текущая, были подсчитаны и в процессе разбора формулы не возникало делений на ноль, статус анализируемой ячейки меняется на "уже вычислялась, значение известно"

Легко видеть, что описанный процесс представляет собой обход в глубину графа, вершины которого соответствуют ячейкам таблицы, а ребра - ссылкам из одной ячейки на другую. Присваивание значений ячейкам происходит в том же порядке, что и присваивание новых номеров вершинам ациклического графа при выполнении топологической сортировки [Липский 88, п.3.4; Кнут 76, п.2.2.3].


 


Решение

{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X+,Y+}
{$M 65520,0,655360}

Program spreadsheet;
Const
  InFile='spsheet.in';
  OutFile='spsheet.out';
  MaxMN=20;
  MaxCell=MaxMN*MaxMN;
  Eps=1E-8;
Type
  Real=Extended;
  TElem=String[102];
  TOffersArr=Array[0..MaxCell-1,0..MaxCell Div 8]Of Byte;
  TOffNumArr=Array[0..MaxCell-1]Of Word;
Var
  M,N,Cells:Word;
  Elems:Array[0..MaxCell-1]Of TElem;
  Value:Array[0..MaxCell-1]Of Real;
  Ok:Array[0..MaxCell-1]Of Boolean;
  Div0:Array[0..MaxCell-1]Of Boolean;
  Offers:^TOffersArr;
  ONum:TOffNumArr;
  DivBy0:Boolean;
  S:String;
  Ps:Byte;

Function CellByXY(X,Y:Byte):Word;
Begin
  CellByXY:=Word(Y-1)*M+X-1;
End;

Procedure CellToXY(C:Word; Var X,Y:Byte);
Begin
  Y:=C Div M+1;
  X:=C Mod M+1;
End;

Function GetOffers(C1,C2:Byte):Boolean;
Begin
  GetOffers:=Offers^[C1,C2 Shr 3] And (1 Shl (C2 And $7))>0;
End;

Procedure SetOffer(C1,C2:Byte);
Begin
  Offers^[C1,C2 Shr 3]:=Offers^[C1,C2 Shr 3] Or (1 Shl (C2 And $7));
  Inc(ONum[C1]);
End;

Procedure Load;
Var
  I,J:Byte;
  Ch:Char;
  Cur:TElem;
Begin
  New(Offers);
  Assign(Input,InFile);
  ReSet(Input);
  ReadLn(N,M);
  For I:=1 To N Do Begin
    For J:=1 To M Do Begin
      Cur:='';
      Repeat
        Read(Ch);
        Case Ch Of
          ' ',#9,'|':;
          Else Cur:=Cur+Ch;
        End;
      Until (Ch='|') Or EOLN;
      Elems[CellByXY(J,I)]:=Cur;
    End;
    ReadLn;
  End;
  Close(Input);
  Cells:=M*N;
End;

Procedure FillOffers;
Var
  I,J:Word;
  X,Y:Byte;
  AS,S1,S2:String[6];
Begin
  FillChar(Offers^,SizeOf(Offers^),0);
  FillChar(ONum,SizeOf(ONum),0);
  For I:=0 To Cells-1 Do Begin
    CellToXY(I,X,Y);
    Str(X,S1);
    Str(Y,S2);
    AS:='{'+S2+','+S1+'}';
    For J:=0 To Cells-1 Do If Pos(AS,Elems[J])>0 Then SetOffer(J,I);
  End;
End;

Function Expression:Real; Forward;
Function Multiplicator:Real;
Var
  Result:Real;
  II:Byte;
  AX,AY:Byte;
  Cnt:Integer;
Begin
  Case S[Ps] Of
    '{':Begin
      Inc(Ps);
      II:=Ps;
      While (S[Ps]>='0') And (S[Ps]<='9') Do Inc(Ps);
      Val(Copy(S,II,Ps-II),AY,Cnt);
      Inc(Ps);
      II:=Ps;
      While (S[Ps]>='0') And (S[Ps]<='9') Do Inc(Ps);
      Val(Copy(S,II,Ps-II),AX,Cnt);
      Result:=Value[CellByXY(AX,AY)];
      Inc(Ps);
      If Div0[CellByXY(AX,AY)] Then DivBy0:=True;
    End;
    '0'..'9':Begin
      II:=Ps;
      While (S[Ps]>='0') And (S[Ps]<='9') Do Inc(Ps);
      Val(Copy(S,II,Ps-II),Result,Cnt);
    End;
    '-':Begin
      Inc(Ps);
      Result:=-Multiplicator;
    End;
    '+':Begin
      Inc(Ps);
      Result:=Multiplicator;
    End;
    '(':Begin
      Inc(Ps);
      Result:=Expression;
      Inc(Ps);
    End;
  End;
  Multiplicator:=Result;
End;

Function Additional:Real;
Var
  Result:Real;
  Temp:Real;
Begin
  Result:=Multiplicator;
  While (S[Ps]='*') Or (S[Ps]='/') Do Begin
    Inc(Ps);
    Case S[Ps-1] Of
      '*':Result:=Result*Multiplicator;
      '/':Begin
        Temp:=Multiplicator;
        If Abs(Temp)Then Begin DivBy0:=True; Break; End Else Result:=Result/Temp;
      End;
    End;
  End;
  Additional:=Result;
End;

Function Expression:Real;
Var
  Result:Real;
Begin
  Result:=Additional;
  While (S[Ps]='+') Or (S[Ps]='-') Do Begin
    If DivBy0 Then Break;
    Inc(Ps);
    Case S[Ps-1] Of
      '+':Result:=Result+Additional;
      '-':Result:=Result-Additional;
    End;
  End;
  Expression:=Result;
End;

Procedure Solve;
Var
  I,J:Word;
  Final:Boolean;
Begin
  FillChar(Ok,SizeOf(Ok),True);
  FillChar(Div0,SizeOf(Div0),False);
  Repeat
    Final:=True;
    For I:=0 To Cells-1 Do If Ok[I] And (ONum[I]=0) Then Begin
      S:=Elems[I]+#0;
      Ps:=1;
      DivBy0:=False;
      Value[I]:=Expression;
      Div0[I]:=DivBy0;
      Ok[I]:=False;
      For J:=0 To Cells-1 Do
        If Ok[J] And GetOffers(J,I) Then Dec(ONum[J]);
      Final:=False;
    End;
  Until Final;
End;

Procedure Save;
Var
  I,J:Byte;
Begin
  Assign(Output,OutFile);
  ReWrite(Output);
  For I:=1 To N Do Begin
    For J:=1 To M Do Begin
      If J>1 Then Write(' ');
      If Ok[CellByXY(J,I)] Or Div0[CellByXY(J,I)]
        Then Write('-')
        Else Write(Value[CellByXY(J,I)]:0:2);
    End;
    WriteLn;
  End;
  Close(Output);
  Dispose(Offers);
End;

Begin
  Load;
  FillOffers;
  Solve;
  Save;
End.

 

© Особенности национальных задач по информатике