プログラミング論II

プログラミング論
電卓，逆ポーランド記法電卓
http://www.ns.kogakuin.ac.jp/~ct13140/Prog/
電卓
文字列の長さを調べるプログラム
void main(){
int i=0;
char txt[100]="hello";
while( txt[i]!='\0' ){
i++;
}
printf("%sの長さは%d\です\n",txt,i);
}
P-3
文字列を数字に変換(自作)
char txt[10] =
int i, n=0;
for(i=0; i<10;
if(txt[i] !=
n = n*10 +
} else {
break;
}
}
printf("%d\n",
"123";
i++){
'\0' ){
txt[i]-'0';
n);
P-4
文字列を数字に変換(自作)
txt[10] は '1','2','3'.
最初のtxt[0]を読むと'1'. (これは49)
'1'-'0'で，int型の1が得られる．
txt[1]を読むと'2'.
1*10 + 2  12.
txt[2]を読むと'3'.
12*10 + 3  123.
P-5
文字列を数字に変換(自作)
txt[]="123456"として，前から読んでいく．
"1234"まで既に読んでおり，次に'5'を読むと…
1234 → 12345
1234*10 + 5
という処理を行う．
P-6
超単純な電卓プログラム
• "1+2" を読み込んだら，"3"を出力．
• 式を読み込み，計算結果を表示するプログラム．
– 式の中には，演算子が1個だけだとする．
– 登場する数字は，1桁の自然数のみとする．
– つまり，文字は3個あり，
順に，「数字」，「演算子」，「数字」が格納されている．
P-7
超単純な電卓プログラム
void main(){
char txt[4] = "7*4";
char a; int x;
/* 0文字目を解析する. */
a = txt[0];
printf("0文字目は，文字コード %d の\n", a);
printf("[%c] という文字です．\n", a);
x = a - '0';
printf("数字に変換すると %d です．\n", x);
:
P-8
超単純な電卓プログラム
void main(){
char txt[4] = "7*4";
char a, o; int x;
/* 0文字目を解析する. */
略
/* 1文字目を解析する. */
o = txt[1];
printf("1文字目は，文字コード %d の\n", o);
printf("[%c] という文字です．\n", o);
:
P-9
超単純な電卓プログラム
void main(){
char txt[4] = "7*4";
char a, b, o; int x, y;
略
/* 2文字目を解析する. */
b = txt[2];
printf("2文字目は，文字コード %d の\n", b);
printf("[%c] という文字です．\n", b);
y = b - '0';
printf("数字に変換すると %d です．\n", y);
:
P-10
超単純な電卓プログラム
void main(){
char txt[4]="7*4";
char a, b, o; int x, y, result;
略
if( o == '+' ){
result = x + y;
} else if( o == '-' ){
result = x - y;
} else if( o == '*' ){
result = x * y;
} else if( o == '/' ){
result = x / y;
}
printf("計算結果は %d です\n", result);
}
P-11
void main(){
char txt[10] = "7*4";
char a, b, o;
/* 0文字目を解析する. */
a = txt[0];
printf("0文字目は，文字コード %d の\n", a);
printf("[%c] という文字です．\n", a);
x = a - '0';
printf("数字に変換すると %d です．\n", x);
/* 1文字目を解析する. */
o = txt[1];
printf("1文字目は，文字コード %d の\n", o);
printf("[%c] という文字です．\n", o);
/* 2文字目を解析する. */
b = txt[2];
printf("2文字目は，文字コード %d の\n", b);
printf("[%c] という文字です．\n", b);
y = b - '0';
printf("数字に変換すると %d です．\n", y);
if( o == '+' ){
result = x + y;
} else if( o == '-' ){
result = x - y;
} else if( o == '*' ){
result = x * y;
} else if( o == '/' ){
result = x / y;
}
printf("計算結果は %d です\n", result);
}
int x, y, result;
実行結果
0文字目は，文字コード 55 の
[7] という文字です．
数字に変換すると 7 です．
1文字目は，文字コード 42 の
[*] という文字です．
2文字目は，文字コード 52 の
[4] という文字です．
数字に変換すると 4 です．
計算結果は 28 です
P-12
練習 0
以下の,txtを反転するには?
char txt[]="Hello";
???
printf("%s\n", txt);
実行結果
olleH
P-13
解答 0
void main(){
char txt[]="Hello";
int len, i;
char tmp;
len = strlen(txt);
for(i=0; i<len/2; i++){
tmp = txt[i];
txt[i] = txt[len-1-i];
txt[len-1-i] = tmp;
}
printf("%s\n", txt);
}
P-14
Stack
Stack スタック
• stack:積み重ね
• 箱を積む
新しいものは，一番上に積み，
一番上から取る.
B
C
B
B
D
B
A
一
番
上
を
取
る
↑
A
一
番
上
に
積
む
↑
A
一
番
上
を
取
る
↑
A
一
番
上
に
積
む
↑
↑
A
一
番
上
に
積
む
B
A
P-16
Stack スタック
• データ管理手法としてのstack
3をpushする
メモリ
3
7をpushする
3
感覚としては，
一番上に積み，
一番上に積んである
ものが取り出せる．
7
6をpushする
3
7
3
7
6
popする.6が取り出せる
2をpushする
3
7
2
popする.2が取り出せる
3
7
P-17
Stack スタック
• データ管理手法としてのstack
– 後入れ先出し
• 最後に入れたものが最初に取り出せる．
• LIFO (Last In First Out)
– PUSH: スタックにデータを入れる操作を"PUSH"と
いう．当然，Stackの一番上に入る．
– POP: スタックからデータを取り出す操作を"POP"と
いう．当然，Stackの一番上のデータが取り出せる．
– Stack Pointer: スタックの一番上がどこにある
を示す情報．Stackに何個積んであるかと似ている．
P-18
練習 1
• 以下の様にpush,popをしたらどうなるか？
8をpushする
3をpushする
popする. ?が取り出せる
7をpushする
popする. ?が取り出せる
popする. ?が取り出せる
P-19
解答 1
8をpushする
8
3をpushする
8
3
popする. 3が取り出せる
8
8
7をpushする
7
popする. 7が取り出せる
8
popする. 8が取り出せる
P-20
余談:FIFO
• FIFO (Fist In First Out)
– Queue, 待ち行列．先に入れたものが先に出てくる．
3をenqueueする.
3
3
3
7をenqueueする.
7
7
7
6
6
6
感覚としては，
先に列んだ客が
先にサービスを
受ける．
6をenqueueする.
denqueueする.3が取り出せる．
denqueueする.7が取り出せる．
P-21
Stack機能のプログラミング
#define ST_SIZE 100
char data[ST_SIZE];
int stack_pointer = 0;
グローバル変数．
本当は好ましくない．
オブジェクト指向言語(C++など)では，
もっと綺麗に記述できる．
void push(char ch){
if( stack_pointer < ST_SIZE ){
data[stack_pointer] = ch;
stack_pointer ++;
printf("(%cをpushしました．)\n", ch);
} else {
printf("(Stackがいっぱいでpushできません．)\n");
}
}
char pop(){
if( 0 < stack_pointer ){
stack_pointer --;
printf("(popして，%cが得られました．)\n", data[stack_pointer]);
return
data[stack_pointer];
} else {
printf("(Stackが空です．popできません．)\n");
return
0;
}
}
P-22
Stack機能のプログラミング
int stack_length(){
return
stack_pointer;
}
void print_stack(){
int i;
for(i=0; i<stack_pointer; i++){
printf(" (print_stack : %d個目は
}
}
%d)\n", i, data[i]);
void main(){
char ch;
push('H');
push('e');
print_stack();
push('r');
ch = pop();
printf("ch = %c\n", ch);
ch = pop();
ch = pop();
ch = pop();
}
P-23
逆ポーランド記法電卓
逆ポーランド記法
• 数式の記述の仕方の1種．
• 括弧が不要．演算順序が一意に定まる．
– 演算順序は，左から順にやっていけば良い．
– ただし，数字同士の区切りが必要になる．
• 演算対象の後に，演算子を記述する．
– 例：「3と5の和」は
通常の記法：
3 + 5
逆ポーランド記法： 3 5 +
• 処理系(文字列処理プログラム)の作成がとても
容易．
P-25
逆ポーランド記法
•1 2 + 2 *
→
((1 2 +) 2 *)
→
(
3
2 *)
→
6
• 上記逆ポーランド記法を，通常の記法に直すと
((1+2) * 2)
– 通常記法では，1+(2*2) と (1+2)*2 は
意味が異なる．
逆ポーランド記法ではこの問題がない
P-26
逆ポーランド記法
•1 2 + 3 4 + *
→
((1 2 +) (3 4 +) *)
→
(
3
(3 4 +) *)
→
(
3
7
*)
→
21
• 上記逆ポーランド記法を通常の記法に直すと
– ((1+2) * (3+4))
– 演算の順番は，(1+2)→3, (3+4)→7, 3*7→21
– これは「左から順」でなく，分かりづらい(とも言える?)
P-27
逆ポーランド記法
•1 2 +
→
→
→
→
左から，+
3 4
((1
(
(
21
+ *
+ *
2 +) (3 4 +) *)
3
(3 4 +) *)
3
7
*)
の順に処理をしていけば良い
P-28
逆ポーランド記法数式の計算
• 1 2 + 3 4 + * の場合．
左から順に処理をしていけば良い
1 2 + 3 4 + *
↓1 2 + を処理し，3に置き換える．
3 3 4 + *
↓3 4 + を処理し，7に置き換える．
3 7 *
↓3 7 * を処理し，21に置き換える．
21
P-29
通常の記法→逆ポーランド記法
(8-2)/(1+2)を逆ポーランド記法にすると…
上記はまず 8-2 が行われるので
8 2 –
次に, 1+2 が行われるので
8 2 – 1 2 +
最後の，6/3 が行われるので
8 2 – 1 2 + /
↑は，→の意味 ((8 2 -) (1 2 +) /)
P-30
逆ポーランド記法電卓の実装
• 以下の手順で実装可能
[1] stackを用意する．
[2] 左から順に読んでいく．
もし，数字だったら，stackにpush
もし，演算子だったら，数字を2個popして
演算結果をpush.
[2]を，式の終わりまで繰り返す．
P-31
逆ポーランド記法電卓の実装
•1 2 + 3 4 + *
stackを用意する．
左から順に読んでいく．
1を読んだ．数字をpush.
2を読んだ．数字をpush.
+を読んだ.2個popし，
演算をし，結果をpush.
3を読んだ．数字をpush.
1
1 2
3
3 3
P-32
逆ポーランド記法電卓の実装
•4 + *
3 3
4を読んだ．数字をpush. 3 3 4
+を読んだ.2個popし，
3
3 7
演算をし，結果をpush.
*を読んだ．2個popし，
演算をし，結果をpush. 21
最後に，stack上にある数字をpopし，終了．
21
答えは "21"
P-33
逆ポーランド記法電卓の実装
• 続きは，プログラミング演習IIで．
P-34

Download Report