How do I extract integers from a string?

[millerjacob49]

I am attempting to write a program in order to solve linear equations of various formats ("5x-8=2" or "5x+5+5x=15"). I am using code written on this forum http://www.cplusplus.com/forum/beginner/34039/
However, I don't understand how I can take a user input in the form of a string, and convert it into a usable form with the following code?

 #include <iostream>

struct VAR{
	float i;
};

struct LINE{//k*x+a
	float a, k;
	VAR* x;

	LINE(){}
	LINE(int a) : a(a), k(0), x(0) {}
	LINE(VAR& v) : a(0), k(1), x(&v) {}
};

LINE operator + (LINE A, LINE B){//assumes that A.x == 0 or B.x == 0 or A.x == B.x
	LINE R;
	R.a = A.a + B.a;
	R.k = A.k + B.k;
	if(A.x) R.x = A.x;
	else R.x = B.x;
	return R;
}

LINE operator - (LINE A, LINE B){//same as +
	LINE R;
	R.a = A.a - B.a;
	R.k = A.k - B.k;
	if(A.x) R.x = A.x;
	else R.x = B.x;
	return R;
}

LINE operator * (LINE A, LINE B){//assumes that A.x == 0 or B.x == 0
	LINE R;
	R.a = A.a * B.a;
	R.k = A.k * B.a + B.k * A.a;
	if(A.x) R.x = A.x;
	else R.x = B.x;
	return R;
}

LINE operator / (LINE A, LINE B){//assumes that B.x == 0
	LINE R;
	R.a = A.a / B.a;
	R.k = A.k / B.a;
	R.x = A.x;
	return R;
}

void operator == (LINE A, LINE B){
	LINE C = A - B;
	C.x->i = -C.a/C.k;
}

int main(){
	VAR x;
	5 == (2 + (x-7)*10)/2;

	std::cout << "x = " << x.i;
	std::cin.get();

	return 0;
}

This is a function I'm attempting to use but I don't know how to extract a integer such as "10" or "100" since it is multiple digits.

void spliteq(string s) {

	string s1 = s.substr(0, s.find('='));
	string s2 = s.substr(s.find('=') + 1, s.size() - s1.size());
	cout << s1 << endl;
	cout << s2;
}

[jonnin]

you are on the right track, you have to locate the integers and parse them out, then you can use stoi to make them integers again.

first thing to do is decide what numerical formats you are going to allow.
lets start with unsigned integers.
for that you can iterate the string, until you find something that trips isdigit() and mark that location as the start of your substring. Then keep going until you find something that is not a digit or you hit the end of the string. Then split out the substring and stoi() it.

then allow signed integers; now you have to handle +- symbols (few use the +, but its possible, you can disallow it if you like but you have to deal with negative).

then you have to see if you allow scientific notation eg 1.234e7 format, or hex, or anything else weird. if you decide to allow doubles, you have to handle leading decimal points, etc. Whatever format you decide to allow, you have to support numbers in that format for every possible pattern.

[Ganado]

In general, you need to form an "expression tree" of the equation. One algorithm to assist in doing this (among others) is called the Shunting Yard algorithm.
But if you're only looking to parse data of a particular, limited form, it can be easier.

e.g. Begin at the start of the expression, find the index of the first operator (+ or -), get the substring between the start of the string and the first operator. Then continue to find the next substring starting from the previous operator. Repeat this, isolating the numbers before teh variable x, if any.

// Example program
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cctype>
using namespace std;

void spliteq(const string& s, string& out_LHS, string& out_RHS) {
	out_LHS = s.substr(0, s.find('='));
	out_RHS = s.substr(s.find('=') + 1, s.size() - out_LHS.size());
}

size_t find_operator(const std::string& expression, size_t start_index = 0)
{
    string supported_operators = "+-";
    for (char ch : supported_operators)
    {
        size_t op_index = expression.find(ch, start_index);
        if (op_index != std::string::npos)
            return op_index;
    }
    return std::string::npos;
}

vector<int> extract_integers(string expression)
{
    vector<int> integers;
    
    size_t prev_search_end = 0;
    for (size_t i = 0; i < expression.length(); i++)
    {
        size_t op_index = find_operator(expression, prev_search_end);
        if (op_index != std::string::npos)
        {
            // operator found - produce substring of term
            string substr = expression.substr(prev_search_end, op_index - prev_search_end);
            
            // if there's a non-number at the end, remove it, e.g. 3x --> 3
            if (!isdigit(substr.back()))
            {
                substr.pop_back();
            }
            integers.push_back(stoi(substr));
            
            prev_search_end = op_index + 1;
        }
    }
    
    // account for last remaining term
    {
        string substr = expression.substr(prev_search_end);
    
        // if there's a non-number at the end, remove it, e.g. 3x --> 3
        if (!isdigit(substr.back()))
        {
            substr.pop_back();
        }
        integers.push_back(stoi(substr));
    }

    return integers;
}

int main()
{
    string input = "5x+6+7x=15";
    
    string equation_LHS;
    string equation_RHS;
    spliteq(input, equation_LHS, equation_RHS);
    cout << "Split: " << equation_LHS << " = " << equation_RHS << '\n';
    
    vector<int> integers = extract_integers(equation_LHS);
    for (int i : integers)
    {
        cout << i << '\n';   
    }
}

Output:

Split: 5x+6+7x = 15
5
6
7

I didn't really do any error checking there, because it's just an example to show you that it's possible.

This extracts integers like you asked, but of course a lot more is needed to actually process the equations that go along with those integers. A general equation simplifier + solver is going to be a lot more work, but it's a good project to try.

If your equations are only constant + linear terms, you could group the linear terms with the constant terms, such that you have Ax + B = C, then do some math to get Ax = (C - B), then x = (C - B)/A.

[millerjacob49]

Thanks for the help guys. So I see how to extract these now, I'm not even sure how to ask my question from here. After parsing, I don't understand how to keep signs (division, addition, etc) with the integers they will go with, as well as keeping the variable with its coefficient?

[markyrocks]

I'm actually working on this with you bc it seems like a good project to play with. Currently having issues myself. But the way I've kept a a number and a operator together is using a vector of pairs.

My method involves breaking the whole string into individual chars, then from there separating out the operators from the numbers and then turning the number chars to floats combining the real numbers with their operators in a

std::vector>pair<float,char>> pairFlCh;

There's other ways to do it but like the idiot proof way to turn char numbers into their int cousins is just doing if else if comparison and conversion.

Like

char zero ='0';
int z;
if (zero == '0'){z=0;}

I was actually getting pretty close but then I ran into a bunch of stupid issues and then I managed to break all kinds of stuff. Working with iterators is a pita. Part of the reason my attempt got complicated in a hurry is bc I'm attempting to implement parentheses handling which adds a whole other can of worms. That and taking into account order of operations in general you can't just clack off the solving of anything from left to right. I'm just thinking about using decimals and using the dot as an operator (not overloading). Also have to take into account multi digit numbers. During the parsing if the the number is more than 1 digit just multiply it by 10 and add the second and so on. This is getting real out of hand quickly.

[jonnin]

After parsing, I don't understand how to keep signs (division, addition, etc) with the integers they will go with, as well as keeping the variable with its coefficient?

that is where the expression tree idea mentioned above is useful.

5x+5+5x=15

you need to get that into your code as
5*x+5 + 5*x
coefficients are an omitted multiply shorthand, and you can't have that in your code, you will find it easier to make that multiply explicit.

and to solve that you may want to put it in a reduced form or insist the user put it in reduced.
10*x+5, in other words, or only ONE term per power of X.

[markyrocks]

you need to get that into your code as 
5*x+5 + 5*x

That was something else I was playing around with in regards to parentheses. Figuring out if a number was directly b4 or after a parenthesis and inserting a * in between

[dhayden]

This is potentially a very complex program. Since this is the beginners forum, it makes me think that the actual problem is easier. Can you post the text of the assignment?

[millerjacob49]

So the assignment is to create a program where a user types in a linear equation(as a string) and the answer is displayed.
Example interactions are given:

User: 4x - 3 = 1
Program: x = 1

User: 4x + 3 = 4x
Program: No Solution

User: 9 + 2(3x + 2) = 8x
Program: x = 13/2 (x = 6.5)

etc..

Is there any sort of data type where I can store an operator? Or do I have to store these as a char and then use a comparison to "convert" it?

[dhayden]

Off hand, I'd say that your data type is a linear expression:

// class to represent m*x + b
class Linear {
    double m, b;
};

As you read and parse each side of the equals sign, you update the Linear instance that represents the value on that side. Once you're done parsing, you solve the equation.

I'd start with code to parse a linear expression.
Then parse both sides of an equals sign.
Then add code to solve the equation.
The add code to parse an equation containing parentheses.

[markyrocks]

you can check out what i was doing here. http://www.cplusplus.com/forum/beginner/270618/

by no means am i saying that this is the correct way to do anything or that its even good for anything. Maybe it will help you maybe it will make you laugh at how shitty it is lol. Its not exactly what youre doing but its my version of a halfassed calculator. it currently only adds and subtracts.

edit now it seems to be able to do multiplication and division based on order of operations. (with single digits, getting multiple digits working shouldn't be a big deal, i already have the framework for it just haven't let it rip yet)

[jonnin]

your assignment's format is simple, but who knows what the professor may test it with.

you store operators as either a code or a letter (which is the same thing, really) and use a condition, yes.
eg if (letter == '+') something = a+b;
else if(letter == '-') ...
and so on.

User: 4x - 3 = 1
Program: x = 1

User: 4x + 3 = 4x
Program: No Solution

what happens if you read it backwards?

1
-3 becomes +3, so 4.
4x becomes 1/4 so 1 again (4*1/4 = 1)
x = 1.

4x + 3 = 4x
x on both sides, reformat. subtract 4x from both sides to get numbers only on right hand side.
3 = 0
^^ detect invalid.

as best as I can tell, your 'easy homework problem' answer is to reformat the equation into
variables = constant format, and then resolve it. I am not sure if going backwards helps or not because the input is not presented in usual useful math formatted structure. But if you can get it into that format, you are done.
So, maybe, as a first step, can you rearrange it just as symbols so that terms with a variable in them are on the left and the right is a constant number? Basically that means removing all constant terms (eg +7 or -1/18 ... stuff with no x in it) from the left, adding them to the right, and then similar logic, remove all terms with a variable on the right, put it back on the left. Then you need to group same exponent on variables, so 3x+2x = 5x and total up the constants (3 + 11 right side change to 14)
you can do that with an inefficient pair of loops, seek and move followed by seek and combine. I do not know your skill level, though. Is this a class where you are expected to know c++ pretty well by now and should be writing a limited equation parser or not? The parser is the right way to do it, but if this is your first programming class, you may need to simplify it.

[Ganado]

Yep, I know this is the easy part and not the part you're struggling with, but once the input is boiled down into a reasonable format, it isn't hard to process all the possibilities of a linear equation:

// Example program
#include <iostream>
#include <limits>
#include <cmath>

// class to represent m*x + b
struct Linear {
    double m, b;
};

// mx + b == nx + c
// mx == nx + (c - b)
// x(m - n) == (c - b)
// x = (c - b) / (m - n)
double solve(const Linear& expL, const Linear& expR)
{
    double m_diff = expL.m - expR.m; // (m - n)
    double b_diff = expR.b - expL.b; // (c - b)
    
    if (m_diff == 0.0 && b_diff == 0.0)
    {
        return std::numeric_limits<double>::infinity();   
    }
    if (m_diff == 0.0) // note: for non-integers, exact comparison with 0 can be inexact.
    {                  // Perhaps surround this with an epsilon
        return std::numeric_limits<double>::quiet_NaN();
    }

    return b_diff / m_diff;
}

char signchar(double num)
{
    return (num >= 0.0) ? '+' : '-';
}

std::ostream& operator<<(std::ostream& os, const Linear& expr)
{
    if (expr.m != 0.0)
    {
        os << expr.m << 'x';
        
        if (expr.b != 0)
        {
            os << ' ' << signchar(expr.b) << ' ' << std::abs(expr.b);   
        }
    }
    else if (expr.b != 0)
    {
        os << expr.b;
    }
    else
    {
        os << 0;   
    }

    return os;
}

void display(const Linear& linA, const Linear& linB)
{
    double x = solve(linA, linB);
    
    std::cout << linA << " == " << linB;
    if (std::isnan(x))
    {
        std::cout << ", No solution\n";
    }
    else if (std::isinf(x))
    {
        std::cout << ", Infinite solutions\n";   
    }
    else
    {
        std::cout << ", x = " << x << '\n';
    }
}

int main()
{
    display( {4, -3}, {0,  1} );
    display( {4, -3}, {0, -1} );
    display( {4,  3}, {4,  0} );
    display( {0,  3}, {0,  3} );
    display( {4,  3}, {4,  3} );
    display( {4,  3}, {0,  0} );
}

4x - 3 == 1, x = 1
4x - 3 == -1, x = 0.5
4x + 3 == 4x, No solution
3 == 3, Infinite solutions
4x + 3 == 4x + 3, Infinite solutions
4x + 3 == 0, x = -0.75

I agree with dhayden's steps.

Edit: Also note, that if for some reason it turns out the using NaN and Inf for this purpose is ambiguous, you could also return a {x, enum} pair where the enum could be {Valid, InfiniteSolutions, NoSolutions}.

[millerjacob49]

I stumbled my way through the assignment and got a (very messy) program working. It was through a mixture of suggestions posted here, so again I appreciate everyones help, I was literally pulling my hair out.

If anyone is interested to see what I came up with after nearly 24 hours of work I'll post the code when I get home.

Basically my largest issue was parsing the string but I figured that out, after parsing, I populated two vectors, one with integers with no variables and the other with integers that had 'x' in front. From here, I simply solved the add/subtract within the vectors, and then divided the variable vector from the integer vector.

Edit: I abandoned the first set of code in my initial post (with the structures and LINE operators) that I found from a different post.