#P3337. Expression Evaluator
Expression Evaluator
描述
这个问题是关于求值一些 C 风格表达式。要计算的表达式仅包含简单的整型变量和有限集合的运算符;表达式中没有常量。程序中共有 26 个变量,名称为小写字母 a 至 z。求值前,这些变量的初始值为
允许的运算符有加法和减法(二元 和 ),含义与众所知的相同。所以,表达式 的值为 2 ()。另外,输入表达式中也允许出现 和 运算符,它们是一元运算符,可以放在变量前后。如果 放在变量前,则在该变量的值用于计算整个表达式之前,其值先自增 1。因此 的值为 2。当 放在变量后,则该变量先用于计算表达式,然后再自增 1。所以 的值是 1,尽管 在计算结束后会变为 4。 运算符行为相同,只是将操作数减 1。
更正式地,一个表达式按如下方式求值:
- 找出所有位于变量前的 。为每个写出自增语句,并将表达式中对应的 省略;
- 同样处理所有位于变量后的 ;
- 此时表达式中已无 ,写出一个语句用于求值此时的表达式(在步骤 1 生成的语句之后、步骤 2 生成的语句之前执行);
- 依次执行步骤 1 中的自增语句、步骤 3 中的计算语句,以及步骤 2 中的自增语句。
按此,求值 等价于执行:
输入
输入第一行是一个整数 ,为测试用例个数;随后 行,每行一个要计算的表达式。表达式中可以有空格,忽略之。保证输入无二义性(如不会出现 ),也不会对同一个变量同时使用前后 或 (如 )。并且每个变量在表达式中最多出现一次。
输出
对每个测试用例,先原样输出输入的表达式,再输出完整表达式的值;然后在单独的行上,按字母顺序输出所有出现在表达式中的变量最终值。仅输出被使用过的变量。详见下面样例格式。
输入数据 1
2
a+b
c+f--+--a
输出数据 1
Expression: a+b
value = 3
a = 1
b = 2
Expression: c+f--+--a
value = 9
a = 0
c = 3
f = 5
来源
Tehran 2006 Preliminary