2016/09/16 13:00- python

[前回迄]
	前々回、前回は、前期の復習をした
		Module の作り方から、データ型(Stack/Queue)、Class の作り方
	# 前回の予告 : オブジェクト指向の話
	#	予定を変更して、Stack を使ってみよう

	式の計算の仕方 ( # コンパイラゼミで話題にする予定だが、こっちに振る )
		[逆ポーランド方式計算]
		[演算子勇戦法]

	逆ポーランド方式計算
		式の表現方法の一つで、
			演算子を、被演算対象の後ろに置く記法
			例:					(中置形式)
				1 2 +		->	1 + 2			1 に 2 を加える
				1 2 * 3 +	->	1 * 2 + 3		1 に 2 を掛けて 3 を加える
				1 2 3 * +	->	1 + 2 * 3		1 に 2 と 3 を掛けた物を加える

			逆ポーランド方式
				かっこが不要 ( 順番を変更すれば、計算順序が指定できる )
					スタックがあれば、簡単に計算できる
						-> コンパイラの中間形式に採用される事も多い
							# 構文木にしてしまえば、どうでも良いのだが..
				日本語との相性が良い
					日本語プログラミング言語で採用されている事がある

	演習 1. 逆ポーランド方式でかかれた式を計算するプログラム(電卓)

	アルゴリズム
		値スタックを用意する
		先頭から word ( 数か演算子 ) を読み取る
			もし、word が数なら、無条件に stack に積む
			そうでなく(もし、演算子 ) なら、stack top の二つの数を計算し、
				その結果を stack 積む

		制限:
			数は整数
			演算子は、四則(+,-,*,/)と余り(%)と、? (スタックトップを出力)
		例:
				5	2		*		3		+		?
			|	|	|		|		|		|		|
			[]	|	|		|		|		|		|
				[5]	|		|		|		|		|
					[5,2]	|		|		|		|
							[10]	|		|		|
									[10,3]	|		|
											[13]	|	
													[13] -> 13

				5	2		3		*		+		?
			|	|	|		|		|		|		|
			[]	|	|		|		|		|		|
				[5]	|		|		|		|		|
					[5,2]	|		|		|		|
							[5,2,3]	|		|		|
									[5,6]	|		|
											[11]	|
													[11] -> 11

	演習 1a. 次のような演算子を増やししてみる
		dup -> スタックトップを複製する
				1 	dup
			|	|	|
			[]	[1]	[1,1]

		change -> スタックトップの上の二つを交換する

		...

		# 色々な演算子を増やすと Forth という言語になる

	演習 2. 中置形式の式を逆ポーランド方式変更する

	アルゴリズム
		値スタックを用意する
		先頭から word ( 数か演算子 ) を読み取る
			もし、数なら、そのまま出力
			そうでなければ(演算子なので、)
				演算の優先順位によって、スタックの優先順位の小くない物を出力し、
				最後に、入力した、演算子をスタックに積む
					入力がおわったら、スタックの中身を出力する

			1	+	2	+	3
		|	|	|	|	|	|	|
		[]	|	|	|	|	|	|
			[]	|	|	|	|	|
				[+]	|	|	|	|
					[+]	|	｜	|
						[+]	｜	|
							[+]	[]
			1		2	+	3	+


			1	+	2	*		3
		|	|	|	|	|		|		|
		[]	|	|	|	|		|		|
			[]	|	|	|		|		|
				[+]	|	|		|		|
					[+]	|		｜		|
						[+,*]	｜		|
								[+,*]	
			1		2			3		* +

		+,-	0
		*,/	1

	演習 2a 演算子を増やす
	演習 2b 優先順位を右からと左からの比較で別の値を持たせると、
				( と ) も、演算子と同じ形で、扱えて、かっこ付きの式を
				逆ポーランド方式にできる
	演習 2c Inter2ReverPorlish + ReverPorish -> 中置形式が計算
				stack 1 個			stack 1 個
					-> stack 2 個で、いきなり中置形式が計算できる

==