<ПРЕД Задача:
СЛЕД>
Задачу решили 3 пользователя: UdH-WiNGeR, defrager, Dest.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Приведение к общему знаменателю

Time limit = 4 секунд(ы)

Дано выражение, состоящее из многочленов от переменной x, операций умножения, сложения вычитания и деления.

Необходимо привести его к виду

"p(x)/q(x)" или "p(x)" или "0",

где p(x) и q(x) многочлены с целыми коэффициентами и НОД(p(x), q(x) ) == 1.

Вход. Слово из языка, порождаемого грамматикой (S — начальный символ грамматики):

 S ::=  NUMBER 
 	| R ( ('+' | '-')  R)*
 NUMBER := <целое число, по модулю не превосходящее 10000>
 PNUMBER := <положительное число, менее 1000>
 R ::= A ('/' A)?
 A ::= NUMBER 
	| 'x' ('^' PNUMBER)?
	| '(' NUMBER ')' 
   	| '(' C (('+' | '-') C)* ')'
 C ::=  (NUMBER '*')? 'x' ('^' PNUMBER)? 

Примеры слов, выводимых из символа S:

 1, --3+45--6,  -x/(2*x),  x^100/x^11, 13/x + x2 — x/(x-1), (13*x-2)/(26*x-4)

Длина входного слова менее 1000 символов. Известно, что во время приведения численные коэффициенты в многочленах не превосходят 2000000000.

Входное выражение состоит не более, чем из 25 слагаемых (выражений, выводимых из R).

Приоритеты операций "*" и "/" одинаковы. Приоритеты операций "+" и "-" одинаковы и имеют приоритет меньше, чем операции '*' и '/'.

Операции '+', '-', '/', '*' левоассоциативны. Например, в выражении a-b-c (где a, b, c — некоторые выражения, выводимые из R или A) порядок выполнения операции задаётся следующей расстановкой скобок: ((a-b)-c).

Известно, что в процессе приведения деления не ноль не возникает.

Выход. Если после приведения к общему знаменателю получается 0, следует вывести "0". Если знаменатель равен 1, то следует вывести многочлен в скобках: "p(x)".

Иначе следует вывести выражение вида "(p(x))/(q(x))" без пробелов. Мономы в многочленах следует перечислять от старшей степени к младшей. Коэффициент при старшем члене знаменателя должен быть положительным. Если численный коэффициент монома равен 1 или -1, то его писать не нужно. Также не следует писать степень 1 у переменной x.

Вход#1
1/x + x
Выход#1
(x^2+1)/(x)

Вход#2
(1+x)/(x^2-1)+1
Выход#2
(x)/(x-1)

Вход#3
(-x^4--1)/(1+x^2+x+x^3)
Выход#3
-x+1

Вход#4
x+x-3*x-1/(5*x)
Выход#4
(-5*x^2-1)/(5*x)

Вход#5
1-1/x^17+(x^13-1)/(x^26-1)
Выход#5
(x^30+2*x^17-x^13-1)/(x^30+x^17)

Автор:
Артем Ворожцов
25 ноября 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.224.197.86