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