四則演算を正しく扱う電卓が欲しい。

(1)

プログラミング言語 I 第 14 回オブジェクト指向

埼玉大学工学部電気電子システム工学科伊藤和人

(2)

要求

四則演算を正しく扱う電卓が欲しい。

100 円ショップで売っている電卓

でも本当は 7 でなければならない

1 + 2 × 3 = 9 になる

1 + 2 × 3 = 7 になる電卓が欲しい

(3)

問題の分析

間違いの原因は、加算と乗算の優先順位を考慮していないこと

1 + 2 × 3

複数の演算子を比較し、優先順位にしたがって演算を実行する

過去に入力した演算子を記憶する必要あり

(4)

スタックを利用

スタック = 本を積み重ねたもの

後入れ、先出しのデータ管理方式

Last-In, First-Out (LIFO)

(5)

スタックを用いた演算実行

計算例

数値のスタックを用意

1 + 2 × 3

1

1 2

数値スタック

直前演算子 ( なし ) +

¹

+

¹

1 +

¹

2 入力

1 1 2

+

¹

×

²

+

¹

×

²

3 ×

²

2 3

=

1 7

+

¹

6 =

1 1 2

答え

(6)

スタックの実現

配列によってスタックを表す

データを積む位置、取り出す位置

・・・常にスタックの頂上

スタックの頂上を表す変数 = スタックポインタ int stack[100];

int sp=99;

例スタック本体

スタックポインタ

スタックは上位 ( 大きな添え字 ) から

下位 ( 小さな添え字 ) に向かってデータを積む

大域変数として用意

(7)

スタックの操作

データをスタックに積む　　　 push 操作

スタックからデータを取り出す　　　 pop 操作

void push( int v ) { stack[sp -- ] = v;

}

int pop( void )

{ return stack[++sp];

}

sp 位置にデータを入れて、 sp を減少

sp を増加し、

sp 位置の

データを読出し

(8)

電卓プログラム例 1

int type, value;

char op, op1=' ', op2 =' ';

while( 1 ){

InputData( &type, &op, &value );

if( type == VALUE ) push( value );

else if( type == OPERATOR ){

if( op2 != ' ' ){ execute( op2 ); op2 = ' '; } if( op1 == ' ' ) op1 = op;

else if( op1 == '*' || op1 == '/' ){

execute( op1 ); op1 = op;

}else{ /* (op1 == '+' || op1 == ' - ') */

if( op == '*' || op == '/' ) op2 = op;

else{ execute( op1 ); op1 = op; } }else{ } /* type == EQUAL */

if( op2 != ' ' ){ execute( op2 ); op2 = ' '; } if( op1 != ' ' ){ execute( op1 ); op1 = ' '; } } }

優先順位に従い先の演算を実行演算子を

保留

優先順位に従い演算を保留

入力データ読み取り

数値、演算子、 ‘=’

(9)

電卓プログラム例 1( 続き )

void execute( char op ){

int n1, n2;

n2 = pop();

n1 = pop();

switch( op ){

case '+': n1 = n1+n2; break;

case '

-

': n1 = n1-n2; break;

case '': n1 = n1n2; break;

case '

/

': n1 = n1/n2; break;

} push( n1 );

}

スタック先頭の 2 つの数値を取り出し、

演算結果をスタックに積む

n1, n2 の順序に注意

(10)

電卓プログラムを拡張する

加算・減算と乗算・除算の 2 種類の優先順位

⇒ op1, op2 の 2 つの変数によって優先順位　　を実現可能

⇒ ただし、面倒な場合分けが必要

例えば、べき乗 (x

^y

) を組み込む

優先順位は 3 種類

⇒ さらに場合分けが複雑に

演算子についてもスタックを利用することで

場合分けを簡単に

(11)

演算子のスタックを利用

if( type == OPERATOR ){

while( ! empty() ){

if( op == '+' || op == '

-

' ){

op1 = pop();

execute( op1 );

}else if( op == '*' || op == '/' ){

op1 = pop();

if( op1 == '*' || op1 == '/' || op1 == '^' ){

execute( op1 );

}else{

push( op1 );

break;

} }

} push( op );

}

演算子スタックが空でないスタック上演算の

優先順位は op 以上

演算 op1 の優先順位が演算 op 以上なので

演算 op1 を実行

演算 op の優先順位が高い

ので op1 をスタックに戻す

演算 op をスタックに積む

(12)

問題点

数値のスタックと演算子のスタック

2 つのスタックを区別する必要あり

スタックを引数に取る方法

専用の関数を用いる方法

push_data( value )

pop_data() push_op( op ) pop_op()

push( stk_data, value )

pop( stk_data ) push( stk_op, op ) pop( stk_op )

あくまでも関数 ( 手続き ) が主体であることに原因がある

⇒ 型の問題あり

⇒ 効率が悪い

同じ型のスタックが

2

個ある場合など

(13)

オブジェクト指向

数値スタック、演算子スタックがあり、

スタックに対して push 操作や pop 操作を行う

オブジェクト ( スタック ) が主体

data_stack.push( value )

data_stack.pop() op_stack.push( op ) op_stack.pop()

数値スタック演算子スタック

この考え方をオブジェクト指向という

(14)

クラス

オブジェクトの型を定義するもの

class CValueStack { public:

CValueStack();

virtual ~CValueStack();

void push( int v );

int pop( void );

int empty( void ){ return sp==99; } private:

int stack[100];

int sp;

};

データ

( 記憶領域とスタックポインタ ) メソッド

( スタック操作関数 ) コンストラクタおよびデストラクタ

データと操作 ( メソッド ) が一体化されている

インライン記述

(15)

クラス ( 続き )

各メンバ関数の定義

CValueStack::CValueStack() { sp = 99;

} CValueStack::~CValueStack() { }

void CValueStack::push( int v ) { stack[sp--] = v;

} int CValueStack::pop( void ) { return stack[++sp];

}

コンストラクタ

デストラクタスタックポインタを初期化

Push 操作

Pop 操作

この場合何もしない

(16)

インスタンスを作る

クラスからインスタンス ( オブジェクト ) を作る

CValueStack data_stack;

COpStack op_stack;

int n;

data_stack.push( 100 );

data_stack.push( -200 );

op_stack.push( '+' );

n = data_stack.pop();

Push 操作 Pop 操作

インスタンス作成

インスタンスに対して

(17)

クラスを用いる利点

オブジェクト指向の考えを実現する

例 : スタックオブジェクトが存在し、スタックに対して push や pop といった操作を指示する

操作だけを公開し、中身 ( 実装 ) は隠す

例 : スタックについて、利用者はデータの読み書きは push(), pop() といった関数を使用することだけを知っていればよい。 push(), pop() が実際にはどのようなプログラムになっているか、知らなくてよい。

プログラムの再利用が容易になる

スタックを利用したいプログラムに、スタックの

クラスを単純にコピーすればよい

(18)

オブジェクト指向の本当の意味

与えられた要求を実現するプログラムを開発する際に、要求を分析し、プログラムの構造を設計するための考え方

この作業を「モデリング」という要求を分析し、本質を抽出

計算機プログラムとして表現できるように単純化する

オブジェクトの振る舞い、オブジェクト間関係

( オブジェクト指向モデリング )

(19)

モデリング例 : 数独

数独のルール

縦列 (9 マスの列が 9 つあります ) 、横列 (9 マスの列が 9 つあります ) のそれぞれに 1 から 9 までの数字が 1 つずつ入ります

太い線で囲まれた 3 × 3 のブロック ( それぞれ 9 マスあるブロックが 9 つあります ) にも、 1 から 9 までの数字が 1 つずつ入ります

出典

:

朝日新聞

オブジェクトを抽出

マス (9 × 9 個 ) 列 (9 個 ) 行 ( 横列 )(9 個 ) ブロック (9 個 )

要求

ボード (1 個 )

(20)

クラスを整理

各オブジェクトを抽象化するクラスを作る

クラス間の関係を分析

マス CPlace

列 CColumn

行 CRow

ボックス CBox

ボード CBoard

CBoard

¹ ⁸¹

CPlace

CColumn CRow

9

CBox

1 1 1 9

9 9

9

1 1 1

(21)

クラスの役割分担 ( 責務 ) を分析

縦列に 1 から 9 までの数字が 1 つずつ入ります

横列に 1 から 9 までの数字が 1 つずつ入ります

ブロックに 1 から 9 までの数字が 1 つずつ入ります 9 個のマスの集め方が異なるだけで、責務は同じ責務に注目して、クラス CGroup へ抽象化する

CBoard

¹ ⁸¹

CPlace

CGroup

9 1

* 1

(22)

クラスの定義 : CPlace

class CPlace { public:

CPlace();

virtual ~CPlace();

void FixValue( void );

int IsFixed( void );

int IsValueAllowd( int v ){ return aValue[v]; } void ExcludeValue( int v );

private:

int bFixed;

int aValue[10];

int nValue;

};

データ

メソッドコンストラクタおよびデストラクタ

クラス CPlace ( マスを表す )

(23)

クラスの定義 : CPlace

CPlace::CPlace() { int v;

for( v=1 ; v<=9 ; v++ ) aValue[v] = 1;

bFixed = 0;

}

int CPlace::IsFixed( void )

{ if( bFixed ) return nValue;

else return - 1;

}

void CPlace::ExcludeValue( int v ) { if( ! bFixed ) aValue[v] = 0;

}

初期化を行うコンストラクタ

オブジェクトが作られるときに 1 度だけ実行する

マスの値が決定していれば、その値

未定ならば- 1 を返す

マスの値が未定なら

値 v を除外する

(24)

クラスの定義 : CPlace

void CPlace::Fix( void ) { int v, v0;

int nCount = 0;

for( v=1 ; v<=9 ; v++ ){

if( aValue[v] ){

nCount++; v0 = v;

if( nCount == 1 ){ } bFixed = 1;

for( v=0 ; v<9 ; v++ ) aValue[v] = 0;

aValue[v0] = 1;

nValue = v0;

} }

このマスに許される値を数える

唯一可能な値に決定する

許される値が 1 つのみならば、その値に決定

マス ( オブジェクト ) に対して値を決定する

⇒ 値決定はマスの操作として定義する

(25)

クラスの定義 : CGroup

class CGroup { public:

CGroup();

virtual ~CGroup();

void SetPlace( int k, CPlace *p );

void L1Infer( void );

void Fix( void );

private:

CPlace *place[9];

};

データ

⇒ グループを構成する 9 個のマス

メソッドコンストラクタおよびデストラクタ

クラス CGroup

( 列、行、ボックスを表す )

グループを構成する

9

個のマスを登録するためのメソッドレベル

1

の推論値を決定できるマスを選ぶ

(26)

クラスの定義 : CGroup

void CGroup::L1Infer() { int k, v;

for( v=1 ; v<=9 ; v++ ){

for( k=0 ; k<9 ; k++ ){

if( place[k] - >IsFixed() == v ) break;

} if( k<9 ){

for( k=0 ; k<9 ; k++ )

place[k] - >ExcludeValue( v );

} } }

レベル 1 の推論

他の 8 個のマスでは値 v を除外する

値 v に決定した

マスが存在する

(27)

クラスを用いる利点

行、列、ボックスからグループへ抽象化

単に 9 個のマス間の関係のみを考慮

行、列、ボックスの区別は必要ない

CGroup では、 CPlace の実装を知らなくてよい

必ず CPlace のメソッド ( インターフェース ) を経由

CPlace 内の変数 bFixed 、配列 aValue などは意識しない

クラスの役割分担 ( 責務 ) が明確になる

クラス単位でプログラムの再利用が容易になる

隠蔽 ( カプセル化 ) CPlace と CGroup の関係より

( 共通化 )

(28)

クラスの定義 : CBoard

class CBoard { public:

CBoard();

virtual ~CBoard();

void Initialize( void );

void L1Infer( void );

/*

その他のメソッド

(

省略

) */

private:

CPlace place[9][9];

CGroup column[9];

CGroup row[9];

CGroup box[3][3];

};

データ

⇒ 81 個のマス 9 個の列

9 個の行

9 個のボックスメソッド

コンストラクタおよびデストラクタ

クラス CBoard

(29)

クラスの定義 : CBoard

void CBoard::Initialize() { int i,j,bx,by;

for( i=0 ; i<9 ; i++ )

for( j=0 ; j<9 ; j++ ){

column[i].SetPlace( j, &(place[i][j]) );

row[j].SetPlace( i, &(place[i][j]) );

for( bx=0 ; bx<3 ; bx++ ) } for( by=0 ; by<3 ; by++ )

for( i=0 ; i<3 ; i++ )

for( j=0 ; j<3 ; j++ )

box[bx][by].SetPlace( j*3+i,

&(place[bx3+i][by3+j]) );

}

列と行の

グループを設定グループとマスの関係を設定する

ボックスの

グループを設定

(30)

レベル 2 の推論を組み込む

「ここ」に入りえない値を除外する

2 1

4

9 7 2 5 1 8

3 6

①ここが 5 に決まった

②このボックスでは値 5 はここに入る

③このボックスでは

値 5 はこれらのマスには入らない

ボックスについてレベル 2 の推論をするための機能が必要

グループとしてのボックスに、機能を追加する

(31)

機能を追加したクラス CBox 追加

CBoard

¹ ⁸¹

CPlace

CGroup

9 1

* 1

CBox

クラス CGroup の機能を引き継ぎ、さらに機能を追加したクラス CBox を定義する

継承一般

特殊

(32)

クラスの定義 : CBox

class CBox : public CGroup { public:

CBox();

virtual ~CBox();

public:

void ExcludeColumn( int i, int v );

void ExcludeRow( int j, int v );

int OnlyColumn( int v );

int OnlyRow( int v );

};

レベル 2 の推論用に追加するメソッド

クラス CGroup を継承するクラス CBox を定義

継承を表す部分

CGroup の SetPlace, L1Infer なども利用可

(33)

クラスの定義を修正

class CBoard { public:

CBoard();

virtual ~ CBoard();

void Initialize( void );

void L1Infer( void );

void L2Infer( void );

/*

その他のメソッド

(

省略

) */

private:

CPlace place[9][9];

CGroup column[9];

CGroup row[9];

CBox box[3][3];

}; ボックスをクラス CBox に変更レベル 2 推論の

メソッドを追加

(34)

クラス CBoard の関数 Initialize

void CBoard::Initialize() { int i,j,bx,by;

for( i=0 ; i<9 ; i++ )

for( j=0 ; j<9 ; j++ ){

column[i].SetPlace( j, &(place[i][j]) );

row[j].SetPlace( i, &(place[i][j]) );

for( bx=0 ; bx<3 ; bx++ ) } for( by=0 ; by<3 ; by++ )

for( i=0 ; i<3 ; i++ )

for( j=0 ; j<3 ; j++ )

box[bx][by].SetPlace( j*3+i,

&(place[bx3+i][by3+j]) );

}

列と行の

グループを設定

ボックスの

グループを設定 box には

関数 SetPlace があり、利用可能

全く変更不要

(35)

クラス CBoard の関数 L2Infer

void CBoard::L2Infer( void ) { int bx, by, bx0, by0;

int i, j, v;

for( v=1 ; v<=9 ; v++ ){

/*

行方向の推論

*/

for( by=0 ; by<3 ; by++ )

for( bx=0 ; bx<3 ; bx++ ){

i = box[bx][by].OnlyRow( v );

if( i >= 0 )

for( bx0=0 ; bx0<3 ; bx0++ ){

if( bx0 == bx ) continue;

box[bx0][by].ExcludeRow( i, v );

} }

/*

列方向の推論

*/

} }

レベル 2 の推論

( 省略 )

CBox のメソッドを利用

ボックス

(bx,by)

では値

v

は

i

行のみ可能他のボックスでは

i

行に値

v

は入らない

(36)

まとめ 1

オブジェクト指向を紹介

プログラム開発の際に、モデリング ( 要求分析、

プログラム構成設計 ) を行うための手法

モデリングを行うことで、バグを少なくし、

プログラム開発効率を向上する

要求とプログラムの動作条件の洗い出し

( 異常入力が与えられたときの振る舞いなど )

プログラム全体の構成を概観することで、

無駄な部分、無理のある部分を特定し、改善

する

(37)

まとめ 2

オブジェクト指向プログラミング言語 (C++) を利用することで、モデルからプログラムへの移行が容易になる

C 言語に比べて C++ 言語は便利な機能があるが、本来はオブジェクト指向の考え方と合わせて初めて真価を発揮する

だからといってしり込みすることなく、便利なと

ころはドシドシ利用すればいい

(38)

プログラミング言語 I のまとめ

プログラミングによって、今まで世界中のどこにもないものを作り出すことが可能

プログラミングには、創造性、緻密さ、想像力、知識が要求される

「習うより慣れろ」とにかくプログラムを作ってみるのが習得の条件

プログラムが複雑になると予想したら、いきなりプログラムを書かずに、まずは分析と設計 ( 場合によってはオブジェクト指向を導入 )

今は C 言語 (C++ 言語 ) を習得するのがベ

スト

四則演算を正しく扱う電卓が欲しい。

プログラミング言語 I 第 14 回 オブジェクト指向

要求

四則演算を正しく扱う電卓が欲しい。

100 円ショップで売っている電卓

でも本当は 7 でなければならない

1 + 2 × 3 = 9 になる

1 + 2 × 3 = 7 になる電卓が欲しい

問題の分析

間違いの原因は、加算と乗算の優先順位を 考慮していないこと

1 + 2 × 3

複数の演算子を比較し、優先順位に したがって演算を実行する

過去に入力した演算子を記憶する必要あり

スタックを利用

スタック = 本を積み重ねたもの

後入れ、先出しのデータ管理方式

Last-In, First-Out (LIFO)

スタックを用いた演算実行

計算例

数値のスタックを用意

1 + 2 × 3

1

数値スタック

直前演算子 ( なし ) +

+

1 +

2

入力

1 1 2

+

×

+

×

3

×

2 3

=

1 7

+

6

=

1 1 2

答え

スタックの実現

配列によってスタックを表す

データを積む位置、取り出す位置

・・・ 常にスタックの頂上

スタックの頂上を表す変数 = スタックポインタ int stack[100];

int sp=99;

例 スタック本体

スタックポインタ

スタックは上位 ( 大きな添え字 ) から

下位 ( 小さな添え字 ) に向かってデータを積む

大域変数として用意

スタックの操作

データをスタックに積む push 操作

スタックからデータを取り出す pop 操作

void push( int v ) { stack[sp -- ] = v;

}

int pop( void )

{ return stack[++sp];

}

sp 位置にデータを 入れて、 sp を減少

sp を増加し、

sp 位置の

データを読出し

電卓プログラム例 1

int type, value;

char op, op1=' ', op2 =' ';

while( 1 ){

InputData( &type, &op, &value );

if( type == VALUE ) push( value );

else if( type == OPERATOR ){

if( op2 != ' ' ){ execute( op2 ); op2 = ' '; } if( op1 == ' ' ) op1 = op;

else if( op1 == '*' || op1 == '/' ){

execute( op1 ); op1 = op;

}else{ /* (op1 == '+' || op1 == ' - ') */

if( op == '*' || op == '/' ) op2 = op;

else{ execute( op1 ); op1 = op; } }else{ } /* type == EQUAL */

if( op2 != ' ' ){ execute( op2 ); op2 = ' '; } if( op1 != ' ' ){ execute( op1 ); op1 = ' '; } } }

プログラミング言語 I 第 14 回オブジェクト指向

間違いの原因は、加算と乗算の優先順位を考慮していないこと

複数の演算子を比較し、優先順位にしたがって演算を実行する

・・・常にスタックの頂上

例スタック本体

データをスタックに積む　　　 push 操作

スタックからデータを取り出す　　　 pop 操作

sp 位置にデータを入れて、 sp を減少

case '': n1 = n1n2; break;

⇒ op1, op2 の 2 つの変数によって優先順位　　を実現可能

演算子スタックが空でないスタック上演算の

演算 op1 の優先順位が演算 op 以上なので

あくまでも関数 ( 手続き ) が主体であることに原因がある