
平台论坛博客文库

› 论坛 › 程序设计 › Shell › dc.sed 解析

dc.sed 解析 [复制链接]

hbmhalley

小富即安

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2012-04-15 20:12 |只看该作者 |倒序浏览

本帖最后由 hbmhalley 于 2012-04-15 20:54 编辑

http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=1844319&page=1

上个月看见这么个东西瞬间闪瞎狗眼
闲着蛋疼翻出来发现还是值得一看的
于是挖个坑能填完最好。本人语文渣，欢迎拍砖，众人填坑填的快。
由于这玩意实在是个怪物，所以打算先分别说 dc 与 sed ，然后再看 dc.sed 的流程。先说 dc。
dc ：“任意精度逆波兰式计算器”
逆波兰式就是后缀表达式，例如
prefix notation --> reverse polish notation
3 + 4 --> 3 4 +
(3 + 4) * 5 --> 3 4 + 5 *
(3 + 4) * (5 + 6) --> 3 4 + 5 6 + *
没错，省括号。
dc 实时维护一个栈，初始为空。执行 '3 4 + 5 6 + *' 的流程就是：
3 入栈；4 入栈；弹出 4 3 将 7 入栈；5 入栈；6 入栈；弹出 6 5 将 11 入栈；弹出 11 7 将 77 入栈；
最后栈里只剩一个 77 。你可以用 p（打印栈顶）或 f（从顶到底打印整个栈）命令查看结果。试试：
dc -e '3 4+5 6+*p'
除了 + - * / 外，还有 % 用来求余数，~ 同时求商与余数，^ 求幂，| 求模意义下的幂，v 求平方根。
其中 + - * / % ^ 弹栈两个压栈一个，~ 弹栈两个压栈两个，v 弹栈一个压栈一个，| 弹栈三个压栈一个。
除了“主栈”外，dc 还提供寄存器，每个寄存器也是一个栈。有两组控制寄存器的命令（其中 r 表示寄存器的名字。所有寄存器的名字都是单个字符，因此你最多可以用 256 个寄存器）
Lr 弹出 r 寄存器栈顶，将弹出的元素压入主栈； Sr 弹出主栈栈顶，将弹出的元素压入 r 寄存器
lr 将 r 寄存器栈顶元素压入主栈 sr 弹出主栈栈顶，用弹出的元素替换 r 寄存器栈顶（若 r 栈为空则作用同 Sr）
（简而言之，l s 两个命令将“寄存栈”当作“寄存器”在用，而 L S 将其用作栈）
举个例子，'3salala*p' 作用是打印 3 的平方，其中 'salala' 借助寄存器 a 复制栈顶。（其实有个 d 命令作用就是复制栈顶。）
dc 还支持“字符串”，所谓字符串其实是可以被执行的代码，类似 lambda 表达式。用 [..] 表示字符串。
x 命令的作用是弹出栈顶元素，若不是字符串则放回，否则将其执行。例如：
'[3 4+5 6+*p]x' 等价于 '3 4+5 6+*p'
（当然，一个不被执行的字符串也不是一点用没有。）
配合寄存器，dc 便有了流程控制的雏形，例如，可以这样实现 yes 命令：
dc -e '[y][plax]dsax'
稍微画个图解释一下：
[y][plax]dsax [y]
^^^
[y][plax]dsax [y] [plax]
^^^^^^
[y][plax]dsax [y] [plax] [plax]
^
[y][plax]dsax [y] [plax] ([plax] /*I'm register a*/)
^^
[y][plax]dsax [y] [plax] ([plax] /*I'm register a*/)
^ └-> 这是即将被弹出并执行的代码
[y][plax]dsax [y] ([plax] /*I'm register a*/) //Output: y
└-plax
^
[y][plax]dsax [y] [plax] ([plax] /*I'm register a*/) //Output: y
└-plax
^^
[y][plax]dsax [y] [plax] ([plax] /*I'm register a*/) //Output: y
└-plax └-> 这是即将被弹出并执行的代码
^
[y][plax]dsax [y] ([plax] /*I'm register a*/) //Output: yy
└-plax
└-plax
^
...
[y][plax]dsax //Output: yyy..y
└-plax
└-plax
....
└-plax
还有六个用来执行代码的命令：< > = !< !> !=
>r 作用是弹出主栈两个元素，若先出栈的大于后出栈的，则执行寄存器 r 栈顶的代码
其余的都差不多，> 是大于，!< 是不小于，等等。
q 命令退出当前及其父亲的代码执行过程
Q 命令弹出栈顶元素 k，并退出 k 层代码的执行过程
语法很简单吧。但是相当完整。例如
求 20 的阶乘：
dc -e '20[d1-d1<r*]dsrxp'
求 [1,999] 内所有 3 或 5 的倍数之和
dc -e '999 0sw [dlw+sw]sA [dd3%r5%*0=A1-d0!=B]dsBx lwp'
求所有不超过 4,000,000 的斐波那契数之和
dc -e '0 1 1sw 0sx [+lwrdswd4000000!<B]sA [d2%0=ClAx]sB [dlx+sx]sC lAx lxpd'
求 600851475143 的最大质因子
dc -e '600851475143 [lp/lCx]sA [lp1+splCxd1!=B]sB [dlp%0=A]sC 1sp lBx lpp'
以上代码中除了第一个改编自 dc.sed 的 Examples ，其余都是 Project Euler 上的题，代码和第一个相比丑了不少，因为实在摆脱不了传统 C 代码的 if while 的思维习惯，只能提前硬生生的构造语句块。这显然不是长久之计。但我相信 dc 必有其精妙之用，期待高手来发掘。
如果不能摆脱 C 代码的习惯，也有方法构造对应的 dc 代码。例如
if (#) {@} 可以写成：
[@]sA # 0!=A
do {@} while (#) 可以写成：
[@ #0!=A] d sA x
while (#) {@} 可以写成：
[@ # 0!=A] sA # 0!=A
或者 [@ lAx] sB [# 0!=B] dsAx
或者 [q]sq [# 0==q @ lAx] dsAx
然而，这只能解决一层块结构，嵌套的块会让代码混乱不堪。其实上面的后三个例子就是这么强行拼凑出来的。
实际上，与“嵌套块”结构对应，我们维护一个“代码栈”，保证当前代码及其子代码不会干扰父辈代码即可：
if (#) {@@} else {&&} -->
[@@]SR # dSS 0!=R [&&]SR LS 0==R LRLRsrsr
do {@} while (#) -->
[@ # 0!=R] dSRx LRsr
while (#) {@} -->
[# 0==q @ lRx] dSRx LRsr
其中，R 就是“代码栈”。S 用来保存 if 语句 # 的计算结果，以供 else 使用。S 也是栈（因为 if 也会嵌套）。q 专门用来保存 [q]（相当于 break）。r 是垃圾箱（要是 dc 支持删除栈顶就不用多此一举了）。
现在，@ 里也可以有 [] 了。还有函数什么的就不说了。这是 dc 强项。
说这一坨目的不是说明 dc 就该写成这样，而是证明 dc 足够强大，dc 语法再疵也不比 C 差，以提供信心挖掘 dc 潜质。
贴一个构造出来的 dc 代码。同样是 Project Euler 的题：求出可写成两个三位数乘积的最大回文数（答案是 906609：906609 == 913 * 993）
################
100si
100sj
0sm
[
lilj*dsk
0sb
[10~dSxSy lb1+sb d0<R]dSRxLRsr
sr lbSb
[Lx lb1-dsb 0<R]dSRxLRsr
Lbsr
1st
[
[0st]SR Ly!=RLRsr lb1-dsb 0<R
]dSRxLRsr
[
[lksm]SR lmlk>RLRsr
]SR lt1=RLRsr
lj1+
[sr10 li1+ [3Q]SR d1000=RLRsr si]SR d1000=RLRsr sj
lRx
] dSRxLRsr
lmp
################
目前为止，dc 语法说的差不多了，还有些有关精度进制、把栈当数组用等等命令，完整用法见手册。
原本想 dc.sed 重点在 sed 而非 dc，但由于 dc.sed 里有好几处将一个高级 dc 命令换成一串简单 dc 命令的处理方式（难道你认为真的能用正则表达式算平方根么- -|），因此不得不先说 dc。但话说回来，dc.sed 根本没有用到其它工具，如果不把它当成 dc 语言的解释器，它只是借用了 dc 的语法来 **存储任务序列** ，间接实现了平方根等几乎不可能完成的功能。之前不是有个 lookup table 技术么，那这就叫 “dc sequence” 技术吧 ^ ^
待续

复制代码

评分

参与人数 3	可用积分 +19	信誉积分 +2	收起理由
zooyo	+ 5		非常不错
cjaizss	+ 10	+ 2	神马都是浮云
waker	+ 4		感谢分享

查看全部评分

文库|博客

zooyo zooyo 当前离线禁止发言好友博客消息论坛徽章: 3	2楼 [报告] 发表于 2012-04-15 21:45 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
zooyo zooyo 当前离线禁止发言好友博客消息论坛徽章: 3	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

yinyuemi

大富大贵

论坛徽章:: 2

3楼 [报告]

发表于 2012-04-16 07:10 |只看该作者

学习~

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

waker

富甲一方

论坛徽章:: 8

4楼 [报告]

发表于 2012-04-16 08:15 |只看该作者

虽然看不懂楼主在说什么,不过这次看来是非常真的很NB的样子

xiaopan3322

大富大贵

论坛徽章:: 0

5楼 [报告]

发表于 2012-04-16 10:45 |只看该作者

虽然看不懂楼主在说什么,不过这次看来是非常真的很NB的样子

xiaopan3322

大富大贵

论坛徽章:: 0

6楼 [报告]

发表于 2012-04-16 10:51 |只看该作者

强烈建议CU管理员把评分功能加上，现在看到这样好的帖子想加分的权利都没了！！！

评分

参与人数 1	可用积分 +2	收起理由
rdcwayx	+ 2	可以评分啊。

查看全部评分

cjaizss

版主

论坛徽章:: 3

7楼 [报告]

发表于 2012-04-16 11:08 |只看该作者

中午的时候拜读拜读

baby_神

小富即安

论坛徽章:: 20

8楼 [报告]

发表于 2015-09-18 16:57 |只看该作者

竟然如此高大上啊，赞一个，写这些东西的人脑子都怎么想的

返回列表

Chinaunix › 论坛 › 程序设计 › Shell › dc.sed 解析

zooyo zooyo 当前离线禁止发言好友博客消息论坛徽章: 3	2楼 [报告] 发表于 2012-04-15 21:45 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
zooyo zooyo 当前离线禁止发言好友博客消息论坛徽章: 3	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

dc.sed 解析 [复制链接]

评分

评分

浏览过的版块