括弧の整合性を調べるプログラム

Question

前提・実現したいこと

[]を入力させ、右括弧路左括弧の個数が等しいことを連結リストのスタックを用いて確認するプログラムを書いています。
左右の括弧が釣り合っているときは対応する括弧に数字を付けます。
例えば、[[][[]]]であれば、[1 [2 ]2 [3 [4 ]4 ]3 ]1と出力します。

以下にそのプログラムを示します。

#include<stdio.h>
#include<stdlib.h>

#define N 100

typedef char DATA;

typedef struct stack{
  DATA n;
  struct stack *next;
} STACK;

typedef struct stack2{
  int n;
  struct stack *next;
} STACK2;

STACK *head1 = NULL;
STACK2 *head2 = NULL;

int c = 0;

void push(DATA x);
DATA pop(void);
int empty(void);

void push2(int x);
int pop2(void);

int main(void){

  char str[N];
  int i = 0, m = 1;

  printf("[]の文字列を入力してください。(%d文字以下)\n", N - 1);

  do{

    scanf("%s", str);

    while(str[i] != '\0'){

      if(!(str[i] == '[' || str[i] ==']')){

        printf("[]以外の文字を入力しないでください。\n");
        i = 0;
        break;
      }
      i++;
    }
  }while(str[i] != '\0');

  i = 0;

  while(str[i] != '\0'){

    if(str[i++] == '[') push('[');
    else pop();
  }

  if(!(empty())){

    printf("[]がつりあっていません。\n");
    exit(1);
  }

  i = 0;

  while(str[i] != '\0'){

    putchar(str[i]);

    if(str[i++] == '['){

      printf("%d ", m++);
      push2(m);
    }
    else printf("%d ", pop2());

  puts("");

  return 0;
}

void push(DATA x){                     /*スタックにデータを乗せる*/

  STACK *a;
  if((a = malloc(sizeof(STACK))) == NULL){

    printf("メモリが足りません。\n");
    exit(1);
  }

  c++;
  a->n = x;
  a->next = head1;
  head1 = a;
}

DATA pop(void){                           /*スタックからデータを取り出す*/

  DATA b;
  STACK *a;

  if(empty()){

    printf("スタックが空です。\n");
    exit(1);
  }

  c--;
  a = head1;
  b = head1->n;
  head1 = head1->next;
  free(a);

  return b;
}

int empty(void){                       /*スタックが空かどうか確認*/

  return (head1 == NULL);
}

void push2(int x){                     /*スタックにデータを乗せる*/

  STACK2 *a;
  if((a = malloc(sizeof(STACK2))) == NULL){

    printf("メモリが足りません。\n");
    exit(1);
  }

  c++;
  a->n = x;
  a->next = head2;
  head2 = a;
}

int pop2(void){                           /*スタックからデータを取り出す*/

  int b;
  STACK2 *a;

  if(empty()){

    printf("スタックが空です。\n");
    exit(1);
  }

  c--;
  a = head2;
  b = head2->n;
  head1 = head2->next;
  free(a);

  return b;
}

発生している問題・エラーメッセージ

コンパイルすると、以下のようなコンパイルエラーが出て上手くいきません。

$ gcc -Wall -pedantic -o algorithm_F_brackets.out algorithm_F_brackets.c
algorithm_F_brackets.c: 関数 ‘main’ 内:
algorithm_F_brackets.c:85:1: 警告: ISO C は入れ子になった関数を禁止しています [-Wpedantic]
 void push(DATA x){                     /*スタックにデータを乗せる*/
 ^
algorithm_F_brackets.c:85:1: 警告: ISO C90 は宣言とコードの混合を禁止しています [-Wpedantic]
algorithm_F_brackets.c:100:1: 警告: ISO C は入れ子になった関数を禁止しています [-Wpedantic]
 DATA pop(void){                           /*スタックからデータを取り出す*/
 ^
algorithm_F_brackets.c:120:1: 警告: ISO C は入れ子になった関数を禁止しています [-Wpedantic]
 int empty(void){                       /*スタックが空かどうか確認*/
 ^
algorithm_F_brackets.c:125:1: 警告: ISO C は入れ子になった関数を禁止しています [-Wpedantic]
 void push2(int x){                     /*スタックにデータを乗せる*/
 ^
algorithm_F_brackets.c: 関数 ‘push2’ 内:
algorithm_F_brackets.c:136:11: 警告: 互換性のないポインタ型からの代入です
   a->next = head2;
           ^
algorithm_F_brackets.c: 関数 ‘main’ 内:
algorithm_F_brackets.c:140:1: 警告: ISO C は入れ子になった関数を禁止しています [-Wpedantic]
 int pop2(void){                           /*スタックからデータを取り出す*/
 ^
algorithm_F_brackets.c:158:1: エラー: expected declaration or statement at end of input
 }
 ^
algorithm_F_brackets.c:158:1: 警告: 制御が非 void 関数の終りに到達しました [-Wreturn-type]
 }
 ^

細かい部分で言えば間違っている部分はいくつもあると思いますが、

Comments

[Zuishin]

スタック不要でしょう。カウンター一つでできるはずです。

[aiueo12345]

カウンタcは必要ないことがわかりました。ですが、カウンタ一つでできるというのがイマイチわかりません。また、今回はスタックでできそうなのでスタックで最後までやりたいと思っています。コメントありがとうございました。

[aiueo12345]

すみません。今更ですが、カウンタで実現できるという意味が分かりました。ただ、整合時の括弧と数字の出力は難しいように思います。

[Zuishin]

簡単だと思います。[ でカウンタを増やしてそれを出力し、] で減らしてそれを出力するだけです。

[aiueo12345]

以下のようにスタックを用いないプログラムを作ってみました。質問の中で示した例『[[][[]]]』を入力した結果は[1 [2 ]2 [2 [3 ]3 ]2 ]1となりました。[[[[]]]]のような場合であれば上手くいったのですが、括弧が途中で一つでも閉じてしまうとカウンタが後戻りしてしまいます。改善すればできますでしょうか。

#include<stdio.h>
#include<stdlib.h>

#define N 100

int main(void){

char str[N];
int i = 0, c = 0;

printf("[]の文字列を入力してください。(%d文字以下)\n", N - 1);

do{

scanf("%s", str);

while(str[i] != '\0'){

if(!(str[i] == '[' || str[i] ==']')){

printf("[]以外の文字を入力しないでください。\n");
i = 0;
break;
}
i++;
}
}while(str[i] != '\0');

i = 0;

while(str[i] != '\0'){

if(str[i++] == '[') c++;
else c--;
}

if(c != 0){

printf("[]がつりあっていません。\n");
exit(1);
}

i = 0;
c = 0;

while(str[i] != '\0'){

putchar(str[i]);

if(str[i++] == '['){

printf("%d ", ++c);
}
else printf("%d ", c--);
}

puts("");

return 0;
}

[Zuishin]

質問の例が間違っていると思っていたので仕様を読み違えていました。それならスタックが必要ですね。

Answer 1

[]の整合性の前にまずは{}の整合性を確かめましょう。
main関数内で}が足りないところがあります。

Comments

[aiueo12345]

{が確かに抜けていたので修正し、他にも間違っている部分を見つけたので修正すると、実行結果は間違ていましたがコンパイルは通りました。
ここからもう一度考えてみたいと思います。
ありがとうございました。

[dice142]

解決できたようで何よりです。
（「}」ではなく「{」が抜けていたのはおかしい気もしますが。）

Answer 2

まずエラーを解消しましょう。エラーは最初のから、コンパイル・エラーは辻褄が合わなくなった所ででますから、エラーの場所から遡って確認しましょう。エラーメッセージの読み方と対処, 検索や質問の原則
で、各々のカッコ「'[' ']' '{' '}' '(' ')'」 に対してカウンタを持てばいいのじゃないですか？
'['で+1　']'で-1とか・・・

Comments

[aiueo12345]

ご回答ありがとうございます。

今回対象としているのは[]のみなのでcateyeさんの回答でいうとカウンタを一つ持つことで実現できるということになりますね。

（今プログラム中にあるカウンタcは不必要ということに気づきましたのでこれは考えないでください。）

考えてみたのですが、整合性については確かにカウンタでできますね。
ただ、整合している場合の括弧と数字の出力は難しいのではないでしょうか？