Задача 15 Сокращение одночленов

Одночлен — это выражение, состоящее из однобуквенных переменных с операциями умножения и возведения в целочисленную степень. Именами переменных являются малые латинские буквы. Умножение обозначается символом ‘*’ (ASCII 42), возведение в степень — символом ‘^’ (ASCII 94). Показатель степени состоит из одной десятичной цифры от 1 до 9. Примеры одночленов: t, a*b*c^2, y*d^1*y^9.

Требуется по данным N + M одночленам построить дробь, равную произведению первых N одночленов, делённому на произведение оставшихся M одночленов. При этом:

1. Числитель и знаменатель дроби должны быть одночленами.

2. Переменная не должна встречаться в дроби более одного раза (т. е. дробь необходимо сократить).

3. Степени переменных должны быть целыми числами большими или равными 2.

4. В числителе и знаменателе переменные должны быть отсортированы по алфавиту.

Входные данные:

В первой строке входного файла содержатся числа N и M (1  N, M  999), разделённые пробелами.

Следующие N + M строк содержат по одному одночлену каждая. Длина каждой строки не превосходит 100 символов.

Выходные данные:

В выходном файле должны быть две строки, содержащие соответственно числитель и знаменатель результата. Если после сокращения в числителе и/или в знаменателе не остаётся ни одной переменной, вместо одночлена следует вывести число 1.

Пример

Input.txt	Output.txt
2 1 x*x^7*x x*y*z y^2*z	x^10 y

program sokrashenie;

var

a:array[1..256] of longint;

b:array[1..256] of longint;

n,m:integer;

procedure init;

begin

assign(input,'input.txt');

reset(input);

readln(n,m);

end;

procedure solve;

var i,j:integer;

st:string;

begin

for i:=1 to n do

begin

readln(st); считываем строку

for j:=1 to length(st) do двигаемся по строке

if st[j] in ['a'..'z','A'..'Z'] если символ буква

then inc(a[ord(st[j])]) считаем ее

else

begin

if st[j]='^' then если символ ^

begin

inc(a[ord(st[j-1])],ord(st[j+1])-ord('0')-1); прибавляем показатель степени

inc(j); переходим к следующему символу

end;

end;

end;

for i:=1 to m do то же самое делаем для числителя

begin

readln(st);

for j:=1 to length(st) do

if st[j] in ['a'..'z','A'..'Z'] then inc(b[ord(st[j])]) else

begin

if st[j]='^' then

begin

inc(b[ord(st[j-1])],ord(st[j+1])-ord('0')-1);

inc(j);

end;

end;

end;

for i:=1 to 256 do сокращаем дроби

if a[i]>b[i] then

begin

a[i]:=a[i]-b[i];

b[i]:=0;

end else begin

b[i]:=b[i]-a[i];a[i]:=0;

end;

end;

procedure out;

var i:integer;

p:boolean;

begin

assign(output,'output.txt'); rewrite(output);

p:=false; по этой логической переменной узнаем

будет ли в числителе 1 или нет

for i:=1 to 256 do

if a[i]<>0 then если буква с кодом i есть в числителе

begin

if p then write('*');

p:=true;

write(chr(i)); выводим букву

if a[i]>1 then write('^',a[i]); если показатель степени >1 печатаем

end; ^ и показатель степени

if not p then write('1'); если в числителе нет букв, то печатаем 1

writeln;

p:=false; то же самое в знаменателе

for i:=1 to 256 do

if b[i]<>0 then

begin

if p then write('*');

p:=true;

write(chr(i));

if b[i]>1 then write('^',b[i]);

end;

close(output);

end;

begin init; solve; out;end.

задачинамассивы