| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
dfs解决,一遍过#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int val[26];
int eval;
bool used[26];
int varNo;
int pos[26];//pos of variable in the string
int invPos[190];
int state[26];//0: no ++/--; 1: ++; -1: --
bool pre[26];//true if pre-inc/dec
bool opr[26];//true if "+" operation
void init(){
eval = 0;
for(int i = 0; i < 26; i++) val[i] = i+1;
for(int i = 0; i < 26; i++) used[i] = false;
varNo = 0;
for(int i = 0; i < 26; i++) state[i] = 0;
for(int i = 0; i < 190; i++) invPos[i] = -1;
}
bool dfs(string &s, int start, int end){
if(start >= end) return true;
if(end == start+1) return false;
if(s[start] != '+' && s[start] != '-') return false;
int zmp = start+1;
while(zmp < end && invPos[zmp]==-1) zmp++;
if(zmp == end || zmp > start+3 || zmp == start+2) return false;
int varName = invPos[zmp];
opr[varName] = (s[start] == '+');
if(zmp == start+3){
if(s[start+1] != s[start+2]) return false;
pre[varName] = 1;
if(s[start+1] == '+') state[varName] = 1;
else state[varName] = -1;
if(dfs(s, start+4, end)) return true;
}
else{
state[varName] = 0;
if(dfs(s, start+2, end)) return true;
if(end >= start+4 && s[start+2] == s[start+3]){
if(s[start+2] == '+') state[varName] = 1;
else state[varName] = -1;
pre[varName] = 0;
if(dfs(s, start+4, end)) return true;
}
}
return false;
}
void process(string s){
init();
int l = s.length();
for(int i = 0; i < l; i++){
if(s[i] < 'a' || s[i] > 'z') continue;
used[s[i]-'a'] = true;
pos[s[i]-'a'] = i;
invPos[i] = s[i]-'a';
varNo++;
}
if(!dfs(s, 0, l)) {
cout << "no solution\n" << endl;
return;
}
for(int i = 0; i < 26; i++){
if(!used[i] || !state[i]) continue;
if(pre[i]){
if(state[i] == 1) val[i]++;
else val[i]--;
}
}
for(int i = 0; i < 26; i++){
if(!used[i]) continue;
if(opr[i]) eval += val[i];
else eval -= val[i];
}
for(int i = 0; i < 26; i++){
if(!used[i] || !state[i]) continue;
if(!pre[i]){
if(state[i] == 1) val[i]++;
else val[i]--;
}
}
cout << " value = " << eval << endl;
for(int i = 0; i < 26; i++){
if(!used[i]) continue;
cout << " " << (char)(i+'a') << " = " << val[i] << endl;
}
}
string igSpc(string s){
string res = "";
int l = s.length();
for(int i = 0; i < l; i++){
if(s[i] != ' ') res += s[i];
}
return res;
}
int main() {
string s;
while(getline(cin, s)){
string ss = igSpc(s);
if(!ss.length()) break;
cout << "Expression: " << s << endl;
process("+"+ss);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator