※ 引述《a26573633 (a26573633)》之銘言：
: 基本C程式語言沒學好,去學資料結構有點崩潰,
: 看到我下面的敘述大概就會了解....我目前有點鳥
: 還請各位給小弟一些指點
: 目前在教遞迴,老師要我們使用遞迴的程式 計算像是+1+*23*45的式子
: 真的不知道該怎麼做,已經卡很久了,還請各位幫忙了,謝謝!!
基礎:
enum OpEnum { plus, minus, multiply, divide, neither_op_nor_digits };
int f(enum OpEnum op, int a, int b) {
switch (op) {
case plus: return (a + b);
case minus: return (a - b);
case mulitply: return (a * b);
case divide: return (a / b);
default: exit(1);
}
}
對吧?
遞迴:輸入是字串,先把以上 enum OpEnum op, int a, int b 合起來想成一個字串.
就字串處理來說,假設你一些函數可以分解字串,取出正確的資料內容.
enum OpEnum extract_op(char[] polish_form, int start, int* end);
int extract_int(char[] polish_form, int start, int* end);
參數 int start 是指從字串中開始尋找的位置, int *end 是指尋找字串之後,
結尾的位置. 為了比較方便一點點, end 是指之前找到字串的尾端位置的下一格位置.
int f(char[] polish_form, int start, int* end) {
enum OpEnum op;
int a;
int b;
int end;
op = extract_op(polish_form, start, &end);
switch (op) {
case plus:
case minus:
case multiply:
case divide:
// 無論 enum OpEnum op 是加減乘除,都是遞迴情況.
a = f(polish_form, end, &end);
b = f(polish_form, end, &end);
switch(op) {
case plus:
return (a + b);
case minus:
return (a - b);
case multiply:
return (a * b);
case divide:
return (a / b);
}
case neither_op_nor_digits:
exit(1);
default:
//這是一種基礎情況,看到字串開頭是數字,就拿那個數字.
return extract_int(polish_form, start, &end);
}
}
再解說個重點: 我說, 函數 f 是
int f(char[] polish_form, int start, int* end);
它是有一個字串開頭餵進來,就有個字串結尾的下一個位置還回去,然後傳回一個整數.
在每個遞迴呼叫時,我都相信有這個特性,並且在函數 f 之內,我維持這個特性.
因為你相信這個函數做的正確,所以看到一個加法,或減乘除,就可以大膽認定,
從運算符號之後先取一個段落做 f 計算,會成功,並且再取一個段落做 f 計算,
也會成功.
那麼,假如有時字串開頭不是運算符號,而是數字,那我就知道是個遞迴的基礎部份.
後序算式的基礎部份就是數字:
digits ::= digit digits | digit
digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
而遞迴部份就是一個運算符號後面接二個段落:
expression ::= op exp_or_digits exp_or_digits
exp_or_digits ::= expression | digits
大概就是如此理解.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.167.44.50
※ 編輯: yauhh 來自: 118.167.44.50 (10/05 23:22)
→
10/05 23:35, , 1F
10/05 23:35, 1F
→
10/05 23:37, , 2F
10/05 23:37, 2F
→
10/06 02:07, , 3F
10/06 02:07, 3F
討論串 (同標題文章)