Function Plotter, Playing with design patterns

Introduction

Download the source code: SourceCode.zip

Imagine that you're developing an industrial program to control a universal testing machine, which one of its functions is to compress metals and measure the force throughout the experiment. Let's assume that a client comes to you and asks for computing the pressure from the formula 'P=F/A'. Easy peasy! We can implement this equation in our program in the blink of an eye. but what if other customers require different formulas? What happens if someone asks you to allow him to enter his formula dynamically into the application in runtime, while there can be countless equations defined? Well, to cope with situations like these (when you don't know the mathematical function definition at compile time), you will need a Function Evaluation Algorithm.

Function Plotter is a simple C++ (Qt) program which takes a mathematical function definition "f(x)" as it's input and illustrates it on a two-dimensional graph (x-y). The figure in below shows the program in runtime.

I've compiled this project on a 64-bit Linux machine. but since it is developed using Qt framework, there should be no problem with compiling on other operating systems like Windows or Mac. The source code is also available here.

Background

There exist a vast collection of function assessment algorithms. The most simple and trivial one which is also the basis of our program is explained expressively in here. We will also explain it in a quick way.

The evaluation algorithm is obvious and easy to implement, but the main issue is to find a practical way to implement enormous operators that can be used to form an equation. Beside elementary and basic arithmetic operators like ( +, *, ^ and etc), functions like 'sin' and 'log' can be constituted mathematical operations. This is why the primary focus of this project is on design patterns rather than the algorithm itself.

Designing the application

Quick review of the function evaluation algorithm

Ordinary logical formulae are represented in Infix notation that is characterized by the placement of operators between operands (like 2 + 3). This notation is human readable but since it can be ambitious, it necessitates the usage of parenthesis. It's also more difficult to parse by computers compared to Postfix notation (like 2 3 +). Therefore the overall steps are to:

1. Scan the input formula (Tokenizing the Infix notation)
2. Convert an Infix notation of the formula into Postfix notation.
3. Evaluate the Postfix notation.

Scanning the input formula

Different operators have different behaviors but all of them are presented to us as an input string, this is why being able to differentiate them is utterly essential. For example "x*sin(x)" is split into 6 Tokens :

• x
• *
• sin
• (
• x
• )

Fortunately, the algorithm is quite simple. we can parse the input string from left to right and match any recognized operator by its mathematical symbol.

Infix to Postfix

The extensive explanation can be found here. A quick ad hoc method for this conversion consists of these steps:

1. Fully parenthesize the expression
2. (Start from the most inner expression and) move the operator between each pair of parentheses right before enclosing parenthesis.
3. Remove all parenthesis.

For example, The converted version of A + B * C (as it is illustrated below) is A B C * +

But the algorithmic way to perform the conversion using the operator's stack includes these steps: (Parsing tokens from start to end)

1. If current token is an Operand -> add it to output
2. If current token is Left Parenthesis -> push it into the stack
3. If current token is Right Parenthesis -> pop the stack until corresponding Left Parenthesis, add each token to output
4. If current token is an Operator ->
   • if it has less or equal precedence compared to the operator on the top of the stack -> pop the token from the stack and add it to output, then push the current privileged one into the stack.
   • if it has higher precedence compared to the operator on the top of the stack or the stack is empty -> push it into the stack
5. Do above steps for all tokens (from left to right) until it finishes
6. If the input string is finished (all tokens are parsed) -> pop the remaining operators in the stack and add them to output.

The figure below shows the steps of converting A * B + C * D into A B * C D * +

Postfix Evaluation

A stack is again the data structure of choice. However, as you scan the postfix expression, it is the operands that must wait, not the operators as in the conversion algorithm above. The algorithm is simple (parsing the Postfix expression from left to right):

1. whenever an operand is seen on the input -> push it into the stack
2. whenever an operator is seen on the input ->
   • if it's a binary operator -> pop the stack two times and apply the operator on them, push the result back into the stack
   • if it's an unary operator -> pop the stack, apply the operator on it and push the result back into the stack.
3. Do above steps for all tokens (from left to right) until it finishes
4. The should be a sole result of the evaluation remained in the stack.

The figure below shows the steps of evaluating 4 5 6 * + ( which is 4 + 5 * 6 = 34)

The Design Patterns

As it is explained, this application is composed of three major parts. Scanner, Infix to Postfix Converter and Postfix Evaluator. In regards to SRP (Single Responsibility Pattern) we implement each part into a separate class. For the sake of OCP (Open Closed Principle), we design the program in a way that adding new operators doesn't force any change or modification in these classes.

SRP

For each phase of the algorithm, a separated class is defined like below and each class has a sole unique responsibility.

typedef QList<std::shared_ptr<Token>> Tokens;
class Scanner
{
  ...
public:
    Scanner(QString input_string);
    Tokens scan();
};
class InfixToPostfix
{
  ...
public:
    InfixToPostfix(Tokens& infix_tokens);
    Tokens convert();
};
class FunctionEvaluator
{
...
public:
    FunctionEvaluator(Tokens& postfix_tokens)
    double evaluate(const QList<QPair<QString,double>>& variables_list);
};

OCP

The reaffirmation of extending operands and respecting OCP is the tricky part. Defining new operators is simply manageable. however, the scanner class should know about newly defined operators, same as postfix evaluator and converter classes. So they should be modified each time we wanted to add a new operator. This fact leaves our design Open for Modifications, which is terrible! OCP says that software entities should be open for extension but closed for modification. Therefore we need to alter our design.

The solution is to take the logic of operators and dependencies out of the Scanner, Postfix converter, and Evaluator. Scanner needs to know about lexical form or symbol of the operators while Postfix converter should be aware of operators precedence, and finally, Evaluator should know the mathematical logic behind every operator. so any attempt to define an operator has to include these three factors. A simple unary operator is defined like:

class Cos final : public UnaryOperator
{
public:
    //This is how the scanner will know about cos signature
    static std::shared_ptr<Cos> checkAndCreate (QString& str)
    {
        return (str == "cos") ? std::make_shared<Cos>() : nullptr;
    }
    Cos()
    {
        _lexical_form = "cos";
        
        //This is how infix to postfix converter will know about this operator precedence
        _precedence = OperatorPrecedence::Functions;
    }
    
    //This is how Postfix evaluator conducts the math.
    double evaluate(double operand) override
    {
        return std::cos(operand);
    }
};

It only remains one thing for us to do. How can scanner build an instance from the new operator? Easy! For building new operators we introduce an OpertarFactory class and we let it does the job for us. As C++ generally does not support reflection we have to add a pointer of new operators to its operator's list.

How to extend program by adding a custom operator

To create a unary operator, we need to extend this file with a new class respected to the new operator.

Phase.1 : Definition of the operator

The class signature for unary operators is like:

class OperatorName final : public UnaryOperator
{
public:
    static std::shared_ptr<OperatorName> checkAndCreate (QString& str)
    {
        return (str == "OperatorSymbol") ? std::make_shared<OperatorName>() : nullptr;
    }
    //ctor
    OperatorName()
    {
        _lexical_form = "OperatorSymbol";
        _precedence = OperatorPrecedence::One_Type_Of_Defined_Precedences;
    }
    double evaluate(double operand) override
    {
        double result;

        //Implement operator's mathematical logic here,
        //the way it affects the operand

        return result;
    }
};

Extending operators collection for BinaryOperators is almost the same, The only difference is that it inherits from BinaryOperator base class and also 'evaluate' function signature is:

double evaluate(double left_operand, double right_operand) override

Phase.2 :

We need to extend OperatorFactory class, so our newly built operator can be recognized and used in scanner. to do this, we need to append this line of code into 'create' function of the OperatorFactory class

operators_constructors.append((std::shared_ptr<Operator> (*)(const QString&)) (&OperatorName::checkAndCreate));

Using The Code

By hitting draw button the code in below will be executed, which also explains how to use the all main components together.

//Initiating a new QT line serie.
QLineSeries* serie(new QLineSeries());
serie->setName(ui->leFunction->text());

//Makeing a list of variables, which includes only x
QPair<QString,double> x = {"x",0};
QList<QPair<QString,double>> variables_list = {x};

//Stage1: Tokenizing function definition.
Scanner scanner(ui->leFunction->text());
auto infix_expression = scanner.scan();

//Stage2: Convert function definition into a postfix notation
InfixToPostfix infix_to_postfix(infix_expression);
auto postfix_expression = infix_to_postfix.convert();

//Stage3: Evaluating the postfix_function for x in range [-30,+30]
FunctionEvaluator evaluator(postfix_expression);

for (double x = -30.0; x <= 30.0; x+=0.1)
{
    variables_list[0].second = x;

    double y = evaluator.evaluate(variables_list);
    /* since the result of an arbitrary function can be limitless and
     * converge to infinity, it can deform our chart. so better to set
     * some boundries.
     */
    if (y > 100) y = 100;
    if (y < -100) y = -100;

    serie->append(x,y);
}

//Update the chart.
chart->addSeries(serie);
chart->createDefaultAxes();
chartView->setChart(chart);

The algorithm of Scanner, converter and evaluator are clarified beforehand. the source code also contains comments so it should be clear.

Improvements

Improve the quality of the code

Unfortunately, I hadn't enough time to complete the error handling sections. I've only marked them in code with TODO tags. After all, this is not a final module or project. It's only an explanatory article.

Implement an interface for Scanner

By Formal methods, Automata theory and compilers science, we know that for parsing most of the mathematical expressions and to be able to recognize syntactical and semantic errors, we need at least a context-free language. Although our demonstrated method can fulfill our needs for many cases, But still someone might want to use a stronger and more robust method. So it will be a good practice to define an interface for scanning phase (like IScanner) to be able to have multiple implementations.

Add a syntax checker to scanner

We definitely demand a syntax checker. My code currently ignores all the faults and for all defective cases, it will generate a bogus zero constant function. A syntax checker can also be designed in the way of OCP.

Future plan

If I find this article interesting to the readers and I get positive feedbacks, the next article will be a trail to this one, But more about Qt itself. Now we've got a good function evaluator, why not illustrate a 3d surface like this?