UVA10932题解

· · 题解

题目大意

你有 26 个变量，要进行以下 2 中操作若干次：

  1. 赋值：形如变量=表达式，将变量的值变为表达式的值；
  2. 询问：形如变量或表达式，输出变量或表达式的值。

解题思路

注：以下有关字符串的，默认以 s_0 为起点。

Part 1 大方向

有关表达式的值的问题，当然是要用栈来解决，可它是中缀表达式怎么办嘞 （给它转成后缀不就好了吗） 转完后缀再算自然是个好办法，但我们其实可以边转边算。

Part 2 准备工作

我们定义 2 个栈 st 和 su，分别存放符号和数字，定义一个数组 mp，存放每个变量的值（若变量名为 c，则其值存放在 mp_{c-'a'}），接着遍历表达式 s，先判断它是赋值还是询问，如果是赋值就从 s_2 开始遍历，是询问就从 s_0 开始遍历。

Part 3 转后缀

当我们遍历到 s_i 时，根据 s_i 的值，分出以下 3 种情况：

当 s_i 为变量时，我们直接把变量的值压入 su 即可；
当 s_i 为数字时，我们要先把整个数字分离出来再压入 su；
当 s_i 为运算符时，若 s_i \ne ")"，则我们要先把 st 里所有优先级比 s_i 高的运算符（特别的，认为“(”的优先级最高）再将 s_i 压入 st；否则，不断将 st 的栈顶弹出并计算直到栈顶为“(”，再将“(”弹出。

Part 4 运算

每当我们从 st 中弹出一个运算符，我们就从 su 中弹出 2 个数值进行计算（注意：若 su 中先弹出的数为 a，后弹出的数为 b，st 中弹出的运算符为 -，那么运算结果应该是 b-a，除号同理），然后将运算结果压入 su。

Part 5 结果

当遍历完 s 时，st 有可能不是空的，这种情况就要不断把 st 的栈顶弹出并重复 Part 4，以上步骤做完后 su 的栈顶即为答案，接着看 s 是赋值还是询问，是赋值就将变量的值设为 su 的栈顶，否则输出 su 的栈顶。

AC code

here