一些技巧是我在解ACM題目的時候湊出來，跟大家分享一下，雖然不是什麼高深的技術。

這些技巧在解題的時候是有用，但是要實用的code可能比較不適合。

如果有更好的方法也歡迎討論。


在parse輸入的時候，用C可以用strtok，只是那函數不太方便使用，我覺得有兩個缺點。

1. strtok會破壞原始的字元陣列，所以常常需要多做一份複製來使用strtok。
2. strtok一次只能針對一個字串用，如果有同時用strtok的需求，用起來比較麻煩。

用sscanf的缺點是如果分隔符號是動態輸入的，那就變成要自己手動產

生sscanf的format string，會比較麻煩。

下面就從簡單的輸入到複雜的輸入來介紹


最簡單的輸入，就是那種一個數字的輸入，或是一行字串的輸入

可以用 while ( scanf( "%d", &n ) == 1 && n != 0 )

和 while ( gets( buf ) != NULL )

來讀取，其中 n != 0 的判斷是因為有些題目會特別指定某些特殊

數字來代表輸入結束。


再來稍微麻煩一點的是題目輸入的個數是動態的，會先有一筆資料

來告知總共有幾筆輸入，大多數都可以用下面的程式來讀取

while ( scanf( "%d", &n ) == 1 && n != 0 ) {
for ( i = 0; i < n; ++i )
scanf( "%d", &input[ i ] );
}


有些問題是一行一行的輸入，但是演算法必須要知道該行長度，每

次輸入之後還要用strlen來算長度很麻煩，可以用下面的寫法

while ( scanf( "%s%n ", &input, &length ) == 1 ) {
}

其中%n的符號代表這次scanf中讀取了幾個字元，就可以讀進資料又知道長度了。

而且%n後的空白是重要的，因為這樣才可以把換行符號吃掉，長度計算才會對。


如果輸入筆數不固定，而且題目的輸入中也不告訴你，都要

靠自己來parse的。像是輸入為一行以某些特殊符號為分隔符號的輸入

例如

1019 1002 1005 1004 1009 1020 1017 9009 1017 1003 1006

我都是用下面這種方法
gets( buf );
for ( p = buf; sscanf( p, " %d %n", &n, &length ) == 1; p += length ) {
}

其中%n表示這次總共讀了多少個字元，所以可以一直把p調整到還沒處理到的部分。


如果輸入分隔符號不是空白，而是多種分隔符號的

舉例來說

aaa-bbb:ccc-ddd-eee:fff-ggg:hhh-iii:jjj:kkk

這就必須要搭配sscanf的 []功能

for ( p = buf, gets( buf ); ; p += length ) {
if ( sscanf( p, "%3[^:-]%1[:-]%n", &input, &delimiter, &length ) != 2 )
break;
}

其中的3和1表示欄位的長度，如果長度是固定的就可以寫上去，確保正確。

這種方法同時還可以知道分隔符號是什麼，如果想要忽略分隔符號的話可以用%*。


如果輸入中存有一些垃圾輸入，就是完全不需要處理的輸入

像是

AAaaaa-BBBbb:Ccccccc-DDDddd

其中的大寫字母代表是無用的字串，這時候可以用 %*s 來處理

for ( p = buf, gets( buf ); ; p += length ) {
if ( sscanf( p, "%*[A-Z]%[^:-]%*[:-]%n", &input, &length ) != 1 )
break;
}

自動就會把大寫字母忽略，也不用浪費變數去儲存他了，我同時也把delimiter忽略了。

雖然sscanf還沒有辦法像regular expression功能那麼強大，不過還是

有一些不錯的功能。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51
※ azter:轉錄至看板 THUMath95 01/25 20:13