第 10 回スタック

本日の内容

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

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

10-1. スタック

先入れ後出し方式

前回は線形リストにより、先入れ先出し方式を学びました。これは大量で容量があらかじめわからないデータを保存するのに便利な方法ですが、入れたデータがそのまま出てきてしまうということでデータ処理には結び付く手法ではありません。これに対して先入れ後出し方式(First In Last Out, FILO)は最初に入れたものが最後に出るような記憶方式です。このような記憶方式をスタックと呼びます。スタックは最近入れたデータをすぐ取り出せるため、位置が近いデータ同士の関係が深いような場合にその関係を解析できます。このようなことがあてはまることはよくある状況ですので、スタックは良く使われます。ここでは例として、括弧の処理を考えましょう。

単純に丸括弧のみの場合は、左括弧で数を増やし、右括弧で数を減らし、一回も負の数にならずに最後が 0 になれば括弧が完全に閉じていると言えます。

例10-1


#include <stdio.h>
int main(){
  FILE *f;
  int c;
  int kazu=0;
  char file[]="samp1.c";
  if((f=fopen(file,"r"))!=NULL){
    while((c=getc(f))!=EOF){
      if(c=='('){
	kazu++;
      }else if(c==')'){
	kazu--;
	if(kazu<0){
	  fprintf(stderr,"閉じ括弧が多過ぎます。\n");
	  fclose(f);
	  return 1;
        }
      }
    }
    fclose(f);
    if(kazu==0){
      fprintf(stderr,"括弧は正常です。\n");
      return 0;
    }else{
      fprintf(stderr,"閉じ括弧が足りません。\n");
      return 2;
    }
  }else{
    fprintf(stderr,"ファイル %s を開けませんでした\n",file);
    return 9;
  }
}

しかし、 C 言語のプログラムなどの括弧が丸括弧だけでない場合のチェックする場合はどうでしょうか? C 言語では開き括弧、閉じ括弧の関係にあるものには次のものがあります。

丸括弧(): 計算の順序や関数を指定する
中括弧{}: プログラムのブロックを指定する
角括弧[]: 配列の添字を指定する
シングルクォーテーションマーク'': 文字を表す
ダブルクォーテーションマーク"": 文字列を表す
/* */: コメントを表す
< >: プリプロセッサ命令 #include において、システムヘッダファイルを指定する

ここでは簡単のために、(1)一文字で、(2)開き括弧と閉じ括弧が別の文字で、 (3)プリプロセッサ用ではない、(){}[]のチェックプログラムを作ってみましょう。この場合も、上のプログラム同様、閉じ括弧が来る時にチェックを行います。

開き括弧が連続していて閉じ括弧が来た場合 ({[( ): 直前の開き括弧と対応づける。
開き括弧が連続した後、閉じ括弧が二個来た場合({[( )]: 最初の閉じ括弧は直前の開き括弧へ、次の閉じ括弧はその前の開き括弧へ

この分析から予想されることは次のことです。

開き括弧は全て記憶しておかなければならない
閉じ括弧と対応させるには、一番最後の開き括弧から順番に取り出す必要がある
一度対応づけた開き括弧はそれ以降の計算では不要となる

この処理のためにスタックを使用します。まず、開き括弧はスタックに順番に格納します。これをスタックにプッシュすると言います。そして、閉じ括弧が来たら、スタックから一つデータを取り出します。この時、そのデータはスタックからデータが取り除かれます。このような操作をスタックからデータがポップされると言います。そして、ポップされた開き括弧と閉じ括弧が対応していればその括弧の対応は取れていると言えます。どこかで対応が取れなかったり、スタックが空になってしまったのにポップしようとしたら括弧の対応がとれてなかったことになります。入力が終った時、スタックが空であれば括弧の対応が取れていたことになります。

例10-2

ここではスタックをグローバル変数の配列を使って実現します。配列のサイズはあらかじめ決めておきます。したがってこのような方式ではそのサイズ以上にプッシュができない制約があります。さて、スタックを制御するのにスタックポインタを用意します。はじめはなにも指さない状態ですが、値がプッシュされると配列の 0 番目から順番にデータを入れていきます。つまり、スタックポインタを一つ増やしては値を入れると言う動作をします。一方、ポップはスタックポインタの指しているデータを返し、スタックポインタは一つ前のデータを指すようにします。このようにすると、スタックポインタが負の値かどうかを調べることにより、スタックが空かどうかが分かります。これらを実装したのが以下のプログラムです。


#include <stdio.h>
#define N 100
#define DEBUG
char stack[N];
int stackpointer=-1;
void printstack(){
  int i;
  for(i=0;i<=stackpointer;i++){
    printf("%c",stack[i]);
  }
  printf("\n");
}
void push(char c){
  stack[++stackpointer]=c;
#ifdef DEBUG
  printstack();
#endif
}
char pop(){
  char ret;
  ret=stack[stackpointer--];
#ifdef DEBUG
  printstack();
#endif
  return ret;
}
int empty(){
  return stackpointer<0;
}
main(){
  FILE *f;
  int c;
  int kazu=0;
  char file[]="samp1.c";
  if((f=fopen(file,"r"))!=NULL){
    while((c=getc(f))!=EOF){
      if((c=='(')||(c=='{')||(c=='[')){
	push(c);
      }else if(c==')'){
	if(empty()){
	  fprintf(stderr,"閉じ括弧が多過ぎます。\n");
	  fclose(f);
	  return 1;
	}else{
	  if(pop()!='('){
	    fprintf(stderr,"閉じ括弧が合ってません。\n");
	    fclose(f);
	    return 4;
	  }
	}
      }else if(c=='}'){
	if(empty()){
	  fprintf(stderr,"閉じ括弧が多過ぎます。\n");
	  fclose(f);
	  return 1;
	}else{
	  if(pop()!='{'){
	    fprintf(stderr,"閉じ括弧が合ってません。\n");
	    fclose(f);
	    return 4;
	  }
	}
      }else if(c==']'){
	if(empty()){
	  fprintf(stderr,"閉じ括弧が多過ぎます。\n");
	  fclose(f);
	  return 1;
	}else{
	  if(pop()!='['){
	    fprintf(stderr,"閉じ括弧が合ってません。\n");
	    fclose(f);
	    return 4;
	  }
	}
      }
    }
    fclose(f);
    if(empty()){
      fprintf(stderr,"括弧は正常です。\n");
      return 0;
    }else{
      fprintf(stderr,"閉じ括弧が足りません。\n");
      return 2;
    }
  }else{
    fprintf(stderr,"ファイル %s を開けませんでした\n",file);
    return 9;
  }
}

線形リストを使ったスタック

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


LIST *stackpointer=NULL;
LIST* push(char *i){
  LIST *newnode=(LIST *)malloc(sizeof(LIST));
  if(newnode!=NULL){
    newnode->item=i;
    newnode->next=stackpointer;
    stackpointer=newnode;
  }
  return 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");

演習10-1

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


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

演習10-2

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

10-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 する。

演習10-3

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

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 10 回 スタック