[問題] 字串比較的問題

[哼！]

※ [本文轉錄自 C_and_CPP 看板]

作者: jgpnsgm (哼！) 看板: C_and_CPP
標題: [問題] 字串比較的問題
時間: Sat Feb 17 20:11:52 2007

搜尋"字串"好像沒有類似的問題

假設要寫一個判斷指令的程式
譬如說C的compiler或是接收指令(RS232, Internet)來做相對應的事情
如果指令的格式是int或是其他可以轉成int的type
就可以用switch case來做...

但是如果是字串...switch case不支援字串...(C,C++,Java)

一個很直覺的方式是用if else 來做

################## start ###################
char cmd[100];
getCmd(cmd);

if ( strcmp ( cmd, "reboot" ) == 0 )
reboot();
else if ( strcmp ( cmd, "shutdown" ) == 0 )
shutdown();
else if ( strcmp ( cmd, "play" ) == 0 )
play();
else if ....
else if ....
else if ....

################## end #####################
如果有一百個指令...就要寫100個if else

如果要用switch case來作....

################## start ###################
char cmd[100];
getCmd(cmd);

switch ( cmd[0] )
{
case 'r':
reboot();
break;
case 's':
shutdown();
break;
case 'p':
play();
break;
default:
break;
}

################## end #####################
這裡switch case舉的例子比較不好，
在某些指令較短，而且有分類的情況下似乎比較好管理

但是以上這兩個方法，看起來應該不是最好的做法
如果switch case能直接支援string應該比較好管理
但不幸的是沒有支援
想請問大家的是，這類的程式應該要怎麼寫才好呢
還請大家提供一些較好的方法
thanks.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.31.135.140

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.31.135.140

[骨頭]

有個用空間換取時間的方法，
用String 作hash建表。

再直接對HASH後的內容處理:P


這個問題讓我想到State Pattern
不過要用在指令判定上 這可能不太適用..;p

--
 String temp="relax"; | Life just like programing
 while(buringlife) String.forgot(temp); | to be right or wrong
 while(sleeping) brain.setMemoryOut(); | need not to say
 stack.push(life.running); | the complier will
 stack.push(scouting.buck()); | answer your life
 stack.push(bowling.practice()); | Bone everything

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.171.121.11

[小安]

※ 引述《jgpnsgm (哼！)》之銘言：
: ################## end #####################
: 如果有一百個指令...就要寫100個if else
: 如果要用switch case來作....
: ################## start ###################

如果要顧及效率的話，
我應該會建立一台 DFSM (確定有限狀態自動機)

這樣的好處是，如果某些指令具有相同的字首
則那些重複的部份只需要比較一次


--
NPDA - Non-deterministic PushDown Automata
(不確定是否推倒自動機)
DPDA - Deterministic PushDown Automata
(確定會推倒自動機)

得証: DPDA 效率比較高

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.148.184

[痞子軍團團長]

※ 引述《jgpnsgm (哼！)》之銘言：

public static int findStringInArray(String cmd, String[] array){
for(int i=0; i<array.length; i++){
if(array[i].equal(cmd)){
return i;
}
}
return -1;
}


//somewhere in your need
switch(findStringInArray("XD", commandSet)){
case COMMAND.XD:
callXDProcedure();
}

//好像是在 Programming Pearl 這本書看到的方法
//應該最符合原 po 吧？
//至於 tkcn 那種... 仰之彌高... [遠目]

--
 侃侃長論鮮窒礙  首頁：http://www.psmonkey.idv.tw
 眾目睽睽無心顫  Blog：http://ps-think.blogspot.com
 煢居少聊常人事 
 殺頭容易告白難  歡迎參觀 Java 版（@ptt.cc）精華區 \囧/

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.195.92

[愚人]

※ 引述《TonyQ (骨頭)》之銘言：
: 有個用空間換取時間的方法，
: 用String 作hash建表。
: 再直接對HASH後的內容處理:P
: 這個問題讓我想到State Pattern
: 不過要用在指令判定上 這可能不太適用..;p

用 Hash 是個好方法 :P

============================================================
// 建立一個命令的範本，用 toString 直接傳回命令的名稱

public abstract class AbstractCommand extends Object{
public void execute() {
}

// 懶得用 HashMap，只好改寫 toString 配合 HashSet
public String toString(){
StringBuffer buf = new StringBuffer();
buf.append(super.toString());
return buf.substring(0, buf.indexOf("@"));
}
}

============================================================
// 寫下你的命令要做些什麼

public class GetPizzaCommand extends AbstractCommand{

public void execute() {
System.out.println("Pizza ! Pizza!");
}

}


public class LookUpCommand extends AbstractCommand{

public void execute() {
System.out.println("Look it up");
}

}

============================================================
// 寫個 invoker
// 所有的 command instance 要加在 hash set 之內

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Invoker {
Set s;

public Invoker(HashSet s) {
this.s = s;
}

public void doIt(String cmd) {
for (Iterator it = s.iterator(); it.hasNext();) {
final AbstractCommand c = (AbstractCommand) it.next();
if (c.toString().equals(cmd)) {
c.execute();
break;
}
}
}
}


============================================================
// 主菜在這裡
import java.util.HashSet;

public class JustDoIt {
public static void main(String[] args) {
HashSet commandSet = new HashSet();
commandSet.add(new LookUpCommand());
commandSet.add(new GetPizzaCommand());
// add many commands you wanted

Invoker e = new Invoker(commandSet);
e.doIt("LookUpCommand");
e.doIt("No Such Command");

}
}


============================================================

有點麻煩的 switch case 不見了

會是仿造 Command Pattern 的設計，

因為想了一下如果用 Hash 要自己維護 Key 會有一點麻煩

多打字就增加打錯的機會，索性修改了 Command 的 toString

再弄個 Invoker 去執行我們的 command

即使沒有找到 command 或沒有這個 command 也不會有什麼錯誤而終止

會這樣設計的理由是，由您的語意來看

我感覺不到命令是前後相關的，所以沒有打算做 stateful 的設計

(DFA, state pattern ...if-goto etc.)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.173.253

[!H45]

※ 引述《qrtt1 (愚人)》之銘言：
: 用 Hash 是個好方法 :P
[...]
: ============================================================
: // 寫個 invoker
: // 所有的 command instance 要加在 hash set 之內
: import java.util.HashSet;
: import java.util.Iterator;
: import java.util.Set;
: public class Invoker {
: Set s;
: public Invoker(HashSet s) {
: this.s = s;
: }
: public void doIt(String cmd) {
: for (Iterator it = s.iterator(); it.hasNext();) {
: final AbstractCommand c = (AbstractCommand) it.next();
: if (c.toString().equals(cmd)) {
: c.execute();
: break;
: }
: }
: }
: }
: ============================================================
[...]

這邊仍然使用了iterator, 循序檢查, 花費時間 O(n)
如果改用Jump table, 或是Event trigger, 將可縮短花費時間 O(1)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.192.62.227

[愚人]

※ 引述《H45 (!H45)》之銘言：
: ※ 引述《qrtt1 (愚人)》之銘言：
: : 用 Hash 是個好方法 :P
: [...]
: 這邊仍然使用了iterator, 循序檢查, 花費時間 O(n)
: 如果改用Jump table, 或是Event trigger, 將可縮短花費時間 O(1)

那直接改 Map 也很快 XD

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.173.253

[godfat 真常]

※ 引述《H45 (!H45)》之銘言：
: [...]
: 這邊仍然使用了iterator, 循序檢查, 花費時間 O(n)
: 如果改用Jump table, 或是Event trigger, 將可縮短花費時間 O(1)

如果要搜尋的目標不多的話，線性搜尋不見得比較慢，可能還更快

--
#!/usr/bin/ruby [露比] /Programming (Kn|N)ight/ 看板《Ruby》
# if a dog nailed extra legs that http://www.ptt.cc/bbs/Ruby/index.html
# walks like an octopus, and Welcome ~Ruby[***@ptt~
# talks like an octopus, then ◢█◣ http://www.ruby-lang.org/
# we are happy to treat it as █   http://www.ruby-doc.org/
# if it were an octopus. ◥ ◤ http://www.rubyforge.org/

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.28.18