UVa 327：Evaluating Simple C Expressions

UVa 327：Evaluating Simple C Expressions2014-10-06 csdn博客 shuangde800题目链接：

题目类型：数据结构，二叉树

样例输入：

a + bb - za+b--+c++c+f--+--a f-- + c-- + d-++e

样例输出：

Expression: a + bvalue = 3a = 1b = 2Expression: b - z

题目大意：

给一个表达式，表达式的变量由26个小写字母组成，这26个字母按顺序的初始值分为为1，2，3，……26，并且表达式中一个变量不会重复出现。操作符由+， -， ++， -- （自增和自减有前缀和后缀）。

然后输出这个表达式的值，和每个出现的变量计算之后的值

解题思路：

因为是数据结构专题，最开始的时候自然想到的是建树的方法来做。

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45529.htm

想好方法之后，开始敲代码。等到把建树的代码敲完后，并且准备计算结果时，发现其实这一题并不需要建树也完全可以，而且更加简单。

不管是什么方法，解题的基本思路是，先把表达式的前缀后缀++， --处理掉，那后从左到右计算就结果就行了。

下面是非建树版的代码：

#include<iostream>#include<cstdio>#include<cctype>#include<cstring>#include<deque>#include<vector>#include<algorithm> using namespace std; vector<char>var;deque<int>que;const int MAXN = 120;char str[MAXN];int val[26]; // 用来保存a,b,……z的初始值int increment; // 对输入的字符串进行过滤，消去空格void Filter（）{int pos=0;for（int i=0; i<strlen（str）; ++i）{if（str[i] ！= " "）{str[pos++] = str[i];}}str[pos] = 0; // 字符串结束标志""} // 是否有前缀inline bool havePrefix（int i）{if（str[i-1]=="+"&&str[i-2]=="+" || str[i-1]=="-"&&str[i-2]=="-"）return true;return false;}// 是否有后缀inline bool haveSuffix（int i）{if（str[i+1]=="+"&&str[i+2]=="+" || str[i+1]=="-"&&str[i+2]=="-"）return true;return false;} void PreProsess（）{increment = 0;while（！que.empty（）） que.pop_back（）;var.clear（）;for（int i=0; i<strlen（str）; ++i）{if（str[i]>="a" && str[i]<="z"）{// 有前缀var.push_back（str[i]）;// 把该字母存入if（i>=2 && havePrefix（i））{if（str[i-1]=="+"）++val[str[i]-"a"];else--val[str[i]-"a"];int n = val[str[i]-"a"];que.push_back（n）;str[i-1]=str[i-2] = " "; } // 有后缀else if（i<=strlen（str）-3 && haveSuffix（i））{int n = val[str[i]-"a"];que.push_back（n）;if（str[i+1]=="+"）{++val[str[i]-"a"];--increment;}else{--val[str[i]-"a"];++increment;}str[i+1] = str[i+2] = " ";}else {int n = val[str[i]-"a"];que.push_back（n）;}}}}int GetSum（）{for（int i=0; i<strlen（str）; ++i）{if（str[i]=="+" || str[i]=="-"）{int a=que.front（）;que.pop_front（）;int b=que.front（）;que.pop_front（）;if（str[i]=="+"）que.push_front（a+b）;elseque.push_front（a-b）;}}return que.front（）;} void Solve（）{// 给a,b,c……z 初始值for（int i=0; i<26; ++i）{val[i] = i+1;}Filter（）;PreProsess（）;int sum = GetSum（）;//puts（str）;printf（"value = %d
", sum）;sort（var.begin（）, var.begin（）+var.size（））;for（int i=0; i<var.size（）; ++i）{printf（"%c = %d
",var[i], val[var[i]-"a"]）;} // printf（"
"）;} int main（）{freopen（"input.txt", "r", stdin）;freopen（"output.txt", "w", stdout）;while（gets（str））{printf（"Expression: %s
", str）;Solve（）;}return 0;}