作者BDFishX (便当鱼X)
看板C_and_CPP
标题Re: [问题] postfix->infix
时间Sun Oct 25 11:46:28 2009
※ 引述《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)
1F：推 funnymean:推荐这篇文章!! 排版真棒!! 10/25 11:52
2F：推 funnymean:可不可以给一点消括号的提示~ XDD 10/25 11:56
3F：→ BDFishX:在做结合的过程中，在什麽情况下放进Stack可以不用加刮号? 10/25 11:59
4F：推 awashharp:还有就是跟什麽东西结合的时候会有ambigious的状况… 10/25 12:38
5F：推 willy7954:应该可以用一个变数去记录上一次做的operator的优先值 10/25 12:41
6F：→ willy7954:再根据这个变数和这次的operator的优先值比较 10/25 12:41
7F：→ willy7954:就可以决定这里是不是要印括号了 10/25 12:42
8F：→ willy7954:不对= ="..应该是和记下这次的.和下一次的比较XD 10/25 12:43
9F：推 VictorTom:推一下:) 话说, 小弟我也没想过消括号的问题Orz 10/25 13:12
10F：推 funnymean:请问一下，如果是二位数字以上怎麽办呢？ 10/25 13:27
11F：→ dendrobium:如果会有两位数的话 通常都会用空格当分隔 10/25 13:45
12F：→ dendrobium:看题目规定吧 10/25 13:46
13F：→ willy7954:读到空格->判断前面读的是operator or operand 10/25 14:53
14F：→ willy7954:是operand就把他转成数字push到stack里 10/25 14:53
15F：推 cholid:原来真的是这样做 排版很用心 推荐这篇文章~~ 10/25 21:22