Скорее всего, Вам известно, что x(sin2x + cos2x)
− x = 0, а также что sin(2x) − 2 sin x cos x = 0. Но известно
ли Вам, что tan (2x)(x − x tan2x) − 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" иначе.
Пример входа
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
Пример выхода
Identity
Identity
Identity
Not an identity
РЕШЕНИЕ
синтаксический анализ
Для решения задачи достаточно
промоделировать вычисление выражения, заданного в виде обратной польской
записи, для нескольких наугад взятых значений x. Если для всех таких значений x
выражение будет равно нулю, то с большой долей вероятности можно утверждать,
что выражение тождественно равно нулю.
Пример
В первом примере задано выражение
(sin2x + cos2x) * x
– x, что тождественно равно нулю.
Разделим строку s
на лексемы. Разделителем является символ с.
vector<string> split(string s,char c)
{
vector<string> res;
int i = 0, j = s.find(c);
while(j >= 0)
{
if (s[i] != c)
res.push_back(s.substr(i,j-i));
i = ++j;
j = s.find(c,j);
}
if (i < s.size()) res.push_back(s.substr(i));
return res;
}
Набор лексем в обратной польской
записи задан в массиве строк tokens. Вычислим значение выражения в точке Value. Функция CheckIdentity возвращает
1, если полученное значение равно нулю
(0 в противном случае).
int CheckIdentity(vector<string> &tokens, double Value)
{
stack<double> s;
for(int i = 0; i <
tokens.size(); i++)
{
if (tokens[i] == "x") s.push(Value); else
if (tokens[i] == "sin")
{
double v = s.top(); s.pop();
s.push(sin(v));
} else
if (tokens[i] == "cos")
{
double v = s.top(); s.pop();
s.push(cos(v));
} else
if (tokens[i] == "tan")
{
double v = s.top(); s.pop();
s.push(tan(v));
} else
if (tokens[i] == "+")
{
double a = s.top(); s.pop();
double b = s.top(); s.pop();
s.push(a+b);
} else
if (tokens[i] == "-")
{
double a = s.top(); s.pop();
double b = s.top(); s.pop();
s.push(b-a);
} else
if (tokens[i] == "*")
{
double a = s.top(); s.pop();
double b = s.top(); s.pop();
s.push(a*b);
}
}
double Result = s.top(); s.pop();
if (fabs(Result) < 1e-7) return
1;
return 0;
}
Основная часть программы. Читаем
входную строку str, разбиваем ее на
лексемы (разделителем является пробел). Вычисляем значение функции, например,
во всех точках x от 1 до 2 с шагом
0.02. Если для некоторого значения x
результат окажется ненулевой, то заданная на входе функция не является
тождественно равной нулю.
while(scanf("%d ",&n),n)
{
gets(str);
vector<string> tokens = split(str,' ');
int flag = 1;
for(Value = 1; Value <= 2; Value += 0.02)
if(!CheckIdentity(tokens,Value))
{
flag = 0; break;
}
if (flag) printf("Identity\n");
else printf("Not
an identity\n");
}