积木

No sub title

C++博客 :: 首页 :: 联系 :: 聚合

:: 管理

140 Posts :: 1 Stories :: 11 Comments :: 0 Trackbacks

常用链接

留言簿(1)

我参与的团队

随笔分类

随笔档案

搜索

阅读排行榜

评论排行榜

【转载】 C++实现Behavioral - Interpreter模式

转载自：http://patmusing.blog.163.com/blog/static/13583496020101501515558/

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

“Given a language, define a represention for its grammar along with an interpreter that uses the representation to interpret sentences in the language.” -GoF

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

Interpreter设计模式中的几种角色：

AbstractExpression:

- 声明一个抽象的Interpret方法，抽象语法树中所有的节点都必须实现该抽象方法。

TerminalExpression:

- 实现和语法中末端符号相关的Interpret方法。

- 在每个句子的末端符号中均需要一个TerminalExpression实例。

NonterminalExpression:

另外一个实现了AbstractExpression 接口的类，用来处理语法树中非末端节点的语法。它含有下一个AbstractExpression(s)的引用，调用它每个子节点的Interpret方法。

Context:

Interpreter方法所需要的信息的容器，该信息对Interpreter而言全局可见。充当几个AbstractExpresssion 实例之间的通讯频道。

PatternClient:

构建或者接收一个抽象语法书的实例。对于一个特定的句子而言，语法树往往由若干个TerminalExpressions 和 NonterminalExpression组成。PatterClient在合适的context下，调用Interpret方法。

Interpreter模式的应用场合是interpreter模式应用中的难点，只有满足“业务规则频繁变化，且类似的模式不断重复出现，并且容易抽象为语法规则的问题”才适合使用Interpreter模式。

使用Interpreter模式来表示文法规则，从而可以使用面向对象技巧来方便地“扩展”文法。

Interpreter模式比较适合简单的文法表示，对于复杂的文法表示，Interpreter模式会产生比较大的类层次结构，这时候就不应该采用Interpreter模式了。

效率不是一个Interpreter关心的关键问题。最高效的解释器通常不是通过直接解释语法分析树实现的，而是首先将它们转换成另一种形式。例如：正则表达式通常被转换成状态机。但即使在这种情况下，如果效率不是一个关键问题，转换器仍可用Interpreter模式实现，该模式仍是有用的。

下面是一个将中文数字转换成阿拉伯数字的例子，其中用到了Interpreter：

// Interpreter.h

#include <iostream>

#include <string>

#include <map>

#include <vector>

using namespace std;

// 下面两个全局函数，用于处理宽字符中文

// 字符串转换：string to wstring

wstring s2ws(const std::string& s)

{

setlocale(LC_ALL, "chs");

const char* _Source = s.c_str();

size_t _Dsize = s.size() + 1;

wchar_t *_Dest = new wchar_t[_Dsize];

wmemset(_Dest, 0, _Dsize);

mbstowcs(_Dest,_Source,_Dsize);

std::wstring result = _Dest;

delete []_Dest;

setlocale(LC_ALL, "C");

return result;

}

// 字符串转换：wstring to string

string ws2s(const std::wstring& ws)

{

std::string curLocale = setlocale(LC_ALL, NULL); // curLocale = "C";

setlocale(LC_ALL, "chs");

const wchar_t* _Source = ws.c_str();

size_t _Dsize = 2 * ws.size() + 1;

char *_Dest = new char[_Dsize];

memset(_Dest,0,_Dsize);

wcstombs(_Dest,_Source,_Dsize);

std::string result = _Dest;

delete []_Dest;

setlocale(LC_ALL, curLocale.c_str());

return result;

}

// Context类，用于保存需要转换的中文字符串和转换后的数据

class Context

{

private:

wstring statement; // 需要转换的中文字符串

int data; // 转换后的数据

public:

Context(wstring statement) : statement(statement)

{

data = 0;

}

~Context()

{

cout << "in the destructor of Context..." << endl;

}

public:

void set_statement(wstring statement)

{

this->statement = statement;

}

wstring get_statement()

{

return statement;

}

void set_data(int data)

{

this->data = data;

}

int get_data()

{

return data;

}

};

// 抽象Expression

class Expression

{

protected:

map<string, int> dictionary; // 字典，保存与中文对应的阿拉伯数字

public:

Expression()

{

dictionary.insert(pair<string, int>("一", 1));

dictionary.insert(pair<string, int>("二", 2));

dictionary.insert(pair<string, int>("三", 3));

dictionary.insert(pair<string, int>("四", 4));

dictionary.insert(pair<string, int>("五", 5));

dictionary.insert(pair<string, int>("六", 6));

dictionary.insert(pair<string, int>("七", 7));

dictionary.insert(pair<string, int>("八", 8));

dictionary.insert(pair<string, int>("九", 9));

dictionary.insert(pair<string, int>("零", 0));

}

virtual ~Expression()

{

cout << "in the destructor of Expression..." << endl;

}

public:

virtual void Interpret(Context& ctx)

{

wstring statement = ctx.get_statement(); // 从ctx中取出中文字符串

wstring zero_string(s2ws("零")); // 宽字符串“零”

//wstring tempstr = statement.substr(statement.size() - 1);

if(statement.size() == 0) // 从ctx中取出的中文字符串长度等于

{

return; // 处理完成，返回

}

else if(statement.substr(statement.size() - 1) == zero_string) // 如果宽字符串中最后一个宽字符为“零”

{

wstring tempstr = statement;

tempstr = tempstr.substr(0, tempstr.size() - 1); // 将最后的“零”去掉

ctx.set_statement(tempstr);

return;

}

else

{

for(map<string, int>::iterator it = dictionary.begin(); it != dictionary.end(); it++)

{

int value = it->second; // 从字典中取出对应的数字

wstring tempstr2 = statement.substr(statement.size() - get_length());

wstring tempstr3 = s2ws(it->first) + get_postfix();

if(statement.substr(statement.size() - get_length()) == (s2ws(it->first) + get_postfix()))

{

int temp_data = ctx.get_data(); // 取出ctx中保存的数据

temp_data += value * Multiplier();

ctx.set_data(temp_data);

wstring temp_str = ctx.get_statement();

temp_str = temp_str.substr(0, temp_str.size() - get_length());

ctx.set_statement(temp_str);

return;

}

int get_length()

{

return get_postfix().size() + 1;

}

public:

virtual wstring get_postfix() = 0;

virtual int Multiplier() = 0;

};

// GeExpression

class GeExpression : public Expression

{

public:

wstring get_postfix()

{

return s2ws("");

}

int Multiplier()

{

return 1;

}

int get_length()

{

return 1;

}

public:

~GeExpression()

{

cout << "in the destructor of GeExpression..." << endl;

}

};

// ShExpression

class ShExpression : public Expression

{

public:

wstring get_postfix()

{

return s2ws("十");

}

int Multiplier()

{

return 10;

}

public:

~ShExpression()

{

cout << "in the destructor of ShExpression..." << endl;

}

};

// BaExpression

class BaExpression : public Expression

{

public:

wstring get_postfix()

{

return s2ws("百");

}

int Multiplier()

{

return 100;

}

public:

~BaExpression()

{

cout << "in the destructor of BaExpression..." << endl;

}

};

// QiExpression

class QiExpression : public Expression

{

public:

wstring get_postfix()

{

return s2ws("千");

}

int Multiplier()

{

return 1000;

}

public:

~QiExpression()

{

cout << "in the destructor of QiExpression..." << endl;

}

};

// WaExpression

class WaExpression : public Expression

{

public:

wstring get_postfix()

{

return s2ws("万");

}

int Multiplier()

{

return 10000;

}

void Interpret(Context& ctx)

{

wstring statement = ctx.get_statement(); //一十九零七百三十一万

wstring zero_string(s2ws("零"));

if(statement.size() == 0)

{

return; // 处理完成，返回

}

else if(statement.substr(statement.size() - 1) == zero_string)

{

wstring tempstr = statement;

tempstr = tempstr.substr(0, tempstr.size() - 1);

ctx.set_statement(tempstr);

return;

}

else

{

vector<Expression*> stx_tree;

stx_tree.push_back(new GeExpression());

stx_tree.push_back(new ShExpression());

stx_tree.push_back(new BaExpression());

stx_tree.push_back(new QiExpression());

if(statement.substr(statement.size() - 1) == get_postfix())

{

int temp_data = ctx.get_data();

ctx.set_data(0);

statement = statement.substr(0, statement.size() - 1);

ctx.set_statement(statement);

for(vector<Expression*>::iterator it = stx_tree.begin(); it != stx_tree.end(); it++)

{

if(ctx.get_statement().size() == 0) break;

(*it)->Interpret(ctx);

}

ctx.set_data(temp_data + ctx.get_data() * Multiplier());

// 删除语法树中动态构造的元素，以免内存泄漏

for(vector<Expression*>::iterator it = stx_tree.begin(); it != stx_tree.end(); )

{

Expression *temp = *it;

it = stx_tree.erase(it);

delete temp;

}

return;

}

public:

~WaExpression()

{

cout << "in the destructor of WaExpression..." << endl;

}

};

// YiExpression

class YiExpression : public Expression

{

public:

wstring get_postfix()

{

return s2ws("亿");

}

int Multiplier()

{

return 100000000;

}

void Interpret(Context& ctx)

{

wstring statement = ctx.get_statement();

wstring zero_string(s2ws("零"));

if(statement.size() == 0)

{

return; // 处理完成，返回

}

else if(statement.substr(statement.size() - 1) == zero_string)

{

wstring tempstr = statement;

tempstr = tempstr.substr(0, tempstr.size() - 1);

ctx.set_statement(tempstr);

return;

}

else

{

vector<Expression*> stx_tree;

stx_tree.push_back(new GeExpression());

stx_tree.push_back(new ShExpression());

stx_tree.push_back(new BaExpression());

stx_tree.push_back(new QiExpression());

stx_tree.push_back(new WaExpression());

if(statement.substr(statement.size() - 1) == get_postfix())

{

int temp_data = ctx.get_data();

ctx.set_data(0);

statement = statement.substr(0, statement.size() - 1);

ctx.set_statement(statement);

for(vector<Expression*>::iterator it = stx_tree.begin(); it != stx_tree.end(); it++)

{

if(ctx.get_statement().size() == 0) break;

(*it)->Interpret(ctx);

}

ctx.set_data(temp_data + ctx.get_data() * Multiplier());

// 删除语法树中动态构造的元素，以免内存泄漏

for(vector<Expression*>::iterator it = stx_tree.begin(); it != stx_tree.end(); )

{

Expression *temp = *it;

it = stx_tree.erase(it);

delete temp;

}

return;

}

public:

~YiExpression()

{

cout << "in the destructor of YiExpression..." << endl;

}

};

// Interpreter.cpp

#include "Interpreter.h"

int main(int argc, char **argv)

{

wstring chinese_number = s2ws("一十九亿零七百三十一万六千八百三十九");

Context ctx(chinese_number);

vector<Expression*> stx_tree;

stx_tree.push_back(new GeExpression());

stx_tree.push_back(new ShExpression());

stx_tree.push_back(new BaExpression());

stx_tree.push_back(new QiExpression());

stx_tree.push_back(new WaExpression());

stx_tree.push_back(new YiExpression());

for(vector<Expression*>::iterator it = stx_tree.begin(); it != stx_tree.end(); it++)

{

(*it)->Interpret(ctx);

}

cout << ws2s(chinese_number) << " = " << ctx.get_data() << endl;

// 删除语法树中动态构造的元素，以免内存泄漏

for(vector<Expression*>::iterator it = stx_tree.begin(); it != stx_tree.end(); )

{

Expression *temp = *it;

it = stx_tree.erase(it);

delete temp;

}

return 0;

}

上述代码运行结果：

in the destructor of GeExpression...