ActionScript 3 (Flash/AIR): GoF デザインパターン – Interpreter

ツリー構造で構文解析結果を表す際に使用されます。が、何に使うのかはイマイチよくわかりません。

例えば “1+2*3” という文字列を AS3 に解釈させて 7 を算出させるために使うそうです。ゲームのアルゴリズムに使えたりするかも。

1+2*3 は、 123*+ という書き方にできます。これは逆ポーランド記法といい、一旦この記法に変換した後に、数値と演算子を判別しながら処理していきます。

ActionScript: Interpreter.as

package jp.feb19.gof.interpreter
{
	public class Interpreter
	{
		public function Interpreter()
		{
		}
		
		public function precedence(a:String, b:String):Boolean
		{
			var high:String = "*/";
			var low:String  = "+-";
			if (a == "(") return false;
			if (a == ")" && b == "(") return false;
			if (b == "(") return false;
			if (b == ")") return true;
			if (high.indexOf(a) > -1 && low.indexOf(b) > -1) return true;
			if (high.indexOf(a) > -1 && high.indexOf(b) > -1) return true;
			if (low.indexOf(a) > -1 && low.indexOf(b) > -1) return true;
			return false;
		}
		
		public function convertToPostfix( value:String ):String
		{
			var stString:StackString = new StackString();
			var result:String = "";
			var operator:String = "+-*/()";
			var topsym:String = "+";
			var isEmpty:Boolean = false;
			
			for (var i:int = 0; i < value.length; i++)
			{
				if (operator.indexOf(value.charAt(i)) == -1)
				{
					result += value.charAt(i);
				}
				else
				{
					while ( !(isEmpty = stString.isEmpty()) &&
						precedence(topsym = stString.pop(), value.charAt(i)) )
					{
						result += topsym;
					}
					if ( !isEmpty )
						stString.push( topsym );
					if ( isEmpty || value.charAt(i) != ")" )
						stString.push( value.charAt(i) );
					else
						topsym = stString.pop();
				}
			}
			while( !stString.isEmpty() )
				result += stString.pop();
			
			return result;
		}
		
		public function evaluate( value:String ):Number
		{
			var stNumber:StackNumber = new StackNumber();
			var operator:String = "+-*/";
			var a:Number = 0;
			var b:Number = 0;
			for (var i:int = 0; i <value.length; i++)
			{
				if (operator.indexOf( value.charAt(i) ) == -1)
				{
					stNumber.push(Number(value.charAt(i)));
				}
				else
				{
					b = stNumber.pop();
					a = stNumber.pop();
					switch(value.charAt(i))
					{
						case "+": a = a + b; break;
						case "-": a = a - b; break;
						case "*": a = a * b; break;
						case "/": a = a / b; break;
					}
					stNumber.push( a );
				}
			}
			
			return stNumber.pop();
		}
	}
}

ActionScript: StackNumber.as

package jp.feb19.gof.interpreter
{
	public class StackNumber
	{
		private var _stack:Array;
		private var _sp:int;
		
		public function StackNumber()
		{
			_sp = -1;
			_stack = [];
		}
		
		public function push(num:Number):void
		{
			_stack[++_sp] = num;
		}
		
		public function pop():Number
		{
			return (isEmpty()) ? 0 : _stack[_sp--];
		}
		
		public function isEmpty():Boolean
		{
			return _sp <= -1;
		}
	}
}

ActionScript: StackString.as

package jp.feb19.gof.interpreter
{
	public class StackString
	{
		private var _stack:Array;
		private var _sp:int;
		
		public function StackString()
		{
			_sp = -1;
			_stack = [];
		}
		
		public function push(str:String):void
		{
			_stack[++_sp] = str;
		}
		
		public function pop():String
		{
			return (isEmpty()) ? "" : _stack[_sp--];
		}
		
		public function isEmpty():Boolean
		{
			return _sp <= -1;
		}
	}
}

ActionScript: InterpreterTest.as

package jp.feb19.gof.interpreter
{
	import flash.display.Sprite;
	
	public class InterpreterTest extends Sprite
	{
		public function InterpreterTest()
		{
			super();
			
			var input:String = "1+2*3";
			trace(input);
			var interpreter:Interpreter = new Interpreter();
			var postfix:String = interpreter.convertToPostfix(input);
			trace(postfix);
			var result:Number = interpreter.evaluate(postfix);
			trace(result);
		}
	}
}

テストクラス

1+2*3
123*+
7

オリジナルプログラミング言語とか作るときに使ったりするそうです。電卓とか作ったりするときにも使えるかも。あとはプログラミンみたいなサイトを作るときとか?

SQL 文も逆ポーラン記法的らしくて、文は Interpreter で読まれているそうです。