设计模式21-Interpreter(解析器)模式-四则运算

在软件构建过程中，如果某一特定领域的问题比较复杂，类似的结构不断重复出现，如果使用普通的编程方式来实现将面临非常频繁的变化。在这种情况下，将特定领域的问题表达为某种语法规则下的句子，然后构建一个解析器来解释这样的句子，从而达到解决问题的目的。

解释器模式即给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

UML图：

• AbstractExpression：定义解释器的接口，约定解释器的解释操作。其中的Interpret接口，正如其名字那样，它是专门用来解释该解释器所要实现的功能。（如加法解释器中的Interpret接口就是完成两个操作数的相加功能）。
• TerminalExpression：终结符解释器，用来实现语法规则中和终结符相关的操作，不再包含其他的解释器，如果用组合模式来构建抽象语法树的话，就相当于组合模式中的叶子对象，可以有多种终结符解释器。
• NonterminalExpression：非终结符解释器，用来实现语法规则中非终结符相关的操作，通常一个解释器对应一个语法规则，可以包含其他解释器，如果用组合模式构建抽象语法树的话，就相当于组合模式中的组合对象。可以有多种非终结符解释器。
• Context：上下文，通常包含各个解释器需要的数据或是公共的功能。这个Context在解释器模式中起着非常重要的作用。一般用来传递被所有解释器共享的数据，后面的解释器可以从这里获取这些值。
• Client：客户端，指的是使用解释器的客户端，通常在这里将按照语言的语法做的表达式转换成使用解释器对象描述的抽象语法树，然后调用解释操作。

举个例子，我们要实现一个四则运算功能，给定表达式和表达式中每个变量的值，然后程序计算出答案。UML图如下：

代码实现：

#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <typeinfo>

using namespace std;

//抽象表达式类
class Expression
{
public:
	//解析公式和数值，其中var中的key是公式中的参数，value值是具体的数字
	//如a = 100; b = 20; c = 40
	virtual int interpreter(map<string, int>& var) = 0;
	virtual ~Expression() {};
};


//变量解析器（终结符表达式）
class VarExpression : public Expression
{
	string key;

public:
	VarExpression(string key) {
		this->key = key;
	}

	//从map中取出变量的值
	int interpreter(map<string, int>& var) {
		return var[key];
	}

	~VarExpression() {}
};

//抽象运算符号解析器
class SymbolExpression : public Expression
{
protected:
	Expression* left;
	Expression* right;

public:
	SymbolExpression(Expression* left, Expression* right) {
		this->left = left;
		this->right = right;
	}

	Expression* getLeft() {
		return left;
	}

	Expression* getRight() {
		return right;
	}
};

//加法解析器
class AddExpression : public SymbolExpression
{
public:
	AddExpression(Expression* left, Expression* right) : SymbolExpression(left, right) {}

	//把左右两个表达式运算的结果加起来
	int interpreter(map<string, int>& var) {
		return left->interpreter(var) + right->interpreter(var);
	}

	~AddExpression() {}
};

//减法解析器
class SubExpression : public SymbolExpression
{
public:
	SubExpression(Expression* left, Expression* right) : SymbolExpression(left, right) {}

	//把左右两个表达式运算的结果相减
	int interpreter(map<string, int>& var) {
		return left->interpreter(var) - right->interpreter(var);
	}

	~SubExpression() {}
};

//解析器封装类，这个类是根据迪米特法则进行封装，目的是让Client只与直接朋友打交道，相当于Facade
class Calculator
{
private:
	Expression* expression;

public:
	//构造函数传参，并解析表达式，构建语法树
	Calculator(string expStr) 
	{
		expression = NULL;

		//栈，用来暂存中间结果
		stack<Expression*> stkExp;

		Expression* left = NULL;
		Expression* right = NULL;

		/*从左到向分析表达式（如:a+b-c)，最终的语法树如下：
		*           -
		*         /   \
		*       +     c
		*     /   \
		*    a     b
		*/
		for (unsigned int i = 0; i< expStr.length(); i++)
		{
			switch (expStr[i])
			{
			case '+':  //加法
					   //1.先从栈中取出左操作数
				left = stkExp.top();
				stkExp.pop();

				//2.从表达式中取出+号后面的右操作数，并生成终结符解析对象
				right = new VarExpression(expStr.substr(++i, 1));

				//3.将左右操作数相加，并把结果放入栈中
				stkExp.push(new AddExpression(left, right));

				break;

			case '-':
				//1.先从栈中取出左操作数
				left = stkExp.top();
				stkExp.pop();

				//2.从表达式中取出+号后面的右操作数，并生成终结符解析对象
				right = new VarExpression(expStr.substr(++i, 1));

				//3.将左右操作数相减，并把结果放入栈中
				stkExp.push(new SubExpression(left, right));

				break;

			default:
				//如果是变量（终结符）：如a+b+c中的a\b\c，
				//则直接生成对应的变量解析器对象
				stkExp.push(new VarExpression(expStr.substr(i, 1)));//为了简化就默认变量都是1个字符
			}
		}

		//栈中保存的就是最终语法树的根结点（本例为SuuExpression对象）
		if (!stkExp.empty())
		{
			expression = stkExp.top();
			stkExp.pop();
		}
	}

	void deltree(Expression* expression)
	{
		SymbolExpression* branch = dynamic_cast<SymbolExpression*>(expression);
		//叶子结点
		if (branch == NULL)
		{
			delete expression;
		}
		else  //分支结点
		{
			//左子树
			deltree(branch->getLeft());

			//右子树
			deltree(branch->getRight());

			//结点
			delete expression;
		}
	}

	~Calculator()
	{
		deltree(expression);
		expression = NULL;
	}

	//开始运算
	int run(map<string, int>& var) {
		return (expression == NULL) ? 0 : expression->interpreter(var);
	}
};

int main()
{
	string expStr = "a+b-c"; //为简化处理，这里必须是合法的表达式

	map<string, int> var;   //相当于Interpreter模式中的Context
	var["a"] = 100;
	var["b"] = 20;
	var["c"] = 40;

	Calculator cal(expStr);

	cout << expStr << " = " << cal.run(var) << endl;
	return 0;
}

运行结果：

a+b-c = 80