プログラミング論 II 電卓，逆ポーランド記法電卓 http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2010/

電卓

文字列の長さを調べるプログラム void main(){ int i=0; char txt[100]="hello"; while( txt[i]!='\0' ){ i++; } printf("%sの長さは%d\です\n",txt,i);

文字列を数字に変換(自作) char txt[10] = "123"; int i, n=0; for(i=0; i<10; i++){ if(txt[i] != '\0' ){ n = n*10 + txt[i]-'0'; } else { break; } printf("%d\n", n);

文字列を数字に変換(自作) 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.

文字列を数字に変換(自作) txt[]="123456"として，前から読んでいく． "1234"まで既に読んでおり，次に'5'を読むと… 1234 → 12345 1234*10 + 5 という処理を行う．

超単純な電卓プログラム "1+2" を読み込んだら，"3"を出力． 式を読み込み，計算結果を表示するプログラム． 式の中には，演算子が1個だけだとする． 登場する数字は，1桁の自然数のみとする． つまり，文字は3個あり， 順に，「数字」，「演算子」，「数字」が格納されている．

超単純な電卓プログラム 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); :

超単純な電卓プログラム 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); :

超単純な電卓プログラム 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); :

超単純な電卓プログラム 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);

実行結果 0文字目は，文字コード 55 の [7] という文字です． 数字に変換すると 7 です． 1文字目は，文字コード 42 の void main(){ char txt[10] = "7*4"; char a, b, o; int x, y, result; /* 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); 実行結果 0文字目は，文字コード 55 の [7] という文字です． 数字に変換すると 7 です． 1文字目は，文字コード 42 の [*] という文字です． 2文字目は，文字コード 52 の [4] という文字です． 数字に変換すると 4 です． 計算結果は 28 です

練習 0 以下の,txtを反転するには? char txt[]="Hello"; ??? printf("%s\n", txt); 実行結果 olleH

解答 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);

Stack

Stack スタック stack:積み重ね 箱を積む C D B B B B B A A A A A A 新しいものは，一番上に積み， 一番上から取る. 一番上に積む↑ 一番上に積む↑ 一番上を取る↑ 一番上に積む↑ 一番上を取る↑ C D B B B B B A A A A A A

Stack スタック データ管理手法としてのstack 感覚としては， 一番上に積み， 一番上に積んである ものが取り出せる． 3をpushする 3 メモリ 7をpushする 3 7 6をpushする 3 7 6 popする.6が取り出せる 3 7 2をpushする 3 7 2 popする.2が取り出せる 3 7

Stack スタック データ管理手法としてのstack 後入れ先出し 最後に入れたものが最初に取り出せる． LIFO (Last In First Out) PUSH:　スタックにデータを入れる操作を"PUSH"という．当然，Stackの一番上に入る． POP:　スタックからデータを取り出す操作を"POP"という．当然，Stackの一番上のデータが取り出せる． Stack Pointer: スタックの一番上がどこにあるを示す情報．Stackに何個積んであるかと似ている．

練習 1 以下の様にpush,popをしたらどうなるか？ 8をpushする 3をpushする popする. ?が取り出せる 7をpushする

解答 1 8をpushする 8 3をpushする 8 3 popする. 3が取り出せる 8 7をpushする 8 7

余談:FIFO FIFO (Fist In First Out) Queue, 待ち行列．先に入れたものが先に出てくる． 感覚としては， 先に列んだ客が 先にサービスを 受ける． 3をenqueueする. 3 7をenqueueする. 3 7 6をenqueueする. 3 7 6 denqueueする.3が取り出せる． 7 6 denqueueする.7が取り出せる． 6

オブジェクト指向言語(C++など)では， Stack機能のプログラミング グローバル変数． 本当は好ましくない． オブジェクト指向言語(C++など)では， もっと綺麗に記述できる． #define ST_SIZE 100 char data[ST_SIZE]; int stack_pointer = 0; 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]; printf("(Stackが空です．popできません．)\n"); return 0;

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

逆ポーランド記法電卓

逆ポーランド記法 数式の記述の仕方の1種． 括弧が不要．演算順序が一意に定まる． 演算対象の後に，演算子を記述する． 演算順序は，左から順にやっていけば良い． ただし，数字同士の区切りが必要になる． 演算対象の後に，演算子を記述する． 例：「3と5の和」は 通常の記法： 3 + 5 逆ポーランド記法： 3 5 + 処理系(文字列処理プログラム)の作成がとても容易．

逆ポーランド記法 1 2 + 2 * → ((1 2 +) 2 *) → ( 3 2 *) → 6 → ((1 2 +) 2 *) → ( 3 2 *) → 6 上記逆ポーランド記法を，通常の記法に直すと ((1+2) * 2) 通常記法では，1+(2*2) と (1+2)*2 は 意味が異なる． 逆ポーランド記法ではこの問題がない

逆ポーランド記法 1 2 + 3 4 + * → ((1 2 +) (3 4 +) *) → ( 3 (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 これは「左から順」でなく，分かりづらい(とも言える?)

逆ポーランド記法 1 2 + 3 4 + * → ((1 2 +) (3 4 +) *) → ( 3 (3 4 +) *) → ((1 2 +) (3 4 +) *) → ( 3 (3 4 +) *) → ( 3 7 *) → 21 左から，+ + * の順に処理をしていけば良い

逆ポーランド記法数式の計算 1 2 + 3 4 + * の場合． 左から順に処理をしていけば良い 1 2 + 3 4 + * ↓1 2 + を処理し，3に置き換える． 3 3 4 + * ↓3 4 + を処理し，7に置き換える． 3 7 * ↓3 7 * を処理し，21に置き換える． 21

通常の記法→逆ポーランド記法 (8-2)/(1+2)を逆ポーランド記法にすると… 上記はまず 8-2 が行われるので 8 2 – 次に, 1+2 が行われるので 8 2 – 1 2 + 最後の，6/3 が行われるので 8 2 – 1 2 + / ↑は，→の意味 ((8 2 -) (1 2 +) /)

逆ポーランド記法電卓の実装 以下の手順で実装可能 [1] stackを用意する． [2] 左から順に読んでいく． もし，数字だったら，stackにpush もし，演算子だったら，数字を2個popして 演算結果をpush. [2]を，式の終わりまで繰り返す．

逆ポーランド記法電卓の実装 1 2 + 3 4 + * stackを用意する． 左から順に読んでいく． 1を読んだ．数字をpush. +を読んだ.2個popし， 演算をし，結果をpush. 3を読んだ．数字をpush. 1 1 2 3 3 3

逆ポーランド記法電卓の実装 4 + * 4を読んだ．数字をpush. +を読んだ.2個popし， 演算をし，結果をpush. 最後に，stack上にある数字をpopし，終了． 答えは "21" 3 3 3 3 4 3 3 7 21 21

逆ポーランド記法電卓の実装 続きは，プログラミング演習IIで．