3

So I have a polynomial addition problem like the one below:

(1*x+2*x^3-1*x+7)+(1+1*x^2-1*x+1*x^4)

I need to figure out how to extract the numbers for the coefficients and exponents and enter them into a dynamically allocated 2D array (from here I can sort them and add them together before outputting the answer).

I am pretty lost on how to do this because the polynomials can be in any order of degrees and include any amount of terms. I can dynamically allocate them after I extract all of the numbers. The part I need help on is:

  • Extracting all of the numbers
  • Differentiating between them to see if it is a coefficient or an exponent
  • Allowing this to happen for any number of terms

If anyone could answer this or at least point me in the right direction it would be appreciated.

Ali
  • 3,373
  • 5
  • 42
  • 54
proCrow
  • 29
  • 1
  • 5

2 Answers2

2

Your problem looks like its parsing and evaluation.

  • Step1: You need to parse the string assuming an infix expression, so that you can pull out the coefficient

  • Step2: push those coefficients into a vector/deque etc to perform the polynomial calculation.

Here are some good examples:

Evaluating arithmetic expressions from string in C++

What is the best way to evaluate mathematical expressions in C++?

Community
  • 1
  • 1
Martein Txz
  • 178
  • 8
0

To extract coefficients from a string you need to create a parser. You can use special library like boost.spirit, you can use special tool which builds parsers like Flex, or you can make your own manually using regular expressions or not.

To store coeficients you can use std::vector<int> using indexes as power of x, so for 1*x+2*x^3-1*x+7 your vector would have data:

{ 7, -1, 0, 2 } // 7*x^0 + -1*x^1 + 0*x^2 + 2*x^3

then you do not need to sort them to add coefficients. To store all polynoms you would use std::vector<std::vector<int>> accordingly.

Slava
  • 43,454
  • 1
  • 47
  • 90