カッコの数を出力する

Question

括弧ばかりからなる記号列が正しい形になっているかどうかを調べたい。括弧には、小括弧 ( )、中括弧 { }、大括弧 [ ] がある。それぞれの括弧は、その開き記号と閉じ記号とが対応していなければならない。正確にいうと、括弧ばかりからなる記号列が与えられとき、つぎの操作を可能な限り繰り返すことでその記号列が空となるならば、その記号列は正しいという。
( と ) がこの順に隣り合って並んでいるなら、共に取り除く。
{ と } がこの順に隣り合って並んでいるなら、共に取り除く。
[ と ] がこの順に隣り合って並んでいるなら、共に取り除く。
入力に与えられた括弧ばかりからなる記号列が正しいなら correct と１行に出力し、正しくなければ wrong と１行に出力するプログラムを作れ。
なお出力の末尾には改行を書き出すこと。

入力例１
({()[]}[{()()((()))}])({}[])
出力例１
correct

が問題です。
以前行ったコメントの数を出力するプログラムを参考にしてやってみたのですがコンパイルすらうまくいきません。どうしたらよいですか。教えていただきたいです。コードは以下です。2個目のコードが以前行ったコメント出力のものです。長くなってしまいすみません。

コード#include <stdio.h>

typedef enum{
    OUT,     /*外*/
    BRAC1,   /*(*/
    BRAC2,   /*)*/
    BRAC3,   /*{*/
    BRAC4,   /*}*/
    BRAC5,   /*[*/
    BRAC6,   /*]*/
}state_t;

int main(void){
    state_t state=OUT;
    int ch;
    while((ch=getchar())!=EOF){
        switch(state){
            case OUT:
            if(ch=='('){
                state=BRAC1;
                break;
                case BRAC1:
                if(ch==')'){
                    state=BRAC2;
                }else{
                    break;
                }
            }else if(ch=='{'){
                state=BRAC3;
                break;
                case BRAC3:
                if(ch=='}'){
                    state=BRAC4;
                }else{
                    break;
                }
            }else if(ch=='['){
                state=BRAC5;
                break;
                case BRAC3:
                if(ch==']'){
                    state=BRAC6;
                }else{
                    break;
                }
            }
        }
    }
    printf("true");
    return 0;
}


#include <stdio.h>

typedef enum {
  OUT,   /* コメントの外        */
  SLASH, /* コメントはじめの'/' */
  IN,    /* コメントの中        */
  STAR,  /* コメントおわりの'*' */
} state_t;

int main(void) {
  int count = 0;
  state_t state = OUT;
  int ch;
  while ( (ch = getchar()) != EOF ) {
    switch ( state ) {
    case OUT:
      if ( ch == '/' ) state = SLASH;
      break;
    case SLASH:
      if ( ch == '*' ) state = IN;
      else 
      if ( ch != '/' ) state = OUT;
      break;
    case IN:
      if ( ch == '*' ) state = STAR;
      break;
    case STAR:
      if ( ch == '/' ){state = OUT;
      count++;
      }else 
      if ( ch != '*' )state = IN;
      break;
    }
  }
  printf("%d\n", count);  /* 結果の出力 */
  return 0;
}

Comments

[cateye]

「コメントを取り除く処理」と「カッコを数える」処理をパイプで繋げばいいのでは？

[YuhiKUROIWA]

ありがとうございます。参考にさせていただきます。

Answer 1

元の文字列を壊さないので、文字列リテラルでも大丈夫なコード。

#include <stdio.h>   // puts
#include <string.h>  // strchr

const char *s, *pa = "([{", *ren = ")]}";

int parse(void)
{
	int c; char *p;
	while ((c = *s++) && (p = strchr(pa, c)))
		if (parse() != ren[p - pa]) return 1;
	return c;
}

int main(void)
{
	s = "({()[][]([{}[]])}[{()()((()))}])({}[])";
	puts(parse() ? "wrong" : "correct");
}

Comments

[YuhiKUROIWA]

ありがとうございます。参考にさせていただきます。

Answer 2

スタックを使う方法

文字列を先頭から見て

• 左括弧(,{,[が来たらスタックに積む
• 右括弧が来たら、スタックの先頭と比較して、ペアにできるなら取り出す、ペアにならないなら失敗
• スタックが最後空になったら成功

C++で実装したけど質問はCだった……Cでスタックが出来んこともないけど……参考まで

#include <bits/stdc++.h>
using namespace std;

int main(){
  string L = "({[";
  string S = "({()[][]([{}[]])}[{()()((()))}])({}[])";
  stack<char> st;
  bool flag = true;
  for(int i=0; i<S.size(); i++){
    if(S[i]==L[0] || S[i]==L[1] || S[i]==L[2])st.push(S[i]);
    if(st.size()==0){flag=false;break;}
    char t = st.top();
    switch(S[i]){
      case ')':if(t==L[0])st.pop(); else flag=false; break;
      case '}':if(t==L[1])st.pop(); else flag=false; break;
      case ']':if(t==L[2])st.pop(); else flag=false; break;
    }
    if(!flag)break;
  }
  if(!flag || st.size()>0)cout<<"wrong\n";
  else cout<<"correct\n";
}

Comments

[kazuma-s]

string S = ")"; の場合、wrong になってほしいのに、そうなりません。

[ohys]

コーナーケースの管理が雑でしたね

[kazuma-s]

st.top() の前に st.size() をチェックしないといけないのでは？

[ohys]

コピペミスった…

Answer 3

fanaさんのを実装してみた:

#define  _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <stdio.h>
#include <stdbool.h>

int main() {
  char kakko[] = "({()[][]([{}[]])}[{()()((()))}])({}[])";
  char* pos;
  bool removed;
  do {
    removed = false;
    pos = strstr(kakko, "()"); if ( pos ) { strcpy(pos, pos + 2); removed = true; }
    pos = strstr(kakko, "{}"); if ( pos ) { strcpy(pos, pos + 2); removed = true; }
    pos = strstr(kakko, "[]"); if ( pos ) { strcpy(pos, pos + 2); removed = true; }
    puts(kakko);
  } while ( removed );
  if ( strlen(kakko) ==0 ) {
    puts("全部消えたからcorrect");
  }
}

Comments

[YuhiKUROIWA]

ありがとうございます。参考にさせていただきます。

Answer 4

隣り合って並んでいるなら、共に取り除く

というルールしか存在しないようなので，謎のステート管理チックな処理は不要でしょう．
単に
「｛"()", "{}", "[]"｝のいずれかを見つけたら除去する」という処理を
できなくなるまでやり続けるだけで済む話に思えます．
（できなくなった時点の内容次第で結果を判断すればよい）

---

まぁ，やり方は上記以外にも有り得るでしょうけども，
現在のコードを活かした方向での話を行うならば，
まずはご自身の考えているやり方（アルゴリズム）の説明が必要であろうと思います．

Comments

[fana]

まぁ，提示コードから，「入力文字列全体を保持することを避けたいのかな？」とか "推測" はできるのですが．

[YuhiKUROIWA]

ありがとうございます。参考にさせていただきます。