娱乐 每 日 算 法 挑 战 （大嘘）【第0x14期】

[Mr.K 018]

第20期来啦！

如各位所见，我给自己挖了两个需要填上的大坑……

这个题虽然是一个表达式求值，但考虑到以后可能出现的冰系魔法2b啥的（暗示），说明这题的目的不是简单的表达式求值哦。大家不一定非要打一个表达式求值的板子出来。

第20期 冰系魔法2a

传说在某个异世界里是存在元素的，也存在元素魔法。那里有一所魔法学院。与其他魔法学院不同，这所学院哪个系的魔法也不教，教的全是魔法背后玄而又玄的深奥知识。但是，来这所学院求学的人却是络绎不绝，因为从这所学院里学到大成之人已经可以自创一系魔法，早已超脱用某个系魔法施法的境界。不过，我们地球人想要一下理解异世界的艰深魔法理论还是很困难的，所以我们当然不会直接像大成之人那样自创魔法。我们从最简单的开始。

在那个异世界有一个魔法小工具，叫做骰娘魔法骰子。向这个骰子输入一个掷骰表达式（别问怎么输入，问就是魔法），这个骰子就能按照表达式的要求自动掷骰子，然后输出（别问怎么输出，问就是魔法）结果。这个小工具在异世界非常流行，几乎家家户户都有。

异世界魔法骰子比地球的骰娘要强大很多。地球的骰娘最多只支持形如rAdB+C的表达式，表示投掷A个B面的均匀骰子，结果取出目的总和再加上C。异世界的骰娘不光支持掷骰，还支持加减乘除四则运算。并且，表达式还能嵌套，允许加括号。比如说：(r3*5+7d2*(r1d6)-1)/2。这个表达式的意思是：先掷一枚6面骰子，出目乘2后减去1，作为骰子的面数（记为A），之后投掷15+7=22个这样的骰子（注意每个骰子都有A个面，而非每个骰子的面数都不相同），出目总和除以2，舍弃小数部分后作为结果输出。

我们规定，括号的运算优先级最高（废话），其次是乘除法，再次是加减法，最后是掷骰子运算。

MrK-018手头已经有了一些用来进行四则运算、模拟掷骰子和输出用的魔法。给定一个掷骰子表达式，他想知道怎样按顺序地调用这些魔法，才能得到表达式要求的输出。

输入

一个掷骰表达式。保证涉及到的数字只有十进制非负整数，不涉及小数。整数可能以以下几种形式出现：

• 一般形式，如114514
• 科学计数法，如1.14e5,1.14E5,3E8等等。

输出

这个表达式对应的魔法调用序列。对于不符合文法的表达式，输出一行Syntax error!。输出的数字格式要与

样例输入1

(r3*5+7d2*(r1d6)-1)/2

样例输出1

输出不唯一，此处展示一种可行的输出。

1: rd 1 6
2: mul 2 [1]
3: sub [2] 1
4: mul 3 5
5: add [4] 7
6: rd [5] [3]
7: div [6] 2
8: out [7]

样例输入2

4e50

样例输出2

1: out 4e50

样例输入3

4d

样例输出3

Syntax error!

 

五月 4, 2020，由Mr.K 018修改

[yhz012]

单说表达式求值其实倒是能改写成逆波兰表示法然后用栈带走吧……

[Mr.K 018]

1 分钟前, yhz012 说道:

单说表达式求值其实倒是能改写成逆波兰表示法然后用栈带走吧……

对这道题而言是的

但是显然下一道题就不会这么轻松了x

[久帝]

我tm都学魔法了怎么还tm要学数学233

[Mr.K 018]

4 分钟前, 久帝 说道:

我tm都学魔法了怎么还tm要学数学233

这恰恰是魔法

[yhz012]

2 分钟前, Mr.K 018 说道:

这恰恰是魔法

数学就是魔法（指让人头疼的程度

 

27 分钟前, Mr.K 018 说道:

但是显然下一道题就不会这么轻松了x

下一题就变成把java翻译成汇编了吧

[Mr.K 018]

刚刚, yhz012 说道:

下一题就变成把java翻译成汇编了吧

一步到位草

好 既然你都这么说了，那就这么定了吧

[yhz012]

2 分钟前, Mr.K 018 说道:

一步到位草

好 既然你都这么说了，那就这么定了吧

别啊，真的会死人的，而且汇编我真的是本科唯一一科差一点挂了的课啊

[Mr.K 018]

1 分钟前, yhz012 说道:

别啊，真的会死人的，而且汇编我真的是本科唯一一科差一点挂了的课啊

真要是java转汇编，那这个题怕是真的要做一个月

每 月 算 法 挑 战

五月 4, 2020，由Mr.K 018修改

[PhoeniXLL]

我傻了，竟然能在同盟做编程题

[Mr.K 018]

1 分钟前, PhoeniXLL 说道:

我傻了，竟然能在同盟做编程题

这个题不难哦，数据结构第一章内容

少侠不来试试吗？

[PhoeniXLL]

刚刚, Mr.K 018 说道:

这个题不难哦，数据结构第一章内容

少侠不来试试吗？

懒啊……年纪大了打不动代码这题我嘴巴了

[Mr.K 018]

3 分钟前, PhoeniXLL 说道:

懒啊……年纪大了打不动代码这题我嘴巴了

有糖拿的！

给出伪代码就行，能拿200节操(max)呢！

[末炼琴]

"之后投掷15个这样的骰子",不是应该是15+7个骰子吗?

[Mr.K 018]

3 分钟前, 末炼琴 说道:

"之后投掷15个这样的骰子",不是应该是15+7个骰子吗?

确实，我马上改

[北冥有鱼1573]

数据结构刚学到表达式求值我试着写一个当练习（

不过r d三目运算符（？）好像有点难处理

[yhz012]

1 小时前, 北冥有鱼1573 说道:

数据结构刚学到表达式求值我试着写一个当练习（

不过r d三目运算符（？）好像有点难处理

R x D y不算三目吧，某种意义上你可以把r丢掉，视作x D y这个运算，就是正常的中间运算了

换个说法

s R x D y t= s (x) D y t，就是把r和d之间加个括号，然后d视为双目运算符就可以了

[Mr.K 018]

2 小时前, 北冥有鱼1573 说道:

数据结构刚学到表达式求值我试着写一个当练习（

不过r d三目运算符（？）好像有点难处理

仅就这个题而言，可以把所有的r都丢掉，然后把d当成运算符

冰系魔法系列的题实际上都是编译原理来着。刚学数据结构的话，可以考虑把整个表达式当成一颗树来看待

另外，不要忘记数字有两种表示方式哦

五月 4, 2020，由Mr.K 018修改
删去说过了好多遍的废话

[PhoeniXLL]

19 小时前, Mr.K 018 说道:

仅就这个题而言，可以把所有的r都丢掉，然后把d当成运算符

冰系魔法系列的题实际上都是编译原理来着。刚学数据结构的话，可以考虑把整个表达式当成一颗树来看待

另外，不要忘记数字有两种表示方式哦

应该是把r当做(再在d前面加上)吧

直接去掉r会出问题

[Mr.K 018]

16 分钟前, PhoeniXLL 说道:

应该是把r当做(再在d前面加上)吧

直接去掉r会出问题

其实一样，把d当成一个优先级比加减号还低的运算符就行

[PhoeniXLL]

1 分钟前, Mr.K 018 说道:

其实一样，把d当成一个优先级比加减号还低的运算符就行

1+r1+1d1

[Mr.K 018]

1 分钟前, PhoeniXLL 说道:

1+r1+1d1

（尴尬）

emmm好像是这样的

[北冥有鱼1573]

真的做起来之后了更多的问题……rd运算符真的很不好搞

比方说，r1d6*r1d6是

1. (r1d6) * (r1d6)，掷两枚六面骰子的结果相乘
2. r1d(6 * r1d6)，先掷一枚6面骰子结果为x，然后掷另一枚6x面骰子

两者中的哪个？

两种掷法结果必然是不一样的，前面一种方法没办法得到大于6的素数，而后一种可以

五月 5, 2020，由北冥有鱼1573修改

[北冥有鱼1573]

其实我遇到的最大的问题是，使用栈计算表达式时，d运算符的优先级最低，因此四则运算先被算好，roll点会在最后从右到左计算（从右到左是因为栈后进先出，表达式最右边的最先出来）

因此当遇到像r(r1d6)d20这样的嵌套roll点时，需要先算外层的r x d20，这就没法继续算了……

[yhz012]

7 小时前, 北冥有鱼1573 说道:

其实我遇到的最大的问题是，使用栈计算表达式时，d运算符的优先级最低，因此四则运算先被算好，roll点会在最后从右到左计算（从右到左是因为栈后进先出，表达式最右边的最先出来）

因此当遇到像r(r1d6)d20这样的嵌套roll点时，需要先算外层的r x d20，这就没法继续算了……

最坏情况其实可以先单独用栈处理一遍rd来变成()d的模式，接着再用常规调度场算法。因为反正都是线性扫一遍，不影响最后O(n)的结果（虽然会加大常数）