プログラミングの問題、分かりますか？
C, C++, Java, Smalltalk のどれかの言語を使って、標準入力からC言語などのプログラムテキストファイルを読み込み、使用している関数名を頻度順に並べるプログラムを作りなさい。これは宣言文と実際の式のどちらも含みます。なお、同じ頻度の関数は辞書順に並べなさい。なお、取り扱える行数は実行時のコンピュータのメモリーのサイズのみに依存しなければなりません。勝手な上限を設けてはいけません。但し、関数名の長さは高々255文字と仮定して良い。
それとプログラムの解析、ソースの流れを説明していただけませんか？
よろしくお願いします。
# 掲示板への丸投げは反応が渋くなるのが普通かと思います。
> C言語などのプログラムテキストファイル
複数言語対応ですか？任意の言語でいいなら少なくとも C はお勧めしません。
もし C 言語で、その課題を文字通り・言語規格通りに実現するためには
C のプリプロセッサとパーサをほぼ完全に実装する必要があると思います。
(特に引数つきマクロを関数と区別するのはかなり面倒なはずです)
# 出題者がどこまで期待しているのかは知りませんが。
あっきーさん、いっつも丸投げですね。
http://madia.world.coocan.jp/cgi-bin/Vcbbs/wwwlng.cgi?print+200412/04120067.txt
これは同じ方？ それとも同じ学校の方でしょうか？
…と言うだけでもなんなので、ヒント。
http://www.pro.or.jp/~fuji/mybooks/cdiag/appendix.a.html
ただし、あっきーさんがもとめているものズバリではありません。
これをズバリにする方法は丸投げしないでくださいね。
> http://www.pro.or.jp/~fuji/mybooks/cdiag/appendix.a.html
> ただし、あっきーさんがもとめているものズバリではありません。
ちょっと見てきました。
当然ですが、サンプルを簡潔にするために面倒なところを仕様でざっくり切ってますね。
・「関数ブロックを探すだけで、内部処理や引数自体はほぼ解析しなくて済む要件」とか。
・「(C言語からすれば勝手な)関数ブロックの {} が常に行頭にあると仮定する仕様」とか。
# まぁ現状でも、例えばグローバル変数の初期化にキャスト/優先度変更などの ( を書くと
# 誤判定してますが、サンプルとしてはまず問題ない程度かと。
このサンプルは、仕様で実処理の大半を解析対象から外してますから精度が出てますが、
あっきーさんのという要件ではそうはいきませんから、このあたりが考えどころでしょうか。
> # 出題者がどこまで期待しているのかは知りませんが。
> (特に引数つきマクロを関数と区別するのはかなり面倒なはずです)
ここまでは期待して無いと思いますよ…
プリプロセッサは処理しないで、関数の書式をかなり限定してもいいんじゃないかなと。
> ここまでは期待して無いと思いますよ…
私にも、おそらくクライアント(出題者)が、完全な実装を求めていないであろう事は
推測できますが、作成期間も分からなければヒアリングもできませんし、
実際に「どの程度」を求められているのかについては判断できてません。
ただ、要求を出された側としては、その内容や実現可能性などもいろいろ検討して、
どこをどう制限するのか、どう対応しないのかを選択をするのも「設計」だと思ってます。
# なんでも全部言われたままにやればいいってものではないわけで...。
> プリプロセッサは処理しないで、関数の書式をかなり限定してもいいんじゃないかなと。
最終的に妥協するのは現実的にも当然として、どこで、どこまで、どう妥協するのか。
実現する機能の取捨択一はまず要求全体を把握してからの話だと思いますし、
要求に内在する問題の洗い出しは、特に対象に詳しくないと難しいと思って
主にその点について言及してるつもりでしたが、どうも言葉足らずだったようです。
サンプル先は、仕様で巧く機能制限して大分処理を削ってるし、
削った分の皺寄せも一般的にまず妥当な範囲だけど、
今回は多分それよりは制限を緩くせざるを得ないだろうから、
どうすればそれほど精度を落とさずに、現実的な範囲に処理を
落とし込めるのか、そのあたりが考えどころでは？
ということが言いたかっただけで「全部作れ〜」とかいうつもりは流石にないです。
> ただ、要求を出された側としては、その内容や実現可能性などもいろいろ検討して、
> どこをどう制限するのか、どう対応しないのかを選択をするのも「設計」だと思ってます。
> 実現する機能の取捨択一はまず要求全体を把握してからの話だと思いますし、
> 要求に内在する問題の洗い出しは、特に対象に詳しくないと難しいと思って
そこまで大げさな話じゃないんじゃないかな、ということです。
設計をしっかりやるに越したことは無いですが、設計することが課題では無いでしょうから。
多分、この方も同じ学校かな？
http://www2.realint.com/cgi-bin/tarticles.cgi?pointc+19018
Banさん、シャノンさん、ありがとうございます。
作成してほしいプログラムは、複数言語対応でなく、任意の言語でかまいません。作成したソースプログラムをプログラムに入力した出力した結果を得られれば満足します。
> http://madia.world.coocan.jp/cgi-bin/Vcbbs/wwwlng.cgi?print+200412/04120067.txt
> http://www2.realint.com/cgi-bin/tarticles.cgi?pointc+19018
この方々はおそらく同じ学校の方でしょう。出力結果は前者が書かれているように、
combination: 4
main: 1
printf: 1
と、カウントし並べ替えるものです。
私は風邪で調子が悪いため、みなさんの力を借りたいと思い、今回掲示板に載せさせていただきました。よろしくお願いします。
> そこまで大げさな話じゃないんじゃないかな、ということです。
> 設計をしっかりやるに越したことは無いですが、設計することが
> 課題では無いでしょうから。
そういうものですか？どの言語を選択するかで明らかに苦労が違いますし、
同じ労力なら完成度もかなり変わると思いますが、そこまでは見(られ)ない
ものなんでしょうか＞評価。
# ...って評価者が掲示板を確認してたらもう意味ないか。
> 作成してほしいプログラムは
# いずれにしてもこれは渋くなるどころではないので、私は一抜けします。
繰り返しですが C はお勧めしません。もっと簡単な言語を選択して
自前で根性展開するなり、構文を整理して CC を使うなりした方が
楽だと思います。参考になるか分かりませんが、がんばってください。
> 私は風邪で調子が悪いため、
# お大事に。
> 私は風邪で調子が悪いため、
風邪で調子悪くても、熱があっても、残業する人は多い。
↓
何が言いたいか。
↓
妙な甘えはしないほうがいい。（むしろ、何も書かない方が敬遠されにくい。）
# イソジンがお奨め。「含みうがい20秒＋喉うがい30秒×3回」が公式らしい。
よほどのことでない限り、かつ、よほどのお人よしで無い限り、丸投げしても答えてくれる人はいません。
会社へ行くと、風邪を引いたのは日頃の体調管理がなってないからだ、などと平気で言われますよ。
むしろ、その別の掲示板で投稿している人に連絡を取って協力して進める、という姿勢の方が健全かと思います。
＃一番いいのは、ご学友なり先生なりにヒントをもらうことです
> そういうものですか？どの言語を選択するかで明らかに苦労が違いますし、
> 同じ労力なら完成度もかなり変わると思いますが、そこまでは見(られ)ない
> ものなんでしょうか＞評価。
言語の選定くらいは必要でしょうが、その後で、実際の開発業務のように要求定義をし、仕様書を書き、作ってからテストをし…などのように本格的にやっても（もちろんいいのですが）「学生らしからぬものを作ってきた」という評価が下るだけではないかと。
箇条書きで要点をピックアップする程度で「設計」は十分だと思われます。
個人的には、多少バグがあろうと制限がきつかろうと「それっぽいもの」ができれば及第点ではないかと思ってます。
まぁ、ここでいくら聞いても、正確な仕様も手がかりの一つも出てきませんので、早々に別の方法を模索したほうが吉です。
多少なりともご自分で努力したことが示されれば、協力する気にもなりますが。
学校でもちゃんとやると評価は下がるんですか。
私は趣味から入っていて、プログラミング必修の学校ではなかったもので、
そういう学校は実務ほど結果主義ではないものかと思ってました。
どこか幻想があるようです。
> 学校でもちゃんとやると評価は下がるんですか
「さがる」ではなく「くだる」です。まぎらわしくてゴメンナサイ。
> そういう学校は実務ほど結果主義ではないものかと思ってました。
話がかみ合っていませんね。
> ただ、要求を出された側としては、その内容や実現可能性などもいろいろ検討して、
> どこをどう制限するのか、どう対応しないのかを選択をするのも「設計」だと思ってます。
> 最終的に妥協するのは現実的にも当然として、どこで、どこまで、どう妥協するのか。
> 実現する機能の取捨択一はまず要求全体を把握してからの話だと思いますし、
そんなに難しく考えるこたぁねぇダロ、と言いたいだけです。
んで、お仲間が増えたようです。
http://cgi2.html.ne.jp/~piro/bbs/wforum.cgi?mode=allread&no=4579&page=0
# [2005/01/08(土) 10:27:01]は完全に読み違えた上に勘違いしてました...orz
> そんなに難しく考えるこたぁねぇダロ、と言いたいだけです。
＞あっきーさん、(もしご覧なら同じ課題に挑戦中の方々)
変に混乱させてしまってたらごめんなさい。
Banさん、シャノンさん、ありがとうございます。
瀬戸っぷさんの紹介されたところでも、なかなか良い答えは紹介されていませんね。プロにとってもそれだけ難しいと言うことでしょうか。
私はC++でやるつもりです。C++もお勧めできないものでしょうか。
自分で作ったものを載せたいのですが、同じ学校の方に真似されても困るのであえて載せていません。努力を見せられなくて残念ですが。幾通りの方法を考えているのですが思ったとおりの出力が得られません。
取り出した関数を数えて、それを『例のように表示させる』こと。
同じ頻度の関数を『辞書順に並べる』こと。
主にこの二つがうまくいきません。
挑戦してくださる方はおられますか。よろしくおねがいします。
以降放置で。
といいつつ最終レス。
> 自分で作ったものを載せたいのですが、同じ学校の方に真似されても困るのであえて載せていません。
その姿勢は誤りです。
「女は他人に見られることで綺麗になる」とよく言いますが、女に限ったことではなく、男でも、絵でも、文章でも、プログラムでも、何でも「他人に見られること」を意識すると、見せても恥ずかしくないようなものを作ろうとして、自然と美しくなります。
逆に言えば、他人に見せないものは、綺麗か汚いかを客観的に判断できないため、なかなか綺麗になりません。
> 挑戦してくださる方はおられますか。よろしくおねがいします。
おられません。あきらめてください。
シャノンさん、いままでありがとうございました。
あまり、こういったことは書きたくないのですが、
プログラムをするにあたってなんなのか、
どういった姿勢でいたらいいのか
などを討議するために、指摘されるために掲示板に載せたわけではありません。本題に書いてあるように、分かるかどうかを皆さんに尋ねているのです。
分かるのであれば手助けをしていただけたら幸いです。
よろしくおねがいします。
# 最後レスです。
> 私はC++でやるつもりです。C++もお勧めできないものでしょうか。
開発言語は問題にしてません。開発言語の話なら得意なものでどうぞ。
解析対象言語としては、関数名の中にスペースや <> まで入ってくる
C++ は「ちゃんと解析する」なら C より確実に面倒です。
あえてお勧めはしませんが、結局は仕様を決めるときの手の抜き方
次第なので、そういう構文を分かった上でちょっと工夫すれば C と
大差ない程度にはできると思います。
> 取り出した関数を数えて、それを『例のように表示させる』こと。
> 同じ頻度の関数を『辞書順に並べる』こと。
仕様にあったデータ構造さえ決めればもう特に問題はないと思います。
> 分かるかどうかを皆さんに尋ねているのです。
では、分かります。
# 課題に対する設計部分に興味を持ったからレスをしてましたが、
# 個人的には既に挑戦とか挑むとかいう要素を感じません。
#
# 公開の掲示板は成果の共有や相互扶助的な一面を持ちます。
# 具体的なものを示さないなら手助けも減るでしょう。
# 仕事で教えている教師の方に授業料の範囲で質問するか、
# 友人と協業するか。後は誰かを雇うなり発注されるのが早そうです。
# 元投稿に対するレスではありません。
テーマとしては面白いものなので'自己研鑽'のために書いてみました。
「関数」ではなく、「'('の直前の識別子」をカウントします。
完璧にはほど遠いですが、コメントの削除、プリプロセッサコマンドの分離、文字列リテラルの判定、トークン分割といった基本的な処理はひととおり含まれています。
ご批判下さい > 諸賢
# １月半ほど前にいくつかのBBSで見かけた
# 「標準入力からテキストファイルを読み込み行を短い順に出力せよ」
# という課題と出題傾向が良く似ていますね。
# 複数の学生が見境なくあちこちに投稿して聞きまくるのに、自分(達)の努
# 力の結果については何も報告しないという学生の'タチ'も似ています。
# 90%以上の確率で同じ学校の同じ教師による出題だと思います。
# きちんと指導して下さいね > 教師サマ
// exam.
// C/C++言語のソースコードにおける'('の直前の識別子と出現度数を，度数の降順で出力するプログラム例
// コメント，プリプロセッサコマンド，文字列リテラル内はカウントしない
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <sstream>
#include <iostream>
const std::string SYMBOLS = "+-*/%<=>!&|^~?:.,;(){}[]";
const std::string OPERATORS[] =
{
"+=", "++", "-=", "--", "->", "*=", "/=", "%=", "<=", "<<",
"==", ">=", ">>", "!=", "&=", "&&", "|=", "||", "^=", "::",
};
// 文字列str中の位置s以降で，文字列tagに一致する最初の部分文字列の先頭位置(該当ない場合はnpos)を返す
// 位置はstrの先頭を0としたインデックス．また，" "で括られた文字列リテラル内は検索対象外．
std::string::size_type find_tag( const std::string& str, std::string::size_type s, const std::string& tag )
{
std::vector< std::string::size_type > quot;
int back_slash = 0;
for( std::string::size_type pos = s; pos < str.size(); ++pos ){
if( str[pos] == '\"' && back_slash % 2 == 0 ){
quot.push_back( pos );
}
back_slash = str[pos] == '\\' ? back_slash + 1 : 0;
}
if( !quot.empty() ){
for( std::vector< std::string::size_type >::size_type idx = 0; idx < quot.size(); ++idx ){
std::string::size_type pos = str.find( tag, s );
if( pos < quot[idx] ){
return pos;
}
s = quot[++idx] + 1;
}
}
return str.find( tag, s );
}
// テキストデータを読み込み，コメント，プリプロセッサコマンドを除いた文字列に変換する
std::string read_source( std::istream& istrm )
{
std::string output;
// 行単位で読み込みつつ，"// 〜"スタイルのコメント削除，複数行のマクロ定義連結
for( std::string line; std::getline( istrm, line ); ){
std::string::size_type pos = line.find_first_not_of( " \t" );
if( pos != std::string::npos ){
line = line.substr( pos, line.find_last_not_of( " \t" ) - pos + 1 );
pos = find_tag( line, 0, "//" );
if( pos == 0 ){
continue;
}
if( pos != std::string::npos ){
line.erase( pos );
line = line.substr( 0, line.find_last_not_of( " \t" ) + 1 );
}
if( *line.rbegin() == '\\' ){
line.erase( line.end() - 1 );
output += line + ' ';
}
else{
output += line + '\n';
}
}
}
// "/* 〜 */" スタイルのコメント削除
for( std::string::size_type beg = 0; ( beg = find_tag( output, beg, "/*" ) ) != std::string::npos; ){
std::string::size_type end = find_tag( output, beg + 2, "*/" );
if( end != std::string::npos ){
output.erase( beg, end + 2 - beg );
}
else{
output.erase( beg );
break;
}
}
// プリプロセッサコマンド行を除いて返却
std::istringstream iss( output );
output.clear();
for( std::string line; std::getline( iss, line ); ){
if( *line.begin() != '#' ){
output += line + ' ';
}
}
return output;
}
bool is_operator( char first, char second )
{
static const size_t OP_SIZE = sizeof( OPERATORS ) / sizeof( std::string );
std::string symbol;
symbol += first;
symbol += second;
return std::find( OPERATORS, OPERATORS+OP_SIZE, symbol ) != OPERATORS+OP_SIZE;
}
// srcに与えられた文字列を，識別子，キーワード，演算子その他の記号に分割してdestに格納する
// srcはread_source関数による処理後の文字列とする
void tokenize_source( const std::string& src, std::vector< std::string >& dest )
{
dest.clear();
std::string tok;
bool in_dquot = false;
bool in_squot = false;
int back_slash = 0;
for( std::string::size_type pos = 0; pos < src.size(); ++pos ){
if( in_dquot || in_squot ){
tok += src[pos];
}
else if( src[pos] == ' ' || src[pos] == '\t' || src[pos] == '\n' ){
if( !tok.empty() ){
dest.push_back( tok );
tok.clear();
}
}
else if( SYMBOLS.find( src[pos] ) != std::string::npos ){
if( !tok.empty() ){
dest.push_back( tok );
tok.clear();
}
if( is_operator( src[pos], src[pos+1] ) ){
tok += src[pos++];
}
tok += src[pos];
dest.push_back( tok );
tok.clear();
}
else{
tok += src[pos];
}
if( src[pos] == '\"' && back_slash % 2 == 0 ){
in_dquot = !in_dquot;
}
if( !in_dquot && src[pos] == '\'' && back_slash % 2 == 0 ){
in_squot = !in_squot;
}
back_slash = src[pos] == '\\' ? back_slash + 1 : 0;
}
}
// --------------------------------------------------------------------------------------------------
// Application
// C/C++言語のソースコードにおける'('の直前の識別子と出現度数を，度数の降順で出力する．
// コメント，プリプロセッサコマンド，文字列リテラル内はカウントしない
const char* KEYWORDS[] = // 識別子としない文字列
{
"if", "for", "while", "switch",
"sizeof",
"char", "int", "long", "unsigned", "signed", "float", "double",
};
class TokenFreq
{
std::string name_; // 識別子
int freq_; // 度数
public:
TokenFreq() : name_( "" ), freq_( 0 ){}
TokenFreq( const std::string& name, const int& freq ) : name_( name ), freq_( freq ){}
std::string name() const { return name_; }
int freq() const { return freq_; }
bool operator < ( const TokenFreq& rhs ) const // 度数の昇順ソート用
{
return freq_ < rhs.freq_ || ( freq_ == rhs.freq_ && name_ < rhs.name_ );
}
bool operator > ( const TokenFreq& rhs ) const // 度数の降順ソート用
{
return freq_ > rhs.freq_ || ( freq_ == rhs.freq_ && name_ < rhs.name_ );
}
};
void collect_token_front_of_paren( std::istream& istrm, std::vector< TokenFreq >& result )
{
std::vector< std::string > keywords;
for( size_t i = 0; i < sizeof( KEYWORDS ) / sizeof( char* ); ++i ){
keywords.push_back( KEYWORDS[i] );
}
std::vector< std::string > tokens;
tokenize_source( read_source( istrm ), tokens );
if( !tokens.empty() ){
std::map< std::string, int > token_to_freq;
for( std::vector< std::string >::size_type i = 0; i < tokens.size() - 1; ++i ){
if( tokens[i+1] == "("
&& SYMBOLS.find( *tokens[i].rbegin() ) == std::string::npos
&& std::find( keywords.begin(), keywords.end(), tokens[i] ) == keywords.end() ){
++token_to_freq[tokens[i]];
}
}
result.clear();
for( std::map< std::string, int >::const_iterator it = token_to_freq.begin(); it != token_to_freq.end(); ++it ){
result.push_back( TokenFreq( it->first, it->second ) );
}
}
}
int main()
{
std::vector<TokenFreq > result;
collect_token_front_of_paren( std::cin, result );
std::sort( result.begin(), result.end(), std::greater< TokenFreq >() );
for( std::vector< TokenFreq >::const_iterator it = result.begin(); it != result.end(); ++it ){
std::cout << it->name() << " : " << it->freq() << std::endl;
}
}
| ツイート |  |