設計模式之美：Interpreter（解釋器） - gaochundong－IT工程師數位筆記本

文章出處

索引

意圖
結構
參與者
適用性
效果
相關模式
實現
- 實現方式（一）：Interpreter 模式結構樣式代碼。
- 實現方式（二）：解釋波蘭表達式（Polish Notation）。

意圖

給定一個語言，定義它的文法的一種表示，并定義一個解釋器，這個解釋器使用該表示來解釋語言中的句子。

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

結構

參與者

AbstractExpression

聲明一個抽象的解釋操作，這個接口為抽象語法樹中所有的節點所共享。

TerminalExpression

實現與文法中的終結符相關聯的解釋操作。
一個句子中的每一個終結符需要該類的一個實例。

NonterminalExpression

對文法中的規則的解釋操作。

Context

包含解釋器之外的一些全局信息。

Client

構建表示該語法定義的語言中一個特定的句子的抽象語法樹。
調用解釋操作

適用性

當有個語言需要解釋執行，并且你可將該語言中的句子表示為一個抽象語法樹時，可以使用 Interpreter 模式。

當存在以下情況時效果最好：

該文法簡單對于復雜的文法，文法的類層次變得龐大而無法管理。
效率不是一個關鍵問題，最高效的解釋器通常不是通過直接解釋語法分析樹實現的，而是首先將它們轉換成另一種形式。

效果

易于改變和擴展文法。
易于實現文法。
復雜的文法難以維護。
增加了新的解釋表達式的方式。

相關模式

抽象語法樹是一個 Composite 模式的實例。
可以使用 Flyweight 模式在抽象語法樹中共享終結符。
可以使用 Iterator 模式遍歷解釋器結構。
可以使用 Visitor 模式在一個類中維護抽象語法樹中的各個節點的行為。

實現

實現方式（一）：Interpreter 模式結構樣式代碼。

TerminalExpression：實現解釋 Terminal Symbols 的語法。

NonTerminalExpression：聚合一到多個 Expression，Expression 可以是 TerminalExpression，也可以是 NonTerminalExpression。。

 1 namespace InterpreterPattern.Implementation1
 2 {
 3   public class Context
 4   {
 5     public Context(string name)
 6     {
 7       Name = name;
 8     }
 9 
10     public string Name { get; private set; }
11   }
12 
13   public abstract class ExpressionBase
14   {
15     public abstract void Interpret(Context context);
16   }
17 
18   public class TerminalExpression : ExpressionBase
19   {
20     public override void Interpret(Context context)
21     {
22       Console.WriteLine("Terminal Symbol {0}.", context.Name);
23     }
24   }
25 
26   public class NonTerminalExpression : ExpressionBase
27   {
28     public ExpressionBase Expression1 { get; set; }
29     public ExpressionBase Expression2 { get; set; }
30 
31     public override void Interpret(Context context)
32     {
33       Console.WriteLine("Non Terminal Symbol {0}.", context.Name);
34       Expression1.Interpret(context);
35       Expression2.Interpret(context);
36     }
37   }
38 
39   public class Client
40   {
41     public void TestCase1()
42     {
43       var context = new Context("Hello World");
44       var root = new NonTerminalExpression
45       {
46         Expression1 = new TerminalExpression(),
47         Expression2 = new TerminalExpression()
48       };
49       root.Interpret(context);
50     }
51   }
52 }

實現方式（二）：解釋波蘭表達式（Polish Notation）。

中綴表達式

中綴表達式中，二元運算符總是置于與之相關的兩個運算對象之間，根據運算符間的優先關系來確定運算的次序，同時考慮括號規則。
比如： 2 + 3 * (5 - 1)

前綴表達式

波蘭邏輯學家 J.Lukasiewicz 于 1929 年提出了一種不需要括號的表示法，將運算符寫在運算對象之前，也就是前綴表達式，即波蘭式（Polish Notation, PN）。
比如：2 + 3 * (5 - 1) 這個表達式的前綴表達式為 + 2 * 3 - 5 1。

后綴表達式

后綴表達式也稱為逆波蘭式（Reverse Polish Notation, RPN），和前綴表達式相反，是將運算符號放置于運算對象之后。
比如：2 + 3 * (5 - 1) 用逆波蘭式來表示則是：2 3 5 1 - * +。

  1 namespace InterpreterPattern.Implementation2
  2 {
  3   public interface IExpression
  4   {
  5     int Evaluate();
  6   }
  7 
  8   public class IntegerTerminalExpression : IExpression
  9   {
 10     int _value;
 11 
 12     public IntegerTerminalExpression(int value)
 13     {
 14       _value = value;
 15     }
 16 
 17     public int Evaluate()
 18     {
 19       return _value;
 20     }
 21 
 22     public override string ToString()
 23     {
 24       return _value.ToString();
 25     }
 26   }
 27 
 28   public class AdditionNonterminalExpression : IExpression
 29   {
 30     private IExpression _expr1;
 31     private IExpression _expr2;
 32 
 33     public AdditionNonterminalExpression(
 34       IExpression expr1,
 35       IExpression expr2)
 36     {
 37       _expr1 = expr1;
 38       _expr2 = expr2;
 39     }
 40 
 41     public int Evaluate()
 42     {
 43       int value1 = _expr1.Evaluate();
 44       int value2 = _expr2.Evaluate();
 45       return value1 + value2;
 46     }
 47 
 48     public override string ToString()
 49     {
 50       return string.Format("({0} + {1})", _expr1, _expr2);
 51     }
 52   }
 53 
 54   public class SubtractionNonterminalExpression : IExpression
 55   {
 56     private IExpression _expr1;
 57     private IExpression _expr2;
 58 
 59     public SubtractionNonterminalExpression(
 60       IExpression expr1,
 61       IExpression expr2)
 62     {
 63       _expr1 = expr1;
 64       _expr2 = expr2;
 65     }
 66 
 67     public int Evaluate()
 68     {
 69       int value1 = _expr1.Evaluate();
 70       int value2 = _expr2.Evaluate();
 71       return value1 - value2;
 72     }
 73 
 74     public override string ToString()
 75     {
 76       return string.Format("({0} - {1})", _expr1, _expr2);
 77     }
 78   }
 79 
 80   public interface IParser
 81   {
 82     IExpression Parse(string polish);
 83   }
 84 
 85   public class Parser : IParser
 86   {
 87     public IExpression Parse(string polish)
 88     {
 89       var symbols = new List<string>(polish.Split(' '));
 90       return ParseNextExpression(symbols);
 91     }
 92 
 93     private IExpression ParseNextExpression(List<string> symbols)
 94     {
 95       int value;
 96       if (int.TryParse(symbols[0], out value))
 97       {
 98         symbols.RemoveAt(0);
 99         return new IntegerTerminalExpression(value);
100       }
101       return ParseNonTerminalExpression(symbols);
102     }
103 
104     private IExpression ParseNonTerminalExpression(List<string> symbols)
105     {
106       var symbol = symbols[0];
107       symbols.RemoveAt(0);
108 
109       var expr1 = ParseNextExpression(symbols);
110       var expr2 = ParseNextExpression(symbols);
111 
112       switch (symbol)
113       {
114         case "+":
115           return new AdditionNonterminalExpression(expr1, expr2);
116         case "-":
117           return new SubtractionNonterminalExpression(expr1, expr2);
118         default:
119           {
120             string message = string.Format("Invalid Symbol ({0})", symbol);
121             throw new InvalidOperationException(message);
122           }
123       }
124     }
125   }
126 
127   public class Client
128   {
129     public void TestCase2()
130     {
131       IParser parser = new Parser();
132 
133       var commands =
134         new string[]
135         {
136           "+ 1 2",
137           "- 3 4",
138           "+ - 5 6 7",
139           "+ 8 - 9 1",
140           "+ - + - - 2 3 4 + - -5 6 + -7 8 9 0"
141         };
142 
143       foreach (var command in commands)
144       {
145         IExpression expression = parser.Parse(command);
146         Console.WriteLine("{0} = {1}", expression, expression.Evaluate());
147       }
148 
149       // Results:
150       // (1 + 2) = 3
151       // (3 - 4) = -1
152       // ((5 - 6) + 7) = 6
153       // (8 + (9 - 1)) = 16
154       // (((((2 - 3) - 4) + ((-5 - 6) + (-7 + 8))) - 9) + 0) = -24
155     }
156   }
157 }