作者yantchen (球童Yanting)
看板NTUE-CS101
标题Re: [课业] 资料结构 作业二
时间Sun Oct 25 17:06:38 2009
中序转前序或後序
手算很简单
依序加上括号
然後把运算符号挪到括号前面
再把括号全部吃掉
例如
1+2*3 → (1+(2*3)) → +1*23
写程式的话
用括号会很复杂 ( 也不是不能做喔 )
通常会改用堆叠的方式
下面是参考答案 请用自己的话改写 不要大家都交一样的答案XD
-
中序运算式转前序运算式的演算法
1. 由右往左读取运算式字串
2. 遇到 运算元(数字) → 直接输出
遇到 运算子(符号) 和 右括号 → 判断堆叠顶端的运算子和目前运算子的优先顺序
> 如果比目前的高
→ 先弹出，再把目前运算子压入堆叠
> 如果比目前的低或一样
→ 直接将目前运算子压入堆叠
遇到 左括号 → 将堆叠中的运算子弹出并输出，到右括号为止
3. 重复步骤2，到整个运算式读取结束
4. 如果堆叠不是空的，弹出堆叠中剩下的运算元
5. 将输出的字串反转，就是前序运算式
-
用上面的例子做一次
1+2*3
由右往左读
3*2+1
堆叠 输出
----------- -----------
3 → 数字输出 3 3
* → 符号 压入堆叠 *
2 → 数字输出 2 * 3 2
+ → 符号 压入堆叠 + 3 2 * ( 因为 * 比 + 高 先弹出 )
1 → 数字输出 1 + 3 2 * 1
清空堆叠 3 2 * 1 +
反转结果 + 1 * 2 3 # ok
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.36.97.131
1F：推 jerry771210:有没有中序转後序的 组语版XD 10/25 18:05
2F：→ yantchen:组语做堆叠还蛮痛苦的XD 10/25 18:05
3F：→ yantchen:去年只有排序跟求值耶 今年好狠 10/25 18:06
4F：推 j2612280:哇呜=0= 10/25 19:38
5F：→ yantchen:组语的在这里 10/26 18:20
http://home.educities.edu.tw/wanker742126/win32asm/w32asm_ap02.html
※ 编辑: yantchen 来自: 203.68.15.196 (10/26 18:20)
噢 前面的 运算子 跟 运算元 打反了 後面条件写运算子是对的 前面居然写反XD
※ 编辑: yantchen 来自: 203.68.15.196 (11/02 15:12)