#P14908. [OOI2013预选赛]Phigon
[OOI2013预选赛]Phigon
题目描述
最近,名为 Phigon 的编程语言变得非常流行。它的主要特点是:所有程序都非常短小简洁。遗憾的是,这些程序有时很难看出为什么会运行很久。
你需要回答这个问题。首先,需要编写一个程序分析器,确定程序执行了多少操作。本题考虑 Phigon 语言的简化模型。
Phigon 中有变量。变量名是由小写英文字母组成的字符串,长度不超过 50。变量名不能是 if、while、or、and、not。
Phigon 中有算术表达式,由整数、变量以及算术运算符 +、-、* 组成。形式化定义如下:
<算术表达式> ::= <项> | <项> (+|-) <算术表达式>
<项> ::= <因子> | <因子> * <项>
<因子> ::= -<因子> | <非负整数> | <变量> | (<算术表达式>)
因此,一元负号优先级高于乘法,乘法优先级高于加减法。程序中出现的每个负整数都视为对相应正整数应用一元负号。例如 -42 表示对非负整数 42 应用一元负号。
赋值语句形式如下:
<变量> = <算术表达式>
执行后,左侧变量被赋值为右侧算术表达式的值。变量第一次被赋值后才视为已声明,之后才能在算术表达式中使用。
Phigon 中有逻辑表达式,由算术表达式、比较运算符 <、<=、>、>=、==、!=,以及逻辑运算符 and、or、not 组成:
<逻辑表达式> ::= <合取式> | <合取式> or <逻辑表达式>
<合取式> ::= <逻辑条件> | <逻辑条件> and <合取式>
<逻辑条件> ::= not <逻辑条件> | <算术表达式> (<|<=|>|>=|==|!=) <算术表达式> | (<逻辑表达式>)
因此,not 的优先级高于 and,and 的优先级高于 or。
条件语句形式如下:
if <逻辑表达式>:
<缩进><语句块>
其中 <语句块> 是若干条语句,并且比外层多 4 个空格缩进。若逻辑表达式为真,则执行对应语句块;否则不执行。嵌套条件语句的缩进相应增加到 8 个空格,以此类推。
循环语句形式如下:
while <逻辑表达式>:
<缩进><语句块>
当逻辑表达式为真时,反复执行语句块。
完整程序是一个由赋值语句、条件语句、循环语句组成的语句块:
<语句块> ::= <语句> | <语句> <语句块>
<语句> ::= <赋值语句> | <条件语句> | <循环语句>
你的任务是求出程序执行结束后所有变量的值,以及每种操作被执行的次数。需要统计的操作包括:=、+、-(一元和二元合计)、*、<=、>=、<、>、==、!=、and、not、or。
输入格式
输入文件是一段 Phigon 程序。每条指令占一行,没有空行。每行长度不超过 500,程序中最多 5000 条指令。
保证所有中间计算值和数值常量的绝对值都严格小于 。
保证每个变量在被用于算术表达式之前,都已经通过赋值语句定义。
输出格式
首先输出每种被执行过的操作的调用次数,格式为:
操作: c
其中 为该操作被调用次数。操作信息按字典序输出。
然后输出一行:
total N operations
其中 是执行的操作总数。保证总操作数不超过 200000。
接着输出一个空行,然后按变量名字典序输出程序结束后的变量值,格式为:
变量名: v
样例
样例 1
a=3
b=a+7*a
*: 1
+: 1
=: 2
total 4 operations
a: 3
b: 24
样例 2
a = 1
if (a > 0):
b=a+a*a-(2*a+(-a)*5)
if (a>=0)and (a < 2):
b = b + 1
if (a<=2) and (a ==1) and(a !=666):
b = b + (-3)*(-3)*0*(-3) + 1
if ((not (a>4)) or (a>4) or (a>4)):
b = b + 1
!=: 1
*: 6
+: 6
-: 5
<: 1
<=: 1
=: 5
==: 1
>: 4
>=: 1
and: 3
not: 1
or: 2
total 37 operations
a: 1
b: 8
样例 3
x = 1
while x < 5:
x = x + 1
+: 4
<: 5
=: 5
total 14 operations
x: 5
评分方式
| 测试点 | 分值 | 限制 |
|---|---|---|
| 1–3 | 0 | 样例测试 |
| 4–26 | 30 | 没有 if 和 while 指令 |
| 27–39 | 没有 while 指令 |
|
| 40–49 | 40 | 无额外限制,离线测试 |
每组分数只有在通过该组和所有之前组的测试点时才会获得。