програмирование
May 11, 2020

Вид производной многочлена

Это задача из курса: "Многопоточное программирование на C/C++" (stepik.org)

Задача простая - найти производную многочлена. Многочлен может быть большой, но только с неотрицательными целыми степенями и целыми коэффициентами. Подумайте, каким образом его лучше представить в памяти? Вывод должен быть без пробелов и в порядке убывания степеней, хотя ввод этому правилу может не удовлетворять. Также на ввод может быть подан многочлен с неприведенными слагаемыми.

Sample Input 1: x^2+x

Sample Output 1: 2*x+1

#include<iostream>
#include<map>
#include<string>
#include<sstream>
#include<regex>

std::string derivative(std::string polynomial) {
	std::regex m("[+]?([-]?[0-9]*)[\\*]?(x?)[\\^]?([0-9]*)");
	std::smatch sm;
	std::map<int, int> pow_k;
	
	while(regex_search(polynomial, sm, m) && polynomial.size() > 0)
	{
		int k = atoi(std::string(sm[1]).c_str());
		int pow = atoi(std::string(sm[3]).c_str());
		if (std::string(sm[2]) == "x") 
		{
			if (pow == 0) pow = 1;
			if (k == 0) k = 1;
			if (std::string(sm[1]) == "-") k = -1;
		}
		pow_k[pow] += k;
		polynomial = sm.suffix();
	}
	
	std::ostringstream result;
	auto begin = pow_k.rbegin();
	auto end = pow_k.rend();
	auto gets = [](int pow, int k){
		std::ostringstream member;
		member << k * pow;
		if (pow > 1) member << "*x";
		if (pow > 2) member << '^' << pow-1;
		return member.str();
	};
	if (begin != end)
	{
		result << gets( begin->first, begin->second );
		++begin;
	}
	for(; begin != end; ++begin)
	{
		if ( begin->first == 0 ) continue;
		if ( begin->second > 0 ) result << '+';
	        result << gets( begin->first, begin->second );
	}
	return result.str();
}

Пришлось немного поработать с регулярными выражениями