Interpreter パターン
Interpreter pattern - Wikipedia
DSL(Domain Specific Lanuage、ドメイン特化言語)を作るときに良いっぽい。要するにAST(Abstract Syntax Tree)を作るときに使うイメージかな?
以下のコードは例の如くwikipediaにあったコードをC++に書きなおしたもの。サンプルは逆ポーランド記法で記述された足し算と引き算からなる数式を評価するもの。めんどくさかったのでメモリの解放してない。
#include <iostream> #include <sstream> #include <string> #include <map> #include <stack> #include <vector> #include <algorithm> using namespace std; /**********************************************************************************/ //一番親玉の抽象クラス class Expression { public : virtual int Interpret(map<string, Expression*> variables) = 0; }; //数値型 class Number : public Expression { public : Number(int number){this->number_ = number;} int Interpret(map<string, Expression*> variables){ return number_;} private : int number_; }; //二項演算子系(+と−) class Plus : public Expression { public : Plus(Expression* lhs, Expression* rhs) : lhs_(lhs), rhs_(rhs){} int Interpret(map<string, Expression*> variables){ return lhs_->Interpret(variables) + rhs_->Interpret(variables); } private : //左辺値と右辺値 Expression *lhs_; Expression *rhs_; }; class Minus : public Expression { public : Minus(Expression* lhs, Expression* rhs) : lhs_(lhs), rhs_(rhs){} int Interpret(map<string, Expression*> variables){ return lhs_->Interpret(variables) - rhs_->Interpret(variables); } private : //左辺値と右辺値 Expression *lhs_; Expression *rhs_; }; //変数(not 数値) class Variable : public Expression { public : Variable(string name) : name_(name){} int Interpret(map<string, Expression*> variables){ //割り当てられてる変数に見つからなかったら0とする if(variables.find(name_) == variables.end()){return 0;} //割り当てられている物(ここでは数値型)に対して再帰的に評価実行 return variables[name_]->Interpret(variables); } private : string name_; }; //評価器 class Evaluator : public Expression { public : int Interpret(map<string, Expression*> context){ return syntaxTree_->Interpret(context); } static void Print(string x){ cout << x << endl; } Evaluator(string expression) { //抽象構文木を格納する変数 stack<Expression*> expressionStack; //文字列を空白で分割 istringstream iss(expression); vector<string> expression_separated; copy(istream_iterator<string>(iss), istream_iterator<string>(), back_inserter(expression_separated)); //Just for check //std::for_each(expression_separated.begin(), expression_separated.end(), Print); //分割文字全部で抽象構文木(Abstract Syntax Tree, AST)を生成 for(vector<string>::iterator x = expression_separated.begin(); x != expression_separated.end(); x++){ if(*x == "+"){ Expression *rhs = expressionStack.top(); expressionStack.pop(); Expression *lhs = expressionStack.top(); expressionStack.pop(); Expression* subExpression = new Plus(lhs, rhs); expressionStack.push( subExpression ); } else if(*x == "-"){ Expression *rhs = expressionStack.top(); expressionStack.pop(); Expression *lhs = expressionStack.top(); expressionStack.pop(); Expression *subExpression = new Minus(lhs, rhs); expressionStack.push( subExpression ); } else{ expressionStack.push( new Variable(*x) ); } } //木の一番上を保持 syntaxTree_ = expressionStack.top(); expressionStack.pop(); } private : Expression* syntaxTree_; }; /**********************************************************************************/ //main int main() { //評価したい文字列を記述 string expression = "w x z - +"; //評価器の生成(内部では抽象構文木の生成) Evaluator * evaluator = new Evaluator(expression); //各変数に値を割り当てる map<string, Expression*> variables; variables.insert(pair<string, Expression*>("w", new Number(5 ))); variables.insert(pair<string, Expression*>("x", new Number(10))); variables.insert(pair<string, Expression*>("z", new Number(42))); //評価&出力 cout << evaluator->Interpret(variables) << endl; return 0; }
この結果は-27になり、これはexpressionに格納されている逆ポーランド記法の評価結果5 + (10 - 42) = -27にちゃんと合う。