Quadric equation parser using QRegExp

Question

I want to implement a parser for a quadric equation using regular expressions. I want to keep it as a console app. I done the regex and tested it in Debuggex. Currently I have 2 problems - I can't get the a,b,c from (ax^2+bx+c) and i want to add bash-like history with up and down arrows. Thanks in advance. My code:

#include <QCoreApplication>
#include <QRegExp>
#include <QString>
#include <QTextStream>
#include <QStringList>
#include <QDebug>
#include <cstdio>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    Q_UNUSED(a);

    QTextStream cin(stdin, QIODevice::ReadOnly | QIODevice::Text);
    QTextStream cout(stdout, QIODevice::WriteOnly | QIODevice::Text);

    const QString regexText = R"(^[-]?\d*x\^2\s*[+,-]\s*\d*x\s*[+,-]\s*\d*$)";

    while(true)
    {
        QRegExp regex(regexText);

        cout << "Enter an equation to solve or press EOF(Ctrl+D/Z) to exit." << endl;
        cout << "--> " << flush;

        QString equation;
        equation = cin.readLine();

        if( equation.isNull() )
        {
            cout << endl;
            cout << "Thanks for using quadric equation solver! Exitting..." << endl;
            return 0;
        }

        int pos = regex.indexIn(equation);
        QStringList captures = regex.capturedTexts();
        qDebug() << captures;
    }
}

Answer 1

I think you're looking to learn how to properly use Capturing groups, which debuggex isn't great at showing you the result of. I'd shoot for a regular expression more along these lines:

^(-?\d*)x\^2\s*([+-]\s*\d*)x\s*([+-]\s*\d+)?$

You can see it in action at RegExr, my preferred RegEx tool. Mouse over the highlighted matches to see what the groups have captured.

You can see that the parentheses essentially deliniate sub-expressions that can be extracted separately, and parsed for meaning. I've chosen to include the operation (+/-) so you can use it to parse the positive or negative nature of the coefficients. You'll see in the example data that it doesn't cover decimal coefficients, but neither did your original expression, and I think this answers the most pressing issue.

Decimals

Capturing a decimal is as easy as adding a snipped after every set of digits that you capture:

(?:\.\d+)?

Which optionally matches (without capturing) a literal period followed by some other digits. This turns your greater Regular Expression into:

^(-?\d*(?:\.\d+)?)x\^2\s*([+-]\s*\d*(?:\.\d+)?)x\s*([+-]\s*\d+(?:\.\d+)?)?$

Which, as you can see, allows the capture of decimal expressions. They still have to be in order (a shortcoming of regular expressions, but only when you're trying to do everything at once), but you've increased the number of problems you can solve.

Reordered

The next step is to deal with out of order expressions. You could do this in a single regular expression, but I recommend against it for a few reasons:

1. It's awful to read, and thus maintain
2. Doing it in a single RegEx makes it hard to exclude extraneous information.
3. Doing it in pieces solves the problem of multiple terms automagically (like x^2+x+x+2)
4. Doing it in pieces sets you up to capture higher order polynomials more easily.

1: Validation

The first basic step is to decide what a term looks like. For me, a term is an operator, followed by optional whitespace, followed a variable expression or a constant. OR:

[+-]\s*(?:\d+(?:\.\d+)?|\d*(?:\.\d+)?x(?:\^\d+(?:\.\d+)?)?)

It's a doozy, so I'll include the Debuggex Visualization.

Wrap your head around the way that expression works, because it's the basic unit for the next one:

^-?\s*(?:\d+(?:\.\d+)?|\d*(?:\.\d+)?x(?:\^\d+(?:\.\d+)?)?)(?:\s*[+-]\s*(?:\d+(?:\.\d+)?|\d*(?:\.\d+)?x(?:\^\d+(?:\.\d+)?)?))+$

When you see that one in Debuggex, it becomes clear that it's basically just the former expression repeated one or more times. I added some whitespace and gave the first one an optional negative instead of an operator, but it's essentially the same.

Now, there is some room missing here, to add a negative or subtract a positive number. (think, 3x+ -4x^2), but it's a minor change to the regular expression, so I think I'll move on. Match that regular expression against your line (trimmed, of course), and you can know you have a valid equation.

2. Extraction

Extraction is based off a single regular expression, modified to capture specific terms. It does require the ability to use a lookahead, which I must admit some Regular expression engines don't support. But Debuggex supports it, and I didn't find confirmation or denial of QRegExp, so I'm going to include it.

((?:^-?|[+-])\s*d*(?:\.\d+)?)

This is your basic Regular Expression. Used by itself, it will capture a number, with no regard as to wether it's a coefficient or constant. To capture a constant, add a negative lookahead to ensure it's not followed by a variable:

((?:^-?|[+-])\s*d*(?:\.\d+)?)(?!\s*x)

To capture a specific exponent, just match it, followed by space or another sign.:

((?:^-?|[+-])\s*d*(?:\.\d+)?)\S*x\^2(?=[\s+-])

To capture without an exponent, use a negative lookahead to ensure it's missing:

((?:^-?|[+-])\s*d*(?:\.\d+)?)\s*x(?!\^)

Although, personally, I'd prefer to capture all variable terms at once with this:

((?:^-?|[+-])\s*d*(?:\.\d+)?)\s*x(?:^(\d+(?:\.\d+)?))

Which has exactly two capturing groups: one for the coefficient, and one for the exponent.