Re: [問題] postfix->infix

[BDFishX (便當魚X)]

※ 引述《funnymean (funnymean)》之銘言：
: 想請問一下
: 要把postfix轉成infix
: 有什麼比較好的方法
: 我想破頭想不出來........   （小弟不才...
: 而且又會遇到像這種的
: 345+*
: -> 3*(4+5)
: 括號都出來了
: 真的很.........!$^&*
: 謝謝大家

原本是 1+6*(8*5+3) 好了，轉 postfix 就是 1685*3+*+

做法其實跟把 postfix 的值算出來的方法很像

假設 Stack 一開始是空的

1 6 8 5 * 3 + * +
Stack：

1 6 8 5 * 3 + * +
數目字 push 進 Stack
Stack：1

1 6 8 5 * 3 + * +
同上
Stack：1 6

... 一直同上到 * 為止 ...

1 6 8 5 * 3 + * +
此時的 Stack 應該會是：
Stack：1 6 8 5
因為碰到 operator *，則從 Stack 中 pop 出兩個值
Stack：1 6 ----> 8 5
將 8 5 和 operator * 結合起來得到 8*5，再放回 Stack
Stack：1 6 (8*5)

1 6 8 5 * 3 + * +
數目字 push 進 Stack
Stack：1 6 (8*5) 3

1 6 8 5 * 3 + * +
碰到 operator +，則從 Stack 中 pop 出兩個值，再做結合
Stack：1 6 ---> (8*5) 3
將這兩個結合起來得到 (8*5)+3，一樣再放回 Stack
Stack：1 6 ((8*5)+3)

1 6 8 5 * 3 + * +
碰到 operator *，一樣從 Stack 中 pop 出兩個值
Stack：1 --> 6 ((8*5)+3)
結合起來得 6*((8*5)+3)，放回 Stack
Stack：1 (6*((8*5)+3))

1 6 8 5 * 3 + * +
碰到 operator +，同上
Stack：--> 1 (6*(8*5)+3)
結合起來得 1+(6*((8*5)+3))，放回 Stack
Stack：(1+(6*((8*5)+3)))

1 6 8 5 * 3 + * + End
Stack 裡面應該只有一個值，pop 出來即為結果：(1+(6*((8*5)+3)))

這個就是你要的 infix，如果想要漂亮一點變成 1+6*(8*5+3) 的話也是可以

但這個要怎麼做，就自己想想看吧~~~XD

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.235.10
※ 編輯: BDFishX         來自: 61.59.235.10         (10/25 11:47)
推 funnymean:推薦這篇文章!!   排版真棒!!
推 funnymean:可不可以給一點消括號的提示~  XDD
→ BDFishX:在做結合的過程中，在什麼情況下放進Stack可以不用加刮號?
推 awashharp:還有就是跟什麼東西結合的時候會有ambigious的狀況…
推 willy7954:應該可以用一個變數去記錄上一次做的operator的優先值
→ willy7954:再根據這個變數和這次的operator的優先值比較
→ willy7954:就可以決定這裡是不是要印括號了
→ willy7954:不對= ="..應該是和記下這次的.和下一次的比較XD
推 VictorTom:推一下:)  話說, 小弟我也沒想過消括號的問題Orz
推 funnymean:請問一下，如果是二位數字以上怎麼辦呢？
→ dendrobium:如果會有兩位數的話 通常都會用空格當分隔
→ dendrobium:看題目規定吧
→ willy7954:讀到空格->判斷前面讀的是operator or operand
→ willy7954:是operand就把他轉成數字push到stack裡
推 cholid:原來真的是這樣做 排版很用心 推薦這篇文章~~