C++ 设计模式——解释器模式

C++ 设计模式——解释器模式

解释器模式是一种特定于语言的模式，用于定义如何评估语言的句法或表达式。它适用于某些重复出现的问题，可以将一个需要解释执行的语言中的句子表示为一个抽象的语法树。这种模式通常被用于开发编程语言解释器或简单的脚本引擎。

引人“解释器”设计模式的定义(实现意图)：定义一个语言的文法(语法规则)，并建立一个解释器解释该语言中的句子。

1. 主要组成成分

1. 抽象表达式（Abstract Expression）：定义了解释操作的接口。这个接口通常包含一个解释（Interpret）方法，该方法接受一个上下文作为参数。
2. 终结符表达式（Terminal Expression）：实现了抽象表达式接口。这些表达式代表了语言中的终结符，如数字或变量。
3. 非终结符表达式（Nonterminal Expression）：也实现了抽象表达式接口。这些表达式代表了语言中的非终结符，通常包含其他表达式。
4. 上下文（Context）：包含解释器之外的一些全局信息。这可能包括变量的值、当前状态等。
5. 客户端（Client）：构建抽象语法树并调用解释操作。客户端通常会创建或被给予一个表示特定句子的抽象语法树，然后调用解释方法。

2. 逐步构建解释器模式

这个逐步构建的过程展示了解释器模式的核心组件如何协同工作，从定义基本的表达式接口，到实现具体的表达式类，再到构建和解释复杂的表达式树。这种方法使得添加新的表达式类型变得简单，同时保持了整体结构的灵活性和可扩展性。

步骤1: 定义抽象表达式

首先定义一个抽象基类 Expression，它是所有表达式的基础，所有的具体表达式类都必须实现这个函数，以便执行具体的解释任务。

//小表达式（节点）父类
class Expression
{
public:
    Expression(int num, char sign) :m_dbg_num(num), m_dbg_sign(sign) {} //构造函数
    virtual ~Expression() {} //做父类时析构函数应该为虚函数

public:
    //解析语法树中的当前节点
    virtual int interpret(map<char, int> var) = 0; //#include <map>，map容器中的键值对用于保存变量名及对应的值

public:
    //以下两个成员变量是为程序跟踪调试时观察某些数据方便而引入
    int m_dbg_num;   //创建该对象时的一个编号，用于记录本对象是第几个创建的
    char m_dbg_sign; //标记本对象的类型，可能是个字符v代表变量（终结符表达式），也可能是个加减号（非终结符表达式）
};

步骤2: 实现终结符表达式

接着，创建一个或多个终结符表达式类，例如 VarExpression，它们直接与语言的终结符相对应。这些类实现了抽象表达式中定义的 interpret() 方法，返回变量在上下文中的值。

//变量表达式（终结符表达式）
class VarExpression :public Expression
{
public:
    VarExpression(const char& key, int num, char sign) :Expression(num, sign) //构造函数
    {
        m_key = key;
    }
    virtual int interpret(map<char, int> var)
    {
        return var[m_key];  //返回变量名对应的数值
    }

private:
    char m_key; //变量名，本范例中诸如a、b、c、d都是变量名
};

步骤3: 实现非终结符表达式

创建运算符表达式基类 SymbolExpression 和非终结符表达式类如 AddExpression 和 SubExpression 代表语言的规则。这些类通常会持有其他 Expression 对象，并在其 interpret() 方法中递归调用这些对象的 interpret() 方法，合并其结果。

//运算符表达式（非终结符表达式）父类
class SymbolExpression :public Expression
{
public:
    SymbolExpression(Expression* left, Expression* right, int num, char sign) :m_left(left), m_right(right), Expression(num, sign) {} //构造函数
    Expression* getLeft() { return m_left; }
    Expression* getRight() { return m_right; }
protected:
    //左右各有一个操作数
    Expression* m_left;
    Expression* m_right;
};

//加法运算符表达式（非终结符表达式）
class AddExpression :public SymbolExpression
{
public:
    AddExpression(Expression* left, Expression* right, int num, char sign) :SymbolExpression(left, right, num, sign) {}//构造函数

    virtual int interpret(map<char, int> var)
    {
        //分步骤拆开写，方便理解和观察
        int value1 = m_left->interpret(var); //递归调用左操作数的interpret方法
        int value2 = m_right->interpret(var); //递归调用右操作数的interpret方法
        int result = value1 + value2;
        return result; //返回两个变量相加的结果
    }
};

//减法运算符表达式（非终结符表达式）
class SubExpression :public SymbolExpression
{
public:
    SubExpression(Expression* left, Expression* right, int num, char sign) :SymbolExpression(left, right, num, sign) {}//构造函数

    virtual int interpret(map<char, int> var)
    {
        int value1 = m_left->interpret(var);
        int value2 = m_right->interpret(var);
        int result = value1 - value2;
        return result; //返回两个变量相减的结果
    }
};

步骤4: 构建语法树

创建一个函数来分析表达式字符串并构建语法树：

//分析—创建语法树（表达式树）
Expression* analyse(string strExp) //strExp：要计算结果的表达式字符串，比如"a-b+c+d"
{
    stack<Expression*>  expStack;//#include <stack>，这里用到了栈这种顺序容器
    Expression* left = nullptr;
    Expression* right = nullptr;
    int icount = 1;
    for (size_t i = 0; i < strExp.size(); ++i)//循环遍历表达式字符串中的每个字符
    {
        switch (strExp[i])
        {
        case '+':
            //加法运算符表达式（非终结符表达式）
            left = expStack.top(); //返回栈顶元素（左操作数）
            ++i;
            right = new VarExpression(strExp[i], icount++, 'v'); //v代表是个变量节点
            //在栈顶增加元素
            expStack.push(new AddExpression(left, right, icount++, '+')); //'+'代表是个减法运算符节点
            break;
        case '-':
            //减法运算符表达式（非终结符表达式）
            left = expStack.top(); //返回栈顶元素
            ++i;
            right = new VarExpression(strExp[i], icount++, 'v');
            expStack.push(new SubExpression(left, right, icount++, '-')); //'-'代表是个减法运算符节点
            break;
        default:
            //变量表达式（终结符表达式）
            expStack.push(new VarExpression(strExp[i], icount++, 'v'));
            break;
        } //end switch
    } //end for
    Expression* expression = expStack.top(); //返回栈顶元素
    return expression;
}

步骤5: 实现内存管理

添加一个函数来释放表达式树的内存：

void release(Expression* expression)
{
    //释放表达式树的节点内存
    SymbolExpression* pSE = dynamic_cast<SymbolExpression*>(expression); //此处代码有优化空间（不使用dynamic_cast），留给读者思考
    if (pSE)
    {
        release(pSE->getLeft());
        release(pSE->getRight());
    }
    delete expression;
}

步骤6: 创建上下文和客户端

在 main 函数中创建上下文（变量映射）并使用解释器：

int main()
{
    string strExp = "a-b+c+d";	 //将要求值的字符串表达式
    map<char, int> varmap;
    //下面是给字符串表达式中所有参与运算的变量一个对应的数值
    varmap.insert(make_pair('a', 7)); //类似于赋值语句a = 7
    varmap.insert(make_pair('b', 9)); //类似于赋值语句b = 9
    varmap.insert(make_pair('c', 3)); //类似于赋值语句c = 3
    varmap.insert(make_pair('d', 2)); //类似于赋值语句d = 2

    Expression* expression = analyse(strExp);  //调用analyse函数创建语法树
    int result = expression->interpret(varmap); //调用interpret接口求解字符串表达式的结果
    cout << "字符串表达式\"a - b + c + d\"的计算结果为：" << result << endl; //输出字符串表达式结果

    //释放内存
    release(expression);

    return 0;
}

3. 解释器模式 UML 图

UML 图解析

解释器模式的 UML 图中包含如下 4 种角色：

1. AbstractExpression (抽象表达式)：声明了一个抽象的解释操作，它是所有终结符表达式和非终结符表达式的公共基类。这里指Expression类。

2. TerminalExpression (终结符表达式)：抽象表达式的子类，实现了语言文法中与终结符表达式相关的解释操作。一个句子中的每个终结符表达式都是该类的一个实例，这些实例可以通过非终结符表达式组成更为复杂的句子。这里指VarExpression类。

3. NonterminalExpression (非终结符表达式)：同样是抽象表达式的子类，实现了语言文法中与非终结符表达式相关的解释操作。考虑到非终结符表达式既可以包含终结符表达式，也可以包含其他非终结符表达式，所以其相关的解释操作一般是通过递归调用实现的。这里指AddExpression、SubExpression。

   注意，引入SymbolExpression类的目的是方便AddExpression、SubExpression作为其子类的编写（方便继承），SymbolExpression类本身并不是非终结符表达式，也并不是必须存在的。

4. Context (环境类/上下文类)：用于存储解释器之外的一些全局信息，例如变量名与值的映射关系、存储和访问表达式解释器的状态等。之后这个信息会作为参数传递到所有表达式的解释操作（interpret成员函数）中作为这些解释操作的公共对象来使用。可以根据实际情况决定是否需要使用该类。这里指varmap这个map容器（虽然上述范例并没有将该容器封装到一个类中）。

4. 解释器模式的优点

1. 易于改变和扩展文法：每个文法规则都对应一个类，可以方便地改变或扩展文法。
2. 实现文法较为容易：每条文法规则都可以表示为一个类，因此可以直接将规则表示为代码。
3. 增加新的解释表达式较为方便：如果需要增加新的解释表达式，只需要添加一个新的类即可。

5. 解释器模式的缺点

1. 对于复杂文法难以维护：当文法规则数目太多时，管理这些类会变得非常困难。
2. 执行效率较低：解释器模式使用了大量的循环和递归调用，对于复杂的句子可能会导致效率问题。
3. 可能会引起类膨胀：每个文法规则都需要一个单独的类，可能会导致系统中类的数量急剧增加。

6. 解释器模式适用场景

1. 简单语法的语言：解释器模式非常适合用于实现一些简单的、可组合的语法规则。例如，计算器程序需要解析和计算数学表达式，可以使用解释器模式来实现。
2. 领域特定语言（DSL）：在某些领域，可能需要定义一个小型的语言来描述特定的任务或行为。例如，SQL查询、正则表达式、配置文件解析等，都可以使用解释器模式来实现相应的解析和执行。
3. 文本处理：解释器模式可以用于文本处理和编译，例如编译器或解释器中的词法分析和语法分析。它可以将输入的文本转换为抽象语法树，并基于这个树结构执行相应的操作。
4. 命令解释： 一些应用程序可能需要解析和执行命令行输入或脚本语言。解释器模式可以用来定义这些命令的语法，并提供相应的解释和执行机制。
5. 规则引擎：在某些业务系统中，可能需要根据一系列规则来执行不同的操作。解释器模式可以用来定义这些规则的语法，并在运行时解析和执行这些规则。
6. 编程语言的实现：实现一种新的编程语言或脚本语言时，解释器模式可以用于解析和执行语言的语法。许多简单的脚本语言和教学语言都使用解释器模式来实现。

总结

解释器模式提供了一种灵活的方式来解释特定语言的句子。它将每个文法规则封装到单独的类中，使得语言的解释变得模块化和可扩展。然而，这种模式在处理复杂语言时可能会导致类的数量激增，并且可能存在性能问题。因此，解释器模式最适合用于简单语言的解释，或者在需要频繁修改语法规则的场景中。在实际应用中，需要权衡其优点和缺点，并根据具体需求决定是否使用此模式。

完整代码

#include <iostream>
#include <cstring>
#include <map>
#include <stack>
#include <vector>

using namespace std;

//小表达式（节点）父类
class Expression
{
public:
    Expression(int num, char sign) :m_dbg_num(num), m_dbg_sign(sign) {} //构造函数
    virtual ~Expression() {} //做父类时析构函数应该为虚函数

public:
    //解析语法树中的当前节点
    virtual int interpret(map<char, int> var) = 0; //#include <map>，map容器中的键值对用于保存变量名及对应的值

public:
    //以下两个成员变量是为程序跟踪调试时观察某些数据方便而引入
    int m_dbg_num;   //创建该对象时的一个编号，用于记录本对象是第几个创建的
    char m_dbg_sign; //标记本对象的类型，可能是个字符v代表变量（终结符表达式），也可能是个加减号（非终结符表达式）
};

//-----
//变量表达式（终结符表达式）
class VarExpression :public Expression
{
public:
    VarExpression(const char& key, int num, char sign) :Expression(num, sign) //构造函数
    {
        m_key = key;
    }
    virtual int interpret(map<char, int> var)
    {
        return var[m_key];  //返回变量名对应的数值
    }

private:
    char m_key; //变量名，本范例中诸如a、b、c、d都是变量名
};

//------
//运算符表达式（非终结符表达式）父类
class SymbolExpression :public Expression
{
public:
    SymbolExpression(Expression* left, Expression* right, int num, char sign) :m_left(left), m_right(right), Expression(num, sign) {} //构造函数
    Expression* getLeft() { return m_left; }
    Expression* getRight() { return m_right; }
protected:
    //左右各有一个操作数
    Expression* m_left;
    Expression* m_right;
};

//加法运算符表达式（非终结符表达式）
class AddExpression :public SymbolExpression
{
public:
    AddExpression(Expression* left, Expression* right, int num, char sign) :SymbolExpression(left, right, num, sign) {}//构造函数

    virtual int interpret(map<char, int> var)
    {
        //分步骤拆开写，方便理解和观察
        int value1 = m_left->interpret(var); //递归调用左操作数的interpret方法
        int value2 = m_right->interpret(var); //递归调用右操作数的interpret方法
        int result = value1 + value2;
        return result; //返回两个变量相加的结果
    }
};

//减法运算符表达式（非终结符表达式）
class SubExpression :public SymbolExpression
{
public:
    SubExpression(Expression* left, Expression* right, int num, char sign) :SymbolExpression(left, right, num, sign) {}//构造函数

    virtual int interpret(map<char, int> var)
    {
        int value1 = m_left->interpret(var);
        int value2 = m_right->interpret(var);
        int result = value1 - value2;
        return result; //返回两个变量相减的结果
    }
};

//分析—创建语法树（表达式树）
Expression* analyse(string strExp) //strExp：要计算结果的表达式字符串，比如"a-b+c+d"
{
    stack<Expression*>  expStack;//#include <stack>，这里用到了栈这种顺序容器
    Expression* left = nullptr;
    Expression* right = nullptr;
    int icount = 1;
    for (size_t i = 0; i < strExp.size(); ++i)//循环遍历表达式字符串中的每个字符
    {
        switch (strExp[i])
        {
        case '+':
            //加法运算符表达式（非终结符表达式）
            left = expStack.top(); //返回栈顶元素（左操作数）
            ++i;
            right = new VarExpression(strExp[i], icount++, 'v'); //v代表是个变量节点
            //在栈顶增加元素
            expStack.push(new AddExpression(left, right, icount++, '+')); //'+'代表是个减法运算符节点
            break;
        case '-':
            //减法运算符表达式（非终结符表达式）
            left = expStack.top(); //返回栈顶元素
            ++i;
            right = new VarExpression(strExp[i], icount++, 'v');
            expStack.push(new SubExpression(left, right, icount++, '-')); //'-'代表是个减法运算符节点
            break;
        default:
            //变量表达式（终结符表达式）
            expStack.push(new VarExpression(strExp[i], icount++, 'v'));
            break;
        } //end switch
    } //end for
    Expression* expression = expStack.top(); //返回栈顶元素
    return expression;
}

void release(Expression* expression)
{
    //释放表达式树的节点内存
    SymbolExpression* pSE = dynamic_cast<SymbolExpression*>(expression); //此处代码有优化空间（不使用dynamic_cast），留给读者思考
    if (pSE)
    {
        release(pSE->getLeft());
        release(pSE->getRight());
    }
    delete expression;
}


int main()
{
    string strExp = "a-b+c+d";	 //将要求值的字符串表达式
    map<char, int> varmap;
    //下面是给字符串表达式中所有参与运算的变量一个对应的数值
    varmap.insert(make_pair('a', 7)); //类似于赋值语句a = 7
    varmap.insert(make_pair('b', 9)); //类似于赋值语句b = 9
    varmap.insert(make_pair('c', 3)); //类似于赋值语句c = 3
    varmap.insert(make_pair('d', 2)); //类似于赋值语句d = 2

    Expression* expression = analyse(strExp);  //调用analyse函数创建语法树
    int result = expression->interpret(varmap); //调用interpret接口求解字符串表达式的结果
    cout << "字符串表达式\"a - b + c + d\"的计算结果为：" << result << endl; //输出字符串表达式结果

    //释放内存
    release(expression);

    return 0;
}