D. 第二章 · 线程撕裂者

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

在生日party上,当聊到lqq今年生日想收到什么生日礼物时,lqq向你转发了一条新闻:“2022年1月,AMD发布了基于Zen3架构的线程撕裂者5000系列CPU,其中的旗舰型号5995WX具有64核心128线程。”

lqq希望能用这台电脑来飞速完成他的毕设,但他不知道这种CPU计算到底有多快。假设lqq手中现在有一台搭载5995WX的电脑,现在他希望使用这台电脑计算一个表达式的值

由于线程撕裂者的线程之间可以互不干扰的运行,所以它最多可以同时计算128个四则运算(+,-,*,/),每一次四则运算耗时1ns

比如:

在表达式中,它可以先同时计算再计算,总共耗时2ns

但是,在表达式中,它不会先同时计算,而是会分步计算,总共耗时2ns

注意:该计算机不会通过交换律、结合律等策略简化运算。这代表,每组连续加减或连续乘除必须从左向右依次计算。比如:(3ns)不会被简化成(2ns)。实际的运算顺序参考下图:

简单来说,后缀表达式中连续两个数和一个算符即可直接运算,比如说,后缀表达式是。其中的,可以同时计算出来,得到,然后进行下一轮计算。

又简单来说,按照运算顺序给表达式补全所有括号,这个CPU可以同时计算所有同级括号内的计算。比如

(以上解释等价,但如果你正确按照Hint里的那种数据结构做,是绝对正确的)

##不建议使用暴力,可能会比较复杂##

请求出表达式的值与计算机求值所消耗的时间(只考虑运算花费的时间,其他耗时忽略不计)

输入格式

一个仅包含四则运算的表达式,以=为结尾,保证字符串长的小于128

输出格式

两行

第一行为一个数,表示表达式的运算结果(运算过程保留双精度浮点数),输出结果四舍五入保留整数部分

第二行为一个数,表示该表达式的运算时间

样例

【样例输入1】

4+3*2+1=

【样例输出1】

11
3

【样例解释】

先计算再计算再计算,耗时3ns

【样例输入2】

5/4+3*2=

【样例输出2】

7
2

数据范围与提示

字符串长度<128

保证字符串中只包含整数(int范围内),+、-、*、/ 四则运算,括号 (、)和 = 保证字符串以左括号 ( 或 数字 开头,以 = 结尾

提示:-0.5 ≈ -1

Hint. 我们课上讲了什么数据结构,可以体现这次计算下次需要调用这次结果的计算之间的关系,以及同一个周期内进行的计算间的关系呢?

通告标题

通告内容

已知晓