題目3: スタック
一般的ヒント
本題目のヒント
トークンとは？
トークン (token) とは，特定の区切り文字を含まないような文字列 (長さは1以上) をいう．コンパイラ関係では頻繁に登場する用語である．
例えば，空白文字を区切り文字とすると，
This is a sample text. 今年は 2021 年です．
という文字列からは
| This |
| is |
| a |
| sample |
| text. |
| 今年は |
| 2021 |
| 年です． |
という8つのトークンが得られる．
検討課題について
検討課題において
「後置式 → 中置式」変換のアルゴリズムを考えよ
という課題がある．
この場合のスタックには，数値だけでなく，式そのものを格納できると考えて構わない．
このとき，例えば「4 3 5 ＋ ×」という後置式の変換途中において，スタックはつぎのような状態をとりうる：
プログラムソースのひな型および実行例
実験1: 関数 push
プログラムソースのひな型
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
/* 前回の実験 1 で作成 */
void printList( struct node* head ){
/* 内容省略 */
}
/* 実験 1 で作成 */
void push( struct node* sp, int x ){
/* 内容は自分で作る */
}
/* 確保されたメモリを解放するための関数の宣言．main関数の後ろで定義 */
void freeList( struct node* head );
int main(void){
struct node* sp;
/* 先頭にダミーノードを作っておく */
sp = (struct node*) malloc(sizeof(struct node) );
sp->next = NULL;
push( sp, 16 );
push( sp, 28 );
push( sp, 100 );
printList( sp );
/* 確保されたメモリを解放する */
freeList( sp );
return 0;
}
void freeList(struct node* head)
{
struct node* p;
while (head) {
p = head->next;
free(head);
head = p;
}
}
実行例
$ ./a.out
100 28 16
実験2: 関数 pop
プログラムソースのひな型
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
/* 前回の実験 1 で作成 */
void printList( struct node* head ){
/* 内容省略 */
}
/* 実験 1 で作成 */
void push( struct node* sp, int x ){
/* 内容は自分で作る */
}
/* 実験 2 で作成 */
/* スタックが空（ダミーノードのみ）ならば 1 を
さもなくば 0 を return する */
int is_empty( struct node* sp ){
/* 内容は自分で作る */
}
/* 実験 2 で作成 */
int pop( struct node* sp ){
struct node* p;
int x;
if ( is_empty( sp ) ){
printf(" *** スタックは空です ***\n");
return -1;
}
p = sp->next;
x = p->data;
/* これ以降の部分は自分で作る */
return x;
}
int main(void){
struct node* sp;
/* 先頭にダミーノードを作っておく */
sp = (struct node*) malloc(sizeof(struct node) );
sp->next = NULL;
push( sp, 16 );
push( sp, 28 );
push( sp, 100 );
printList( sp );
while ( !is_empty( sp ) ){
printf("スタックは空でありません\n");
printf("取り出したデータ = %d\n\n", pop( sp ) );
}
printf("スタックが空になりました\n");
pop( sp );
/* 確保されたメモリを解放する */
free( sp );
return 0;
}
実行例
$ ./a.out
100 28 16
スタックは空でありません
取り出したデータ = 100
スタックは空でありません
取り出したデータ = 28
スタックは空でありません
取り出したデータ = 16
スタックが空になりました
*** スタックは空です ***
実験3: 電卓作成のための予備プログラム
プログラムソース
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
int data;
struct node* next;
};
/* 実験 1 で作成 */
void push( struct node* sp, int x ){
/* 内容は自分で作る */
}
/* 実験 2 で作成 */
/* スタックが空（ダミーノードのみ）ならば 1 を
さもなくば 0 を return する */
int is_empty( struct node* sp ){
/* 内容は自分で作る */
}
/* 実験 2 で作成 */
int pop( struct node* sp ){
/* 内容は自分で作る */
}
/* 確保されたメモリを解放するための関数の宣言．main関数の後ろで定義 */
void freeList( struct node* head );
int main(void) {
char str[256];
char* token;
int x;
struct node* sp;
int a, b;
/* 先頭にダミーノードを作っておく */
sp = (struct node*) malloc(sizeof(struct node) );
sp->next = NULL;
printf("後置式を入力してください(255文字以内; 要素は空白で区切ること) \n > ");
fgets(str,sizeof(str),stdin); /* fgets を使うと改行までをまとめて入力できる（解説）*/
token = strtok(str, " \n");
/* 以下のままでは push, pop は行っていないため，電卓としては機能しない．
実験テキストのアルゴリズムに従って以下を改良すること．*/
while ( NULL != token ){
if ( strcmp(token, "+") == 0 ){
printf("演算子 %s\n", token);
}
else if ( strcmp(token, "-") == 0 ){
printf("演算子 %s\n", token);
}
else if ( strcmp(token, "*") == 0 ){
printf("演算子 %s\n", token);
}
else if ( strcmp(token, "/") == 0 ){
printf("演算子 %s\n", token);
}
else{
x = atoi(token);
printf("数値 %d\n", x);
}
token = strtok(NULL, " \n");
}
printf("演算結果 = %d\n", pop(sp));
if (! is_empty(sp)) {
printf("スタックが空ではありません\n");
freeList( sp );
return 1;
}
/* 確保されたメモリを解放する */
freeList( sp );
return 0;
}
void freeList( struct node* head )
{
struct node* p;
while (head) {
p = head->next;
free(head);
head = p;
}
}
実行例
$ ./a.out
後置式を入力してください(255文字以内; 要素は空白で区切ること)
> 32 56 + 17 - 78 *
数値 32
数値 56
演算子 +
数値 17
演算子 -
数値 78
演算子 *