新加坡程序員考題一則及分析

考題原文：

Problem statement

You must work out a super string class, String, that is derived from the C++ standard class string. This derived String class must add two new member functions

1; a pattern recognition function that returns the number of occurrences of a string pattern in a string. This function must use operator overloading of the / (division) operator.

2; a function get_token that returns tokens extracted from the string

A token is a substring occurring between space characters in the string or between space characters and the end of the string. The string " aaa bbb cc " has the tokens "aaa", "bbb", and "cc" . When the function is called the first time, it must return "aaa", the next time "bbb", and then "cc". When it is called the 4th time it must return an empty string, and when it is called the 5th time it starts all over returning "aaa". Optionally, you may extend the solution so that tokens may be separated by any character out of a set of character given as a string argument.

參考譯文：

問題描述：

你必須創建一個功能強大的串處理類，String，這個類必須從 C++ 中標准的 string 類派生，必須在該派生類中添加兩個成員函數：

1、模式識別函數，返回某個串中指定串模式的出現次數。該函數必須使用 / （除法）運算符重載。

2、用函數 get_token 從串中吸取某個記號並返回該記號。

記號指字符串的一個子串，它位於字符串的空格之間，或者位於空格和串尾之間。如：字符串“ aaa bbb cc ”中的記號有“aaa”、“bbb”和“cc”。當第一次調用該函數時，它必須返回“aaa”，下次再調用時返回“bbb”，第三次調用時返回“cc”，依此類推。當第四次調用該函數時，它必須返回一個空串，最後當第五次調用它時，返回結果又從 “aaa” 開始。你可以隨意擴展這個解決方案，讓記號可以用某組字符以外的任何字符分割，這組字符可以作為一個串參數傳遞。

算法分析（寫成代碼）：

int CMyString::operator/ (const String& sub)
{
　if(sub.IsEmpty())
　　　return 0;
　int count=0;　　　　//sub在字符串中的出現次數count
　int ret=Find(sub);　　//輔助變量ret
　if(ret==-1)
　　 return 0;
　else if(ret<=GetLength())
　{
　　do

　　　count++;
　　　ret=Find(sub,GetAt(ret));
　　}
　　　 while(ret!=-1)
　　 }
　 return count;
}
CString CMyString::get_token()
{
　 static int callednum=0;　　//callednum紀錄該函數的被調用次數
　 int totalnum=operator/('' '');　　//totalnum是空格的總個數
　 if(totalnum==0)
　　　return NULL;
　 int tokennum,ret1=0,ret2=0;　　//tokennum是的token的總個數
　 while((ret1=Find('' '',ret2))!=-1 &&((ret2=Find('' '',ret1))!=-1)
　 {
　　　if(ret1==ret2-1)
　　　　totalnum--;//兩個相鄰的空格算作一個
　　　return　Mid(ret1,ret2-ret1);
　 }
　 if(ret2==-1)
　　　return Right(GetLength()-ret1);
　　tokennum=totalnum;
　 (callednum++)%=tokennum;
}

聲明:這只是粗糙的算法，要想真正實現指定功能，可能細節需要修改！希望對MFC的初學者有所幫助！