#P3337. Expression Evaluator

    ID: 2338 传统题 文件IO:poj 2000ms 64MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>模拟字符串Tehran 2006 Preliminary

Expression Evaluator

描述

这个问题是关于求值一些 C 风格表达式。要计算的表达式仅包含简单的整型变量和有限集合的运算符;表达式中没有常量。程序中共有 26 个变量,名称为小写字母 a 至 z。求值前,这些变量的初始值为 a=1,b=2,  ,  z=26.a = 1,\quad b = 2,\;\dots,\;z = 26.

允许的运算符有加法和减法(二元 ++ 和 -),含义与众所知的相同。所以,表达式 a+cd+ba + c - d + b 的值为 2 (1+34+21 + 3 - 4 + 2)。另外,输入表达式中也允许出现 ++++ 和 -- 运算符,它们是一元运算符,可以放在变量前后。如果 ++++ 放在变量前,则在该变量的值用于计算整个表达式之前,其值先自增 1。因此 ++cb++c - b 的值为 2。当 ++++ 放在变量后,则该变量先用于计算表达式,然后再自增 1。所以 c++bc++ - b 的值是 1,尽管 cc 在计算结束后会变为 4。 -- 运算符行为相同,只是将操作数减 1。

更正式地,一个表达式按如下方式求值:

  1. 找出所有位于变量前的 ++++。为每个写出自增语句,并将表达式中对应的 ++++ 省略;
  2. 同样处理所有位于变量后的 ++++
  3. 此时表达式中已无 ++++,写出一个语句用于求值此时的表达式(在步骤 1 生成的语句之后、步骤 2 生成的语句之前执行);
  4. 依次执行步骤 1 中的自增语句、步骤 3 中的计算语句,以及步骤 2 中的自增语句。

按此,求值 ++a+b++++a + b++ 等价于执行:

a=a+1; a = a + 1;

result=a+b;result = a + b;

b=b+1;b = b + 1;

输入

输入第一行是一个整数 TT,为测试用例个数;随后 TT 行,每行一个要计算的表达式。表达式中可以有空格,忽略之。保证输入无二义性(如不会出现 a+++ba+++b),也不会对同一个变量同时使用前后 ++++ 或 --(如 ++a++++a++)。并且每个变量在表达式中最多出现一次。

输出

对每个测试用例,先原样输出输入的表达式,再输出完整表达式的值;然后在单独的行上,按字母顺序输出所有出现在表达式中的变量最终值。仅输出被使用过的变量。详见下面样例格式。

输入数据 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