Question

Using only core C++ (no special libraries, except STL vector or string if you want), write a C++ program that allows a user to input a string and

(a) Checks if the expression is a valid polynomial. Parentheses or negation are not allowed. Spaces should be ignored. E.g.,

the following are valid i. n^2+2*n+5 ii. 2*n + 4.54* n^5 +4 +5*n

and the following are invalid iii. n^3n iv. n^4.2 v. 5n vi. n^3 -3*n

if an input is given with a Parentheses or a negative like (n^3 - 3*n) should be ignored. Also for 5n to be valid it has to be 5*n.

(b) If the polynomial is valid, outputs its big-O notation. E.g., for (ii) above it is O(n^5).

Just needs something to check for a polynomial and if it is a valid polynomial to cout a bigO

Thanks

If any confusion, ill answer in the comments.

Answer 1

Solution :-

In the question, we are asked to find if the polynomial expression that we are being given is valid or not. If valid then we have to give the Big O notation that is the complexity in which the polynomial can be solved or in a simple way, the highest power of the polynomial.

Conditions when the expression can be stated as invalid :-

1. If there is a negation, or a negative integer somewhere in the expression, then the polynomial is not valid. n - 1

2. If there is any parentheses, then the expression is not valid. (2 + 6 * n^3)

3. If the variable is raised to the power of a number that is not an integer ( like decimal ), then the expression is not valid. For example n ^ 4.2 is not valid, as n is raised to the power of a number that is not an integer.

4. If there is no operator in between the polynomial variable (n or any lower case alphabet) and a number, then the expression is not valid. For example, n5.

5. If there is more than one term for a single degree, then the expression is invalid. For example, n^2 + 3*n^2 + 5 ,here there are two terms for the degree 2. The option (ii) in the question will also be considered as invalid.

Basic observations that is needed to solve the problem :-

1. So basically, we need to find if there is any negative sign or any parentheses in our expression. If yes then stop the program by prompting that the expression is invalid.

2. Secondly we need to check if there is any decimal sign which is power of a variable, if yes then return by prompting the expression invalid and if there is any operator in between the variable and any number.

3. To find the complexity of the expression we need to find the largest integer among from the expression that is an integer.

4. We need to check every integer value of the exponents and see if there is any repetition. If yes it means there is more than one term for a single degree, then the expression is invalid.

The source code is given below with the functionalities of each of the if statements, while loops and the printing statements.

#include <bits/stdc++.h>

using namespace std;

vector<int> getexponents(string s)
{
        int length = s.length();
        vector<int> vi;
        int number = 0;  // number is the variable where each power of the variable is stored and compared to max if it is the largest or not. 
        int j;
        int c = 0;
        for(int i = 0; i<length; i++)
        {
                if(s[i] == '^')   // loop to check and find if there is any exponent greater than 1
                {
                        j = i;
                        j++;
                        while(s[j] == ' ' && j<length)  // going till the end of the index from where the exponent value starts ignoring all the white spaces.
                                j++;
                        
                        while(j < length && ((int(s[j]) >= 48 && int(s[j]) <= 57)))  // locating the pointer till the end of the exponent value.
                                j++;
                        
                        
                        i = j-1;
                        
                        j--;
                        c = 0;
                        while(j >= 0 && (int(s[j]) >= 48 && int(s[j]) <= 57)) // converting the exponent value form character to integer type.
                        {
                                number += ( ((int)(s[j]) - 48) * pow(10, c) );  
                                c++;
                                j--;
                        }
                        
                        vi.push_back(number);
                        
                        number = 0;
                }
                else
                if(int(s[i]) <= 122 && int(s[i]) >= 97)  // for the exponent value of 1.
                {
                        j = i + 1;
                        while(j<length && s[j]==' ')
                                j++;
                        if(j >= length)
                                vi.push_back(1);
                                
                        if(j < length && (s[j] == '*' || s[j] == '+'))
                                vi.push_back(1);
                }
                else
                if(int(s[i]) <= 57 && int(s[i]) >= 48) // for the constant value where exponent of n is 0
                {
                        c = i;
                        bool x = false, y = false;
                        j = c + 1;
                        while(j<length && (s[j]==' ' || (int(s[j]) >= 48 && int(s[j]) <= 57) || s[j] == '.'))
                                j++;
                                
                        if(j < length && (s[j] == '+' ))
                                y = true;
                        else
                        if(j >= length)
                                y = true;
                        
                        i = j-1;
                        j = c - 1;
                        
                        while(j>=0 && s[j]==' ')
                                j--;
                                
                        if(j >= 0 && s[j] == '+')
                                x = true;
                        else
                        if(j<0)
                                x = true;
                        
                        if(x && y)
                        {
                                vi.push_back(0);
                        }
                }
                
        }
        
        return vi; // finally returning the vector containing all the exponents.
}

bool isvalid (string s) // to check whether the expression is invalid or not
{
        int length = s.length(); // the length of the expression
        int j;                      
        for(int i = 0; i<length; i++)  // traversing through the expression to see if the expression is invalid or not.
        {
                
                if(s[i] == '-' || s[i] == '(' || s[i] == ')')  // if any parantheses or negative sign is found then it is invalid
                        return 0;
                
                
                if(s[i] == '.')  // to check is the number having a decimal is a power of the polynomial variable or not.
                {
                        j = i - 1;
                        while((s[j]==' ' ||  (int(s[j]) >= 48 && int(s[j]) <= 57)) && j >= 0)
                                j--;
                        
                        if(j >= 0 && s[j] == '^')
                                return 0;
                }
                
                if(int(s[i]) >= 97 && int(s[i]) <= 122)  // if any * or ^ or + is missing or is not present in the side of the polynimial variable then it is an invalid expression.
                {
                        j = i-1;
                        while(j >=0 && s[j] == ' ')
                                j--;
                                
                        
                        if(j >= 0 && (s[j] == '^' && s[j] != '+' && s[j]!= '*')){
                                return 0;
                        }
                        
                        j = i+1;
                        while(j < length && s[j]==' ')
                                j++;
                                
                        if(j < length && (s[j] != '^' && s[j] != '+' && s[j]!= '*')){
                                return 0;
                        }
                }
        }
        
        vector<int> v;
        v = getexponents(s);
        
        sort(v.begin(), v.end()); // sort is an stl function which sorts in O(n log n) where n is the length of the vector.
        
        for(int i = 1; i<v.size(); i++) //
        {
                if(v[i] == v[i-1])
                        return 0;
        }
        return 1;
}

int findbigO(string s)  // function to find the Bif O value of the expression.
{
        int length = s.length();
        int max = 0;  // max contains the largest value present in the vector.
        
        vector<int> exp = getexponents(s);
        
        
        
        for(int i = 0; i<exp.size(); i++) // finding the maximum among the exponent values.
        {
                if(max < exp[i])
                        max = exp[i];
        }

        return max;
}

int main ()
{
        string s;
        cout<< "Enter the expression :";
        getline (cin >> ws , s);    // taking the expression as the input.
        
        cout<<endl;
        
        bool check = isvalid(s); // the function isvalid is called with the argument as the string that we took as input.
        
        if(! check)     
        {
                cout<< "The expression is invalid."<<endl;  // printing out the statement if the expression is invalid.
                return 0;
        }
        
        cout <<"The expression is valid."<<endl;  // Printing out if the expression is valid.
        int power = findbigO(s);  // calling the findbigO function to find the power of the expression.
        
                        
        cout<<"O (n ^ "<< power <<")";  // finally printing out the value of bigO.
        
        return 0;
}

Let's understand each of the part clearly.

isvalid( string s )

This function tells that if the expression that is given to us is valid or not.

1. Firstly it checks if there is any sign of ' ( ', ' ) ', ' - ' with the help of the if statement  if(s[i] == '-' || s[i] == '(' || s[i] == ')') and then returning 0 if the statement is true.

2. The expression can be invalid if there is a decimal power if the polynomial variable.

The if statement if(s[i] == '.'), finds the character ' . ' in the expression and if it gets the same then it ignores all the white spaces and the digits preceding it with the help of the statement while((s[j]==' ' || (int(s[j]) >= 48 && int(s[j]) <= 57)) && j >= 0) and finds for a different character which is not a white space or a digit or it stops if there is no more character left to check.

The index at which the ' . ' character is found, the value is stored in j and before checking for the different character we reduce j by 1 because we do not want to check for the same character where ' . ' is stored.

We will check if the character that we want to check is ' ^ ' or not, if yes then it is an invalid expression.

3. If any operator is missing between any number and the polynomial variable, which makes it invalid, then the expression is invalid.

The statement if(int(s[i]) >= 97 && int(s[i]) <= 122) does the work for the same. It checks of these is any other character beside +, ^ or * associated with the polynomial variable after ignoring all the white spaces with the statement while(j >=0 && s[j] == ' ') and while(j < length && s[j]==' ').

If we got any other character than +, ^ or *, then the expression is invalid.

4. When all the above conditions pass, then we go to check if there is more than one term for a single degree by calling the function getexponents and sorting the vector using stl's inbuilt sort function which takes O (n log n) time if there are n number of exponents are there.

After sorting it becomes easy for us to check if there is any exponent value which is repeating. If yes then the expression is invalid, else it is valid.

findbigO(string s)

The function findbigO(string s) finds the value for the Big O of a valid expression. It searches all for all the numbers after the character ^ and converts the expression which is in character into number which is then compared to find the maximum value.

length stores the length of the expression. number stores the value of each number before comparing it to the max value which stores the maximum value and is finally returned. The default value of max is 0.

The for loop for(int i = 0; i<length; i++) traverses the expression and finds for the character ' ^ ' and if it gets then it ignores all the white spaces and the digits to get to the end of the number from where the statement while(j >= 0 && (int(s[j]) >= 48 && int(s[j]) <= 57)) starts calculating the numerical value of the exponent.

After getting the value of exponent, every time it is compared to the max with the statement if(number > max). We get the maximum value of the exponents and then return the value.

getexponents(string s)

To get all the exponent values present in the expression for the polynomial variable, this function helps to get all those values and returns a vector containing the exponents.

For the exponents greater than 1, the expression will have the character ' ^ ' in it, hence we can take the character as the reference and find out the value of the expression. But for the exponents less than or equal to 1, we have to check all the characters if it only contains the constant value for which exponent is 0 and if it only contains ' n ', then the exponent is 1.

We push back all these values in the vector and return it.

In the main function, we take the input of the string with the help of getline (cin >> ws , s); as it helps to take a line as input even if a white space is present. The function isvalid is called by passing the string as the argument and getting the value in check. If check is 0 then the expression is invalid and if 1 then we find the BigO value by calling the function findbigO() and take the input in power which is then printed in the final statement.

Some screenshots of the working of the program.

Here the expression is 4 * n^3 + 3*n + 9 and the expression is valid. with Big O (3).

The expression is invalid as there is a - sign in the expression.

The expression is invalid as there is no operator in between n and 5.

Here the expression is n^5 + 3 + n*6 and the expression is valid. with Big O (5).

If any doubts or confusion still remains then I can definitely clear it in the comment box.

After the changes asked by the question provider :-

The time complexity of the program will change according to the changes asked. As we are now sorting all the exponents in the function isvalid() to find if there is an exponent which is common for two or more terms, which makes the complexity of the program O(n log n), where n = the numbers of exponent present in the vector. For the worst case, that is the large value of the length of expression, the complexity of the program will become O(n log n).

The source code has been changed and has been converted according to the new requirement.

Some new screenshots after the changes asked by the owner.

Here the degree of 2*n and 5*n are equal, hence the expression is invalid.

Here, the expression 3.6 * n^2 is equal to the expression n^2. Hence this is also invalid.

Here, there are 2 constants 14 and 4 which have a degree of 0 (n^0).