坏掉的打字机
贝博士发明了一种能够自动输出数字并求和的打字机,但这台打字机出了一些故障,它除了输出数字以外还会随机地输出其他字符。艾小姐让贝博士不要着急,她写了一段程序,能够让这台打字机即使在这样的情况下也能输出正确答案。那么,你知道艾小姐的程序是怎么写的吗?
输入描述:单行文本(字符数小于100000)。
输出描述:提取该文件中所有的数字,并输出它们的和。如果结果为整数,则输出整数。如果结果为小数,则输出的小数不应该带有末尾的0(字符串中的数字在-999999到999999之间,且最多含有3位小数)。
输入样例:10.20.5.9.9.-8.22.,40.75
输出样例:57.63
考点
字符串、正则表达式
题解
从字符串中提取出符合题意的“合法的”数字,并求和。
在所有出现的非数字的符号中,只有负号“-”和小数点“.”是可以被认为合法的数字的,但也要出现在正确的位置中,假如有连续相连的负号或小数点,也是不可被解析的,应当忽略。所以,解题的方法就是按照“最长匹配”原则,从头至尾依次检查,如果遇到不合法的字符,则跳过,重新开始查找合法的数字,直到匹配出所有合法的数字再进行求和。
比如例子中的字符串:“10.20.5.9.9.-8.22.,40.75”,从头开始检查,10.20 是合法的数字,但是 20 后面的小数点就不合法了,应当忽略;然后从该小数点后面的 5 再次开始检查,5.9 也是合法的数字,但后面的小数点同样不合法,略过;再从 9 开始检查,9. 被认为是 9.0,也是合法的,但是小数点后面的负号“-”不能算在一起,所以记下 9.0,重新开始检查新数字。
上述过程用 while 循环嵌套 if 判断也可以完成,但实在麻烦。最方便的办法就是使用正则表达式了。我们观察题目规定的合法数字,可以发现它们都至少存在这样几个规律:
- 以一个“-”开始或没有“-”;
- 整数部分不限制位数,但至少有一位(不能以小数点开始);
- 有一个小数点“.”或不存在小数点(整数);
- 小数部分最多有三位。(此处有坑,题目中有一个用例出现了四位小数,致使答案也是四位小数)
将上面四部分用正则表达式写出来,就可以得到 -?\d+\.?\d{0, 4},然后使用 re 模块的 findall 方法找到所有数字即可。(为了100% AC此题,写成了 {0, 4} 从而匹配最多四位小数,如果严格按照题意,此处应该写成 {0, 3}。)
代码
s = input().strip()
import re
pattern = "-?\d+\.?\d{0, 4}"
res = round(sum(map(float, re.findall(pattern, s))), 4) # 转换成浮点数求和并保留4位小数
print(str(res).rstrip(".0")) # 去除右边多余的 0 及小数点
布尔零点计数
使一个布尔表达式的值为零的取值组合称为该表达式的一个布尔零点。
比如,布尔表达式A+B+C就只有一个零点,就是(A,B,C)的取值组合(0,0,0)。而布尔表达式A*B*C就有不止一个零点,(A,B,C)的取值组合为(0,0,1)或(1,1,0)都是它的零点。其中A、B、C都是布尔变量,而布尔变量只能取值0或1。
布尔表达式可以把布尔变量去掉而只保留运算符,称为布尔表达式的简写。如:+*(+)就是布尔表达式A*(B+C)的简写。
现在用|表示或运算,它有如下的真值表:
0|0=0
0|1=1
1|0=1
1|1=1
布尔表达式的优先级是:乘法运算优先于加法运算和或运算,但小括号可以改变优先级为“小括号中的内容优先”。
现给出只包含乘法运算和或运算的布尔表达式的简写,求表达式的零点计数。
输入描述:单行文本,表示布尔表达式的简写(字符数小于10000)。
输出描述:表达式的零点计数d(d>=0)。
输入样例:(|)*
输出样例:5
考点
字符串、后缀表达式
题解
首先理解题意,两个布尔变量的乘法(*)运算其实就是逻辑里的与运算,“|”就是或运算,而且题目中的例子也符合逻辑运算的规则:
其中,把 True 换成 1,False 换成 0,就是题目里表述的布尔表达式了,而且是最简单的表达式(只有两个布尔变量),所以,可以通过观察得到规律:
- 乘法运算时,要使结果为 False,有三种可能,即两个变量都为 False,其中一个变量为 False(两种情况)
- 或运算时,要使结果为 False,只有一种情况,即两个变量都为 False
所以解题思路如下:
首先,将题目给出的表达式,按照计算优先级转化为后缀表达式,这样就可以从左至右依次取出布尔变量进行计算。
计算的时候,遵循上面提到的两个规律,设两个布尔变量分别是 与 ,则
-
的结果为 0 的组合个数分别为上面提到的三种可能之和,也就是
-
为 0 的组合数 为 0 的组合数
-
为 0 的组合数 为 1 的组合数
-
为 1 的组合数 为 0 的组合数
-
的结果为 0 的组合个数只有一种可能,也就是
由此可见,为了得到最终结果为 0 的组合数,在每一步的计算过程中,我们还要记录中间计算结果为 1 的组合数。于是,我们可以使用一个二维数组 ( 表示布尔变量的个数)用来表示:当转化为后缀表达式,也就是不用考虑计算优先级的情况下,计算到第 的变量时,结果为 0 和结果为 1 的组合数各是多少。
不难发现,由于我们每次计算都只需要考虑先前最后一次计算的结果,不需要记录每个位置,所以可以将此数组压缩成一维,也就是两个变量 和 ,分别表示计算到最新位置,结果为 0 和为 1 的组合数各是多少。当计算结束,只要输出 的内容即可。
不过,由于在转化为后缀表达式时,我们需要记录布尔变量的位置,而且我们可以提前得出判断:单个布尔变量结果为 0 和为 1 的“组合”数都是 1(因为只有一个变量),所以只要在布尔变量的位置填充进一个 和 都是 1 的数组即可。这样也更方便后缀表达式的计算(因为需要将计算结果压入栈)。
此题在输出时会产生溢出,但原题并未解释如何处理,所以如果使用 Python 的话,需要模拟溢出的过程(对 取模),将溢出后的结果作为答案才能 AC。
代码
formula = input().strip()
n = len(formula)
dp = [1, 1] # 一维数组,保存计算过程中结果为0和为1的组合数
# 以下为转换后缀表达式的模板
pre = {"|":0, "*":1} # 计算优先级,转后缀表达式要用到
stack = list()
post = list()
for i in range(n):
if formula[i] == "(":
stack.append(formula[i])
elif formula[i] == ")":
while stack and stack[-1] != "(":
post.append(stack.pop())
stack.pop()
else:
if i == 0 or i > 0 and formula[i-1] == "(":
post.append(dp.copy()) # 将每个布尔变量的计算结果单独填充
while stack and stack[-1] != "(" and pre[formula[i]] <= pre[stack[-1]]:
post.append(stack.pop())
stack.append(formula[i])
if i == n-1 or i < n - 1 and formula[i+1] != "(":
post.append(dp.copy()) # 将每个布尔变量的计算结果单独填充
while stack: post.append(stack.pop())
# 递推计算开始
for i in post:
if i == "*" or i == "|":
a = stack.pop()
b = stack.pop()
if i == "*": c = [a[0]*b[0]+a[0]*b[1]+a[1]*b[0], a[1]*b[1]] # 三种可能相加
else: c = [a[0]*b[0], a[1]*b[0]+a[1]*b[1]+a[0]*b[1]] # 同理
stack.append(c)
else:
stack.append(i)
# 栈中剩下的内容就是答案
res = stack[0][0]
print(res % 2**32) # 模拟溢出,输出答案