65.9K
CodeProject 正在变化。 阅读更多。
Home

函数绘图器，玩转设计模式

Hamidreza Ebtehaj
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.97/5 (30投票s)

2017年1月26日

CPOL

8分钟阅读

viewsIcon

29505

downloadIcon

687

设计最简单的函数求值器。

引言

下载源代码： SourceCode.zip

想象一下，您正在开发一个用于控制万能试验机的工业程序，该程序的功能之一是压缩金属并在实验过程中测量力。假设一位客户要求您根据公式“P=F/A”计算压力。这很简单！我们可以在程序中瞬间实现这个方程。但如果其他客户需要不同的公式呢？如果您要求客户在运行时能够动态输入他的公式，而公式可能数不胜数，那该怎么办？好吧，为了应对这种情况（当您在编译时不知道数学函数的定义时），您将需要一个函数求值算法。

函数绘图器是一个简单的 C++ (Qt) 程序，它以数学函数定义“f(x)”作为输入，并在二维图（x-y）上进行绘制。下图显示了程序运行时的情况。

我已在 64 位 Linux 机器上编译了此项目。但由于它是使用 Qt 框架开发的，因此在 Windows 或 Mac 等其他操作系统上编译应该没有问题。源代码也可在此处获得：here。

背景

存在大量的函数评估算法。最简单、最基本的算法是我们程序的基础，在此处进行了清晰的解释。我们也会快速地解释它。

求值算法显而易见且易于实现，但主要问题是如何找到一种实用的方法来实现构成方程的庞大运算符。除了基本的算术运算符（如（+、*、^ 等））之外，像“sin”和“log”这样的函数也可以构成数学运算。这就是为什么本项目的主要重点是设计模式而不是算法本身。

设计应用程序

快速回顾函数求值算法

普通的逻辑公式用中缀表示法表示，其特点是将运算符放在操作数之间（如 2 + 3）。这种表示法易于人类阅读，但由于可能存在歧义，因此必须使用括号。与后缀表示法（如 2 3 +）相比，它也更难被计算机解析。因此，总体步骤是：

  1. 扫描输入公式（对中缀表示法进行分词）
  2. 将公式的中缀表示法转换为后缀表示法。
  3. 求值后缀表示法。

扫描输入公式

不同的运算符具有不同的行为，但它们都以输入字符串的形式呈现给我们，因此能够区分它们至关重要。例如，“x*sin(x)”被分解为 6 个**词法单元**。

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

幸运的是，算法相当简单。我们可以从左到右解析输入字符串，并通过其数学符号匹配任何识别出的运算符。

中缀转后缀

此处可找到详细的解释。一种快速的临时转换方法包括以下步骤：

  1. 完全括号化表达式
  2. (从最内层表达式开始) 将每对括号之间的运算符移到其外层括号的右侧。
  3. 删除所有括号。

例如，A + B * C 的转换版本（如下图所示）是 A B C * +。

但是，使用运算符栈执行转换的算法方法包括以下步骤：（从头到尾解析词法单元）

  1. 如果当前词法单元是操作数 -> 将其添加到输出
  2. 如果当前词法单元是左括号 -> 将其推入栈
  3. 如果当前词法单元是右括号 -> 从栈中弹出直到遇到相应的左括号，将每个词法单元添加到输出
  4. 如果当前词法单元是运算符 ->
    • 如果其优先级小于或等于栈顶运算符的优先级 -> 从栈中弹出该词法单元并添加到输出，然后将当前优先级高的运算符推入栈。
    • 如果其优先级高于栈顶运算符的优先级，或者栈为空 -> 将其推入栈
  5. 对所有词法单元（从左到右）执行上述步骤，直到完成
  6. 如果输入字符串结束（所有词法单元都已解析）-> 弹出栈中剩余的运算符并将它们添加到输出。

下图显示了将 A * B + C * D 转换为 A B * C D * + 的步骤。

后缀求值

栈再次是首选的数据结构。但是，当您扫描后缀表达式时，需要等待的是操作数，而不是像上面的转换算法中那样等待运算符。该算法很简单（从左到右解析后缀表达式）：

  1. 每当在输入中看到操作数时 -> 将其推入栈
  2. 每当在输入中看到运算符时 ->
    • 如果是二元运算符 -> 从栈中弹出两次，并在它们上应用运算符，然后将结果推回栈
    • 如果是单元运算符 -> 从栈中弹出一个操作数，在该操作数上应用运算符，然后将结果推回栈。
  3. 对所有词法单元（从左到右）执行上述步骤，直到完成
  4. 栈中应该只剩下一个求值结果。

下图显示了对 4 5 6 * +（即 4 + 5 * 6 = 34）求值的步骤。

设计模式

正如所解释的，此应用程序由三个主要部分组成：扫描器、中缀转后缀转换器和后缀求值器。根据 SRP（单一职责原则），我们将每个部分实现为一个单独的类。为了 OCP（开闭原则），我们设计程序的方式是，添加新运算符不会强制更改或修改这些类。

SRP

对于算法的每个阶段，都会定义一个单独的类，如下所示，每个类都有一个唯一且独立的职责。

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

扩展操作数并遵守 OCP 的部分棘手。定义新运算符很容易管理。但是，扫描器类需要了解新定义的运算符，后缀求值器和转换器类也是如此。因此，每次我们想添加一个新运算符时，都需要修改它们。这个事实使我们的设计对修改开放，这是非常糟糕的！OCP 规定软件实体应该是对扩展开放的，对修改关闭的。因此，我们需要修改我们的设计。

解决方案是将运算符的逻辑和依赖关系移出扫描器、后缀转换器和求值器。扫描器需要了解运算符的词法形式或符号，而后缀转换器应该了解运算符的优先级，最后，求值器应该了解每个运算符背后的数学逻辑。因此，任何尝试定义运算符的操作都必须包含这三个因素。一个简单的单元运算符定义如下：

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);
    }
};

我们只需要做一件事。扫描器如何从新运算符构建实例？很容易！为了构建新运算符，我们引入了一个 OpertarFactory 类，并让它为我们完成工作。由于 C++ 通常不支持反射，我们必须将新运算符的指针添加到其运算符列表中。

如何通过添加自定义运算符来扩展程序

要创建单元运算符，我们需要扩展此文件，创建一个遵守新运算符的新类。

第一阶段：运算符的定义

单元运算符的类签名如下：

 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;
     }
 };

扩展二元运算符集合的操作也几乎相同。唯一的区别是它继承自 BinaryOperator 基类，并且“evaluate”函数的签名是：

double evaluate(double left_operand, double right_operand) override

第二阶段

我们需要扩展 OperatorFactory 类，以便我们的新运算符可以被识别并在扫描器中使用。为此，我们需要将以下代码行添加到 OperatorFactory 类的“create”函数中：

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

使用代码

单击绘制按钮时，将执行以下代码，该代码也解释了如何将所有主要组件结合在一起。

    //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);

前面已经阐明了扫描器、转换器和求值器的算法。源代码也包含注释，应该很清楚。

改进

提高代码质量

不幸的是，我没有足够的时间来完成错误处理部分。我只在代码中用 TODO 标签标记了它们。毕竟，这不是一个最终模块或项目。它只是一个解释性文章。

实现扫描器的接口

根据形式化方法、自动机理论和编译器科学，我们知道要解析大多数数学表达式并能够识别语法和语义错误，至少需要一个上下文无关语言。虽然我们演示的方法可以在许多情况下满足我们的需求，但仍然有人可能希望使用更强大、更健壮的方法。因此，为扫描阶段（如 IScanner）定义一个接口以便拥有多个实现将是一个好做法。

向扫描器添加语法检查器

我们绝对需要一个语法检查器。我的代码目前会忽略所有错误，对于所有无效情况，它都会生成一个错误的零常数函数。语法检查器也可以按照 OCP 的方式进行设计。

未来计划

如果读者觉得这篇文章有趣，并且我得到积极的反馈，下一篇文章将是这个系列的后续，但更多是关于 Qt 本身。现在我们有了一个很好的函数求值器，为什么不绘制像这样的 3D 曲面呢？

© . All rights reserved.