※ 引述《title (MARIA ALWAYS)》之銘言：
: 我有一個問題˙˙
: 例如有一段 infix
: a+b*c/d+e 的式子
: 寫一程式把它變成 prefix
: ++/a*bcde
: 稍微指點就行了˙˙不勝感激
可以試著用如下的定義來 parse 一個式子
Expression := Expression '+' Term
or Expression '-' Term
or Term
Term := Term '*' Num
or Term '/' Num
or Num
Num := Variable
or '(' Expression ')'
這樣的定義(主要基於運算子的結合性與優先序)
可以用在一般的四則運算，幫助你把式子切開來
例如 Expression(a+b*c/d+e)
= Expression(a+b*c/d) '+' Term(e)
= Expression(a) '+' Term(b*c/d) '+' Num(e)
= Term(a) '+' Term(b*c) '/' Num(d) '+' Num(e)
...
把式子切開來以後
就可以用它來 construct 一個 Binary Tree
這個 Binary Tree 的 Leaf Node 是 Variable, 其他 Node 是 Operator
Infix, Prefix, Postfix 其實就是這個 Tree 的 Traversal 順序而已 :)
因為是「稍加指點」，所以就不給程式碼嘍 :)
--
也許人在愛人或被愛的過程中，
內心都藏著一份先天或後天所造成的偏執吧！
才會引發出那麼多不可解釋的愛的問題......
光禹．為真愛承諾
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: t197-58.dialup.
> -------------------------------------------------------------------------- <
作者: CharlieL (少說多做) 看板: C_and_CPP
標題: Re: 有關infix˙postfix˙prefix變換
時間: Sun Mar 21 17:50:39 1999
※ 引述《hotball (哲哲魚)》之銘言：
: ※ 引述《title (MARIA ALWAYS)》之銘言：
: : 哇˙˙˙頗具啟發性耶˙˙
: : 軒田學長可以再多說一點嗎
: : 謝謝˙˙
: If all operators in your experssion are binary operators (i.e. takes two
: operands) then a simple stack implementation will do the job.
: The algorithm can be found in most textbooks about algorithm or data
: structure.
Ya, 學長的意思是醬子的
例如說我們在看這個式子
3+5*6-7/8^9*4
我們可以用醬的方法來作(用兩個 Stack)
Operator Stack
Operand Stack
然後呢？其實蠻簡單的，就是把這句話的 Operator/Operand 取出來
Push 進去 Stack 就可以了
例如說，上面的式子，經過五次 push 後，會變成
-7/8^9*4
Operator: + *
Operand: 3 5 6
這時候進來了一個 '-' 號，注意 '-' 的 Priority 比 '*' 要低
這意謂著什麼呢？就是 '*' 要先算，所以 instead of 直接把 '-' 號推進去
我們先處理 5*6 (如果是計算式子的值，就是把 5,6,* 拿出來，把 30 推進去)
於是 Stack 變成
Operator: +
Operand: 3 30
注意這時 '-' 號仍然意味著 '+' 號可以先算了
所以 Stack 變成
Operator:
Operand: 33
然後，再把 -7/8^9*4 繼續推入，得到
*4
Operator: - / ^
Operand: 33 7 8 9
* 的推入，會先導致 ^ 和 / 的被運算
如此繼續
就可以得到結果了
--
也許人在愛人或被愛的過程中，
內心都藏著一份先天或後天所造成的偏執吧！
才會引發出那麼多不可解釋的愛的問題......
光禹．為真愛承諾
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: t201-54.dialup.