1-15. Interpreter パターン

与えられた言語に対して、その文法表現とインタープリタを定義します。

サンプルとして数式を解釈する例を示します。
文法表現を以下のように定義します。

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;
		}
	}
}