split string S

[onetwo12]

How can I split string S into substring S[i]? Also substring S[i] should set some number a[i].
Should I use strtok to split the string?

[seeplus]

As a c++ example of using strtok():

#include <iostream>
#include <cstring>

int main()
{
	char str[] {"qwe:asd:zxc"};

	for (auto elem = std::strtok(str, ":"); elem; elem = std::strtok(NULL, ":"))
		std::cout << elem << '\n';
}

qwe
asd
zxc

But is this a C++ question using std::string or a c-style null-terminated string - or a C question?

[onetwo12]

Thank you. I know how strtok works.

But is this a C++ question using std::string or a c-style null-terminated string - or a C question?

C++

[onetwo12]

For example, to split string:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main ()
{
  vector<string> arr;
  string str ("Hello; How; are you");
  string delim("; ");
  size_t prev = 0;
  size_t next;
  size_t delta = delim.length();

  while( ( next = str.find( delim, prev ) ) != string::npos ){
    string tmp = str.substr( prev, next-prev );
    cout << tmp << endl;
    arr.push_back( str.substr( prev, next-prev ) );
    prev = next + delta;
  }
  string tmp = str.substr( prev );
  cout << tmp << endl;
  arr.push_back( str.substr( prev ) );

  return 0;
}

So how can I get a[i] for string[i]?

[doug4]

What is a[i]?
What is string[i]?

Your code has a vector called arr which, by its name, suggests it is equivalent to a in your question.

Your code has a string called str which, by it name, suggests it is equivalent to string in your question.

I have no idea what you mean by getting a[i] for character string[i].

Your question is not clear. Maybe you can reword it to explain what you are looking for. Give us an example of one solution that you are looking for.

[seeplus]

To split a string on a delimiter and ignore leading white-space - and create a vector, then consider:

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

int main()
{
	const std::string str {"Hello; How; are you"};

	std::vector<std::string> words;
	std::istringstream iss(str);

	for (std::string s; std::getline(iss >> std::ws, s, ';'); words.push_back(std::move(s)));

	for (const auto& w : words)
		std::cout << w << '\n';

	std::cout << '\n';
}

What is meant by a[i] for string[i] ?????

[onetwo12]

What is a[i]?
What is string[i]?

What is meant by a[i] for string[i] ?????

Now I have(version with strtok is not correct):

#include <iostream>
#include <cmath>
 
using namespace std;
 
int StrToInt(string b) {
         int l, M;
         l = b.length();
         M = 0;

         for (int i = 0; i < l; i++) {
              M += (b[i] - '0') * pow(10, l-i-1);
         }
         return M;
}
 
int main() {
     int N; 
     string a; 

     cout << "enter S: ";
     getline(cin, a);
     N = StrToInt(a);
     cout << "number: " << N << endl;
     system("pause");

     return 0;
}

[lastchance]

If x<=1 then you will minimise the polynomial by splitting after every single digit.

The problem arises when x > 1 ...

[lastchance]

Really not sure if this is correct for x > 1 ...

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;


void minPoly( const string &str, double x )
{
   vector<double> coefficients;
   if ( x <= 1.0 )
   {
      for ( int i = 0; i < str.size(); i++ )
      {
         int a = str[i] - '0';
         cout << a << " ";
         coefficients.push_back( a );
      }
   }
   else
   {
      double L = 0, R = stod( str ), tenf = pow( 10.0, str.size() - 1.0 ), xn = 1.0;
      
      for ( int i = 0; i < str.size(); i++ )
      {
         int a = str[i] - '0';
         cout << a;
   
         L = 10.0 * L + a;
         R -= tenf * a * xn;
   
         if ( ( tenf - 1.0 ) * L > R / xn * ( x - 1.0 ) )
         {
            coefficients.push_back( L );
            L = 0.0;
            R *= x;
            xn *= x;
            cout << " ";
         }
         tenf /= 10.0;
      }
      coefficients.push_back( L );
   }
   cout << '\n';

   double poly = 0.0, xn = 1.0;
   for ( double c : coefficients )
   {
      poly += c * xn;
      xn *= x;
   }
   cout << poly << '\n';
}


int main()
{
   string str;
   double x;
   cout << "Enter string: ";   cin >> str;
   cout << "Enter x: ";        cin >> x;
   minPoly( str, x );
}

Enter string: 314159
Enter x: 0.5
3 1 4 1 5 9 
5.21875

Enter string: 314159
Enter x: 3.5
3 14 15 9
621.625

[onetwo12]

Really not sure if this is correct for x > 1 ...

Thank you very much! It seems to me that it works for x>1 (I checked).

I tried to solve it and I found task like task below is.

Given a segment (stick) [0, N], which needs to be cut at the marked places L[1], L[2], ..., L[k]. The numbers N, L[i] are natural numbers, 1 <= N <= 1,000,000, 1 <= k <= 200, 0 <L[i] <N. The numbers L[i] are different. At a time, we can cut one segment into two and pay for this a price equal to its length. Make cuts in the marked places, paying the minimum price for this.
Input. The first line of the input file contains the length of the stick N and the number of cutting points k. The second line contains the coordinates of the cutting points L[1] L[2] ... L[k].
Output. Output the cutting pattern in the first line in any format. In the second line, output the minimum price for sawing.

What can you say about it? It sееms to me that It is the same task.

#include <stdio.h>
#include <sys/types.h>
#include <iostream>
#define K 202
#define INFTY INT_MAX

int k, n;
int a[K][K];                                         
int l[K];                                            

void print_brackets(int start, int end);              

int main(int argc, char* argv[]) {
   int i, j, m, k, n;
   std::cin >> n >> k;

   l[0] = 0;                                         
   for(i = 1 ; i <= k ; i++) std::cin >> l[i];      
   l[++k] = n;                                     

   for(i = 0 ; i <= k; i++) a[i][i] = a[i][i+1] = 0;  

   for(m = 2; m <= k ; m++)                           
      for(i = 0 ; i + m <= k ; i++) {
         int L = l[i+m] - l[i];
         a[i][i+m] = INFTY;
         for(j = 1 ; j < m; j++)
            if(a[i][i+m] > a[i][i+j] + a[i+j][i+m])
               a[i][i+m] = a[i][i+j] + a[i+j][i+m];
         a[i][i + m] += L;
      }

   print_brackets (0, k);
   putc('\n', stdout);

   std::cout << a[0][k];
   system("pause");
   return 0;
}

void print_brackets(int start, int end) {
   int L = l[end] - l[start];
   int i, j, m;
   if(end - start <= 1){
      for(i = start ; i < end; i++)
         std::cout << l[i];
      std::cout << l[end];
   }

   else
   for(j = 1 ; j  < end - start ; j++  )
      if(a[start][end] == a[start][start+j] + a[start+j][end] + L) {
         std::cout << "( ";
         print_brackets(start, start+j );
         std::cout << ", ";
         print_brackets(start+j, end ) ;
         std::cout << " )";
         break;
      }
}

[onetwo12]

double L = 0, R = stod( str ), tenf = pow( 10.0, str.size() - 1.0 ), xn = 1.0;

lastchance, can you explane what means L, R, tenf, xn?

[lastchance]

For the ORIGINAL problem:

L - Left (i.e. the polynomial to the left)
R - Right (i.e. the polynomial to the right)
tenf = 10^f-1 (where f is the degree of the polynomial; it's the effective value of a lead coefficient)
xn = xⁿ - a current power of x

Don't ask me to reproduce the maths - I think in peculiar ways.

The code looked at the consequence of putting a cut at a specific point, and opted for the smaller.

If x <= 1 it is easy to prove that minimisation is achieved by cutting everywhere.
If x > 1 ... it's difficult to see. I couldn't prove that it works in this case, although it seems plausible. I've checked it for one or two small polynomials; only you can tell me if it works for larger ones.


BTW - my code has nothing to do with dynamic programming and, as far as I can see, is completely unrelated to the second problem which you posed.

[onetwo12]

For the ORIGINAL problem

Thank, I understood.

If I will solve this task with the help of dynamic programming should I take this logic?

For example I have S = 12345

s0 = "1", s1 = "2345"
s0 = "1", s1 = "2", s2 = "345"
s0 = "1", s1 = "23", s2 = "45"
...
s0 = "1", s1 = "2", s2 = "3", s3 = "45"
s0 = "12345"

[jonnin]

cut one segment into two and pay for this a price equal to its length

sorry, what length, there are 2 items now. The total? the piece cut off?

DP may work.
c++ strings or not, sometimes it pays to barbarian these kinds of problems.
eg struct (char*, int) where char* is the start location, int is the length, and you don't fool with actual substrings or any of that just leave the data in place and simulate the chopping.