eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Перевірка на ноль

Перевірка на ноль

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

Скоріш за все, Вам відомо що x(sin^2 x + cos^2 x) − x = 0, а також що sin(2x) − 2 sin x cos x = 0. Але чи відомо Вам, що tan(2x)(x − x tan^2 x) − 2x tan x = 0? Або чи повірите Ви в те, що sin (2x) − 2 cos x = 0?

Останнє твердження хибне, але не вірте нам. Вам слід написати програму, яка перевірить, чи спрощується заданий алгебраїчний вираз до нуля (всякий раз коли він визначний).

Вхідні дані

Складається з декількох тестів, кожний з яких міститься в одному рядку. Кожний тест починається цілим числом n - кількістю лексем, що описують формулу. Наступні n лексем задають формулу в оберненому польському запису. Запис задається наступним чином. Спочатку є порожній стек, та наступні команди маніпулюють його вмістом:

  • "x" заносить змінну x до стеку.

  • "sin", "cos" и "tan" замінюють верхній елемент стеку на значення його синуса, косинуса та тангенса відповідно.

  • "+", "-" та "*" замінюють два верхні елементи стека (a на вершині, за ним слідує b) на їх суму (b + a), різницю (b − a) чи добуток (b ∗ a) відповідно.

Вхідні дані коректні, результатом виразу є значення на вершині стеку. Довжина рядку не більша за 300 символів. Аргументами функцій можуть бути функції, тобто вираз вигляду x sin sin є допустимим, але рекурсія не буде заходити далі вказаного випадку. Вхід завершується рядком, в якому n = 0.

Вихідні дані

Для кожного тесту вивести в окремому рядку "Identity", якщо вираз тотожно дорівнює нулю, та "Not an identity" інакше.

Приклад

Вхідні дані #1
15 x sin x sin * x cos x cos * + x * x -
16 x sin x cos * x sin x cos * + x x + sin -
24 x x + tan x x tan x tan * x * - * x tan x * - x tan x * -
10 x x + sin x cos - x cos -
0
Вихідні дані #1
Identity
Identity
Identity
Not an identity
Джерело 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011