Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs解决,一遍过

Posted by KatrineYang at 2017-01-19 02:14:24 on Problem 1539
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator