※ 引述《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.