サンプルとして数式を解釈する例を示します。
文法表現を以下のように定義します。
expression ::= number | operation | '(' expression ')'
operation ::= expression operator expression
operator ::= '+' | '-' | '*' | '/' | '%'
number ::= { '0' | ... | '9' } +
実行結果:expression=1+(2-3)*4/5%6
exprList=[1.0, 2.0, 3.0, -, 4.0, *, +, 5.0, /, 6.0, %]
-0.6
package design_pattern;
import java.util.Deque;
import java.util.LinkedList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* Interpreter パターン
* GoF
*
* 与えられた言語に対して、その文法表現とインタープリタを定義します。
*
* サンプルとして数式を解釈する例を示します。
* 文法表現を以下のように定義します。
* <pre>
* expression ::= number | operation | '(' expression ')'
* operation ::= expression operator expression
* operator ::= '+' | '-' | '*' | '/' | '%'
* number ::= { '0' | ... | '9' } +
* </pre>
* 実行結果:
* <pre>
* expression=1+(2-3)*4/5%6
* exprList=[1.0, 2.0, 3.0, -, 4.0, *, +, 5.0, /, 6.0, %]
* -0.6
* </pre>
*
* @author 2015/05/29 matsushima
*/
public class InterpreterSample {
/**
* main
*
* @param args
*/
public static void main(String[] args) {
Parser parser = new InterpreterSample().new Parser();
parser.parse(args.length >= 1 ? args[0] : "1+(2-3)*4/5%6");
double value = parser.interpret();
System.out.println(value);
}
/** 数式のパーサ。 */
public class Parser {
private Pattern pattern = Pattern.compile("(\\d+)|([+\\-*/%(])|(\\))");
private LinkedList<Expr> exprList; // パースした数式の BNF リスト
/** 数式のパース。 */
public void parse(String expression) {
System.out.println("expression=" + expression);
exprList = new LinkedList<>();
Deque<OperatorExpr> operStack = new LinkedList<>(); // 演算子スタック
Matcher matcher = pattern.matcher(expression);
while (matcher.find()) {
String token = matcher.group();
if (null != matcher.group(1)) { // 123
// BNF リストに追加
this.exprList.add(new NumberExpr(token));
} else if (null != matcher.group(2)) { // +-*/%(
OperatorExpr expr = new OperatorExpr(token);
if (!"(".equals(token)
&& !operStack.isEmpty()
&& expr.priority <= operStack.peek().priority) {
// 優先順位の高い演算子を取り出し
do {
this.exprList.add(operStack.pop());
} while (!operStack.isEmpty()
&& expr.priority >= operStack.peek().priority);
}
// BNF リストに追加
operStack.push(expr);
} else if (null != matcher.group(3)) { // )
// "(" まで演算子を取り出し
while (!((OperatorExpr)operStack.peek()).operator.equals("(")) {
this.exprList.add(operStack.pop());
}
operStack.pop();
}
}
this.exprList.addAll(operStack);
System.out.println("exprList=" + this.exprList);
}
/** パースした数式の計算。 */
public double interpret() {
Deque<Double> valueStack = new LinkedList<>();
for (Expr expr: this.exprList) {
expr.interpret(valueStack);
}
return valueStack.pop();
}
}
/** expression のインターフェース。 */
public abstract class Expr {
public abstract void interpret(Deque<Double> valueStack);
}
/** number。 */
public class NumberExpr extends Expr {
public double value;
public NumberExpr(String value) {
this.value = Double.valueOf(value);
}
@Override
public void interpret(Deque<Double> valueStack) {
valueStack.push(this.value);
}
@Override
public String toString() {
return String.valueOf(this.value);
}
}
/** operator。 */
public class OperatorExpr extends Expr {
public String operator;
public int priority;
public OperatorExpr(String str) {
this.operator = str;
switch (this.operator) {
case "+": this.priority = 1; break;
case "-": this.priority = 1; break;
case "*": this.priority = 2; break;
case "/": this.priority = 2; break;
case "%": this.priority = 2; break;
case "(": this.priority = 0; break;
default: throw new RuntimeException(this.operator);
}
}
@Override
public void interpret(Deque<Double> valueStack) {
double value1 = valueStack.pop();
double value2 = valueStack.pop();
switch (this.operator) {
case "+": valueStack.push(value2 + value1); break;
case "-": valueStack.push(value2 - value1); break;
case "*": valueStack.push(value2 * value1); break;
case "/": valueStack.push(value2 / value1); break;
case "%": valueStack.push(value2 % value1); break;
default: throw new RuntimeException(this.operator);
}
}
@Override
public String toString() {
return this.operator;
}
}
}
