UVa 327 - Evaluating Simple C Expressions
程序员文章站
2024-03-19 09:17:04
...
327-Evaluating Simple C Expressions | 3763 |
30.56%
|
1145 |
70.66%
|
样例输入:
a + b b - z a+b--+c++ c+f--+--a f-- + c-- + d-++e
样例输出:
Expression: a + b value = 3 a = 1 b = 2 Expression: b - z
给一个表达式, 表达式的变量由26个小写字母组成,这26个字母按顺序的初始值分为为1,2,3,……26,并且表达式中一个变量不会重复出现。 操作符由+, -, ++, -- (自增和自减有前缀和后缀)。
然后输出这个表达式的值,和每个出现的变量计算之后的值
解题思路:
因为是数据结构专题, 最开始的时候自然想到的是建树的方法来做。
想好方法之后, 开始敲代码。 等到把建树的代码敲完后, 并且准备计算结果时, 发现其实这一题并不需要建树也完全可以,而且更加简单。
不管是什么方法, 解题的基本思路是, 先把表达式的前缀后缀++, --处理掉, 那后从左到右计算就结果就行了。
下面是非建树版的代码:
#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; // 字符串结束标志'\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);
else
que.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\n", sum);
sort(var.begin(), var.begin()+var.size());
for(int i=0; i<var.size(); ++i){
printf(" %c = %d\n",var[i], val[var[i]-'a']);
}
// printf("\n");
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
while(gets(str)){
printf("Expression: %s\n", str);
Solve();
}
return 0;
}
上一篇: 程序员的浪漫:词云照片 【wordcloud+jieba】
下一篇: MD5加密