文字列についての問題

Question

"Bangkok"    -->  "b:*,a:*,n:*,g:*,k:**,o:*"
"Las Vegas"  -->  "l:*,a:**,s:**,v:*,e:*,g:*"

上記の例は、文字列を受け取り、それぞれの文字の出現数を*の数で表しています。このような文字列を戻り値として返す関数を作成する問題をcodewars(https://www.codewars.com/kata/5b358a1e228d316283001892/train/c)というサイト内で解いています。

自分で作成した関数をテストしてみると
("Chicago") の場合は、
"c:**,h:,i:,a:,g:,o:",となるべきところが "C:h:i:c:a:g:o:"のようになってしまいます。
コードを示しますので、どこがおかしいのか教えていただけますか。また、コード内でstring++ = と何度か書いてあるのですが、いまいちこの*(変数名)++の意味が分かっていないので、こちらのほうも教えていただきたいです。特に、一番最初の*string++はstring[0]と同じことなのでしょうか？

#include <string.h>
#include <stdlib.h> //malloc

char* get_strings(const char *city)
{
  int i, j, n;
  n = strlen(city);
  char *string;
  string = malloc( n * 4 + 1);
   char *base = string;
  
  for(i = 0; i < n; i++ )
  {
    
    int count = 0;
    int count2 = 0;
    
    for(j = 0; j < n; j++)
    {
      if(city[i] == city[j])count++;
      
    } 
     
    *string++ = city[i];
    *string++ = ':';
    
    if(i > 0)
    {
      for(int b = i - 1; b == 0; b--)
      {
        if(city[i] == city[b])count2++;
      }
    }
    
    
    if(count2 != 0)
    {
      
    
      for(int a = 1; a == count; a++)
      {
        *string++ ='*';
      }
    
      if(i != (n -1))
      {
        *string++ = ',';
      }
      else if(i == (n - 1))
      {
        *string++ = '\0';
      }
    
    
      
      
    }
  
  
  
  
  }
  
  return base;
}

回答いただいたものを参考にして、少し修正してみました。

#include <string.h>
#include <stdlib.h> //malloc
#include <ctype.h>  // tolower

char* get_strings(const char *city)
{
  int i, j, n;
  n = strlen(city);
  char *string;
  string = malloc( n * 4 + 1);
   char *base = string;
  
  for(i = 0; i < n; i++ )
  {
    int c = tolower((unsigned char)city[i]);
    if (!isalpha(c)) continue;
    
    int count = 0;
    int count2 = 0;
    
    for(j = 0; j < n; j++)
    {
      if(tolower(city[i]) == tolower(city[j]))count++;
      
    } 
    
    
    if(i > 0)
    {
      for(int b = i - 1; b >= 0; b--)
      {
        if(tolower(city[i]) == tolower(city[b]))count2++;
      }
    }
      if(count2 != 0)continue;
     
    *string++ = tolower(city[i]);
    *string++ = ':';
    
       
      for(int a = 1; a <= count; a++)
      {
        *string++ ='*';
      }
    
      if(i != (n -1))     //この部分が問題？
      {
        *string++ = ',';
      }
      else
      {
        *string = '\0';
      }
          
  
  }
  
  return base;
}

文字列によって成功するようになりましたが、まだ問題があるようです。
メッセージは

string_literal("Bangkok") should return "b:*,a:*,n:*,g:*,k:**,o:*", actual: "b:*,a:*,n:*,g:*,k:**,o:*,\""

string_literal("Dhaka") should return "d:*,h:*,a:**,k:*", actual: "d:*,h:*,a:**,k:*,"

Answer 1

("Chicago") の場合は、

"c:**,h:,i:,a:,g:,o:*",となるべきところが "C:h:i:c:a:g:o:"のようになってしまいます。
コードを示しますので、どこがおかしいのか教えていただけますか。

大文字を小文字に変換していないので C が大文字のままです。

if (count2 != 0) { だと、今の文字より前に同じ文字があったということだから、
今の文字が最初に出てきたのに '*' を string に追加しません。

さらに

      for(int a = 1; a == count; a++)
      {
        *string++ ='*';
      }

これだと count が 1 の時だけ '' が 1個追加され、
count が 1 でない時は '' は追加されません。

私なら次のように書きます。

#include <string.h> // strlen
#include <stdlib.h> // malloc, free
#include <ctype.h>  // tolower
#include <stdio.h>  // puts

char *get_strings(const char *city)
{
	int n = strlen(city);
	char *string = malloc(n * 4), *base = string;

	for (int i = 0; i < n; i++) {
		int c = tolower((unsigned char)city[i]);
		if (!isalpha(c)) continue;
		int j = i;
		while (--j >= 0 && c != tolower((unsigned char)city[j])) ;
		if (j >= 0) continue;
		if (string > base) *string++ = ',';
		*string++ = c;
		*string++ = ':';
		for (j = i; j < n; j++)
			if (c == tolower((unsigned char)city[j]))
				*string++ = '*';
	}
	*string = '\0';
	return base;
}

int main(void)
{
	char *p;
	p = get_strings("Chicago"); puts(p); free(p);
	p = get_strings("bangkok"); puts(p); free(p);
	p = get_strings("Las Vegas"); puts(p); free(p);
}

Answer 2

*string++ は、演算子の優先度の関係で、*(string++)こうなります。
まず最初に、string++ が解決されます。
char *string;とstringはポインタ型なので、これはポインタ演算になります。
ポインタ変数に対して、++すると、ポインタ変数の型に応じたサイズだけ、ポインタが進みます。
charは1Byteなので、string++とすると、stringが保持しているポインタ(アドレス)が
1Byte分進んだ値に更新されます。

しかし、string++と、後置インクリメントなので、stringの値は1つ進みますが、
string++という式自体の値は、進む前の元のstringの値になります。
式の値としてだけ見れば、string++は、stringと同じになります。

その次に、*の部分が解決されます。
*はポインタ変数に対して、それが保持しているアドレスに書かれているデータへアクセスする、
間接参照演算子です。

先に書いたように、*string++のうち、string++の部分は、stringと等価ですので、
*stringと書いたのと同じになります。普通のポインタの先へのアクセスです。

*string = 'A' とすると、それに対する代入なので、ポインタ示すアドレスに、'A'が書き込まれます。
それに加えて、
*string++ = 'A' の場合は、stringの値が加算されますので、ポインタのアドレスは先に進みます。

つまり、ポインタの指すアドレスに、データを書き込み、さらに、ポインタを次に進めるという内容となります。

内容としては、
*string = 'A';に続いてstring++;をしたのと同じになります。

---

全体の流れが判りやすいようにコメントを付けます。

#include <string.h>
#include <stdlib.h> //malloc

char* get_strings(const char *city)
{
  int i, j, n;
  n = strlen(city);
  char *string;
  string = malloc( n * 4 + 1);
   char *base = string;

  for(i = 0; i < n; i++ )    //元の文字列から一つずつ文字をとる
  {

    int count = 0;
    int count2 = 0;

    for(j = 0; j < n; j++)   //元の文字列の中に同じ文字があるかカウント
    {
      if(city[i] == city[j])count++;   //自分があるので最低1以上
    } 

    *string++ = city[i];     //全ての文字を無条件で提示用に登録
    *string++ = ':';

    if(i > 0)                //iが1以上なら=1文字目だけを除いて以下を処理
    {
      for(int b = i - 1; b == 0; b--)    //今の文字より前の文字を調べる
      {
        if(city[i] == city[b])count2++;  //同じ文字があればカウント
      }
    }


    if(count2 != 0)                    //自分より前に同じ文字があれば
    {
      for(int a = 1; a == count; a++)  //カウントした数だけ
      {
        *string++ ='*';                //*を付ける
      }

      if(i != (n -1))                  //最後の文字以外なら
      {
        *string++ = ',';               //,を付ける
      }
      else if(i == (n - 1))　　　　　　 //最後の文字以外ではなく最後の文字なら(if不要)
      {
        *string++ = '\0';              //末端文字を付ける
      }
    }
  }
  return base;
}

まずは、大文字と小文字を区別しないという処理がありません。
次に、表示用文字列に対して、文字を登録する時に、問答無用で登録してしまっているので、
C:h:i:c:a:g:o:の様に、二つ目のcが登場してしまっています。
2つ以上ある文字の2度目の登場はスルーする必要があります。

*が出ないのは、*を出すかを決める条件が、「自分よりも前に同じ文字が1つ以上あれば」となっています。
Chicagoの文字列の中で、大文字小文字を区別した場合、「自分よりも前に同じ文字が1つ以上」あるものは存在しないので、*が表示されません。
「自分よりも前に同じ文字が1つ以上あれば、その数の*を表示する」ではなく、
「文字列の中に自分と同じ文字があった数の*を表示する」とする必要があります。
(自分自身を含むので必ず1以上の*は付きます)

Comments

[Merrifield]

回答ありがとうございます。参考にしてコードを直しました。与えられた文字列によって、成功したり失敗したりするようになりました。
string_literal("Ahmedabad") should return "a:***,h:*,m:*,e:*,d:**,b:*", actual: "a:***,h:*,m:*,e:*,d:**,b:*,"
このようなエラーが出るのですが、これは最後に,がついているということになるのでしょうか？コードの最後のほうの,や終端文字の処理に問題あるのでしょうか？

[amiya]

文字列の最後の文字は、d です。しかし、d は既に出ているので、実際には出力文字には登録されません。
一方、実際に最後に出力する文字である b を出した時には、文字列にはまだ残りがあるから、
続きがあるだろう、として、, を付けています。
という感じに、元の文字列の最後の文字かどうかと、出力文字の最後の文字かは一致しません。
なので、「最後の文字なら～」という条件判断は使えません。
ある文字を登録する段階でその文字が最後かどうかはわからないので、
発想を変えて、2文字目以降を登録する時に、, を付けてから後に続けるか、
もしくは、全部終わった最後に、ヌル文字で上書きすることで、最後の , を削ってしまうという方が楽かもしれません。

[hana_yama_san]

あのですね、コードを直すのは良いのですが、
修正前と修正後の比較が出来るように
記述していただけると有難いです。

後から来て、見た人には極めて分かり辛いです。

[Merrifield]

>>amiyaさん

最後の部分をヌル文字で上書きすることで上手く出来ました。ありがとうございました。