第 8 回スタック

本日の内容

8-1. スタック
8-2. 数式の解釈

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

8-1. スタック

動的なメモリの確保

C 言語の配列はあらかじめ容量を決めておく必要があります。しかし、それでは処理できる情報量に限りがあります。そのため、任意の長さのメモリを確保する関数 malloc が C 言語に提供されています。 malloc 関数は必要なバイト数を引数にすると、OS から確保したメモリの先頭の番地を値として返します。一方、 free 関数はメモリの番地を引数とすると、そのメモリを OS に返します。確保した領域を C 言語の変数として使うには、変数に必要なメモリのバイト数を求め、そのバイト数だけ確保し、返ってきたメモリの番地をその変数の型にキャストする必要があります。型からその型に必要なバイト数を求めるにはsizeof 演算子を使います。

malloc の使用例を次に示します。


#include <stdio.h>
#include <stdlib.h>
main(){
  int x;
  int *y;
  y=(int *)malloc(50*sizeof(int));
  for(x=0; x<50; x++){
    printf("%d ",y[x]=x);
  }
  printf("\n");
  for(x=0; x<50; x++){
    printf("%d ",*y++);
  }
  printf("\n");
  free(y);
}

線形リスト

malloc 関数を使用すれば必要なだけメモリを確保できますが、上に示したようにあらかじめ必要な容量を定める必要があるため、配列の形では連続して値を格納することができません。

そこで、線形リストという仕組みを使えば、必要なだけ連続して値を格納することができます。線形リストとは、値を格納する場所と、次の値がある番地を格納する場所を持つ構造体を並べたものです。新たに値を格納したい場合は、その構造体をメモリ上に確保して、その手前の構造体からそのメモリを参照するように調整します。


typedef struct lst {
   char *item;
   struct lst *next;
} LIST;

スタック

今回は、カッコを取り扱うことを考えます。初めにカッコの対応を識別する方法を考えましょう。

カッコの対応がとれているかどうかは状態遷移図ではチェックできないことがわかっています。そのため、今回はスタックというデータ構造を紹介します。

スタックとは、データを連続してためて取り出す仕組みで、入れたばかりのものが先に取り出され、先頭に入れたものは最後に出ます。これを先入れ後出し方式(First In Last Out FILO) と言います。ものを重ねて、上から取り出すイメージです。スタックにデータを入れるのを push と言い、スタックからデータを取り出すのを pop と言います。スタックはコンピュータの処理によく使われます。機械語にも用意されていることが多いです。またスタックが空であることを示す empty 関数も用意されていることが多いです。

スタックの容量を無制限にするには線形リストを使います。始めは空のスタックを用意します。スタックは pop で値を取り出すと、次の pop ではその前に push した要素を取り出せるようにしなければならないので、線形リストを用いて push, pop は次のように実現します。


LIST *stackpointer=NULL;
void push(char *i){
  LIST *newnode=(LIST *)malloc(sizeof(LIST));
  newnode->item=i;
  newnode->next=stackpointer;
  stackpointer=newnode;
}
char *pop(){
  LIST *d=stackpointer;
  char *i=stackpointer->item;
  stackpointer=stackpointer->next;
  free(d);
  return i;
}
int empty(){
  return stackpointer==NULL;
}

初期状態
push("a");
push("b");

演習8-1

次のプログラムでスタックをテストしなさい。


#include <stdio.h>
#include <stdlib.h>
/* 上の LIST の定義をここにコピーする */
/* 上のスタックのコードをここにコピーする */
main(){
  push("abc");
  push("def");
  printf("%s\n",pop());
  push("ghi");
  printf("%s\n",pop());
  printf("%s\n",pop());
}

演習8-2

スタックを利用してカッコの対応がとれているかどうかをチェックするプログラムを書きなさい。但し、チェックするカッコは (){} [] の三種類とします。

8-2. 数式の解釈

逆ポーランド記法

我々が一般に数式と呼んでいるのは、数と数の間に演算子が入る形のものです。ところで、この位置関係は実際には本質的でなく、二つの数をどう計算するかという意味であればどう置いても構いません。例えば、英語では「Add 1 and 2」と先頭に指定しますし、日本語では「 1 と 2 を加える」と演算は最後に指定します。どちらも 1 + 2 という同じ式を表しています。

中置記法: 1 + 2
前置記法: + 1 2
後置記法(逆ポーランド記法): 1 2 +

さて、 2 * 3 + 4 * 5 という式を考えてみましょう。カッコをつけて表すと次のようになります。

中置記法: ((2 * 3) + (4 * 5))
前置記法: (+ (* 2 3) (* 4 5))
後置記法(逆ポーランド記法): ((2 3 *) (4 5 *) +)

中置記法では足し算とかけ算の演算子の優先順位という問題がありますが、前置記法、後置記法ともそのような問題は発生しません。したがって、カッコは必要ありません。例えば、 (1+2)*3 という式は後置記法では 1 2 + 3 * となり、 1+(2*3) は 1 2 3 * + とカッコなしで区別できます。さらに、後置記法では演算子が来た時に直前の二つの値に対してその演算を行えば計算ができることになります。この「直前の二つ」という情報を扱うのにスタックを使います。後置記法での計算の概要は次の通りです。

数を読んだら、数を push する。
演算子を読んだら、数を二つ pop し、計算し、結果を push する。

演習8-3

逆ポーランド記法の数式を計算するプログラムを書きなさい。

中置記法でのカッコの取り扱い

では本来の中置記法での計算はどうやったら実現できるでしょうか? 中置記法を逆ポーランド記法に変換すればあとは上に示したスタックを使った計算で値を求めることができます。しかし、ここでは直接値を求めることを考えましょう。カッコをどうやって処理すればよいかがポイントですが、次のように考えます。

開きカッコが来たら、演算を途中で止め記憶し、新しい計算ができるように準備する
閉じカッコが来たら、カッコの中を計算して値を求める。そして、記憶しておいた演算を元に戻す。

これを前回作ったプログラムに追加するとカッコに対応することができます。ここでは、補足で作成したプログラムを参考にします。このプログラムでは計算の結果は result に入り、演算子は op に入り、読み込んだ値は num に入り、num の符号は sign に入ります。この場合に、上の処理は次のように具体化できます。

数字を読み込む代わりに開きカッコを読み込んだら、num の値を計算するのを止めて result と op をスタックに push する。新たな計算を始める意味で result=0, op=' ' とする。
数字を読み込んでいて閉じカッコを読み込んだら、そこまでの値を計算する。計算結果を num に入れ、スタックから result と op を pop する。

なお状態が一つ増えているのは閉じカッコが来た時、次に数字が来ることを許さないからです。入力される式で閉じカッコの直後に数字が来ないことがわかっていれば次のように手抜きができます。

演習8-4

補足で作成したプログラムを利用して、カッコの処理を付け足しなさい。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 8 回 スタック