Лаба 1-3 Лабы / lab1 / main

#include <stdlib.h>
#include <iostream>

using namespace std;

//символы для чтения из файла
enum {OpenSymb='{',CloseSymb='}',OpenVeSymb='<',CloseVeSymb='>', SeparatorSymb=','};

//перечисления типов множества
typedef enum {MTypeElement, MTypeSet, MTypeVector, MTypeNull} MSetType;


//структура множества

struct MSet_{
  bool is_set;		//являектся ли элемент множеством
  bool is_vector;	//являектся ли множество направленым
  bool is_null;		//являектся ли множество нулевым
  char name[256];	//имя элемента  
  int col;			//число вхождений
  MSet_ *entrys;	    //указатель еа массив вхождений помножеств в данное множество
};

//создание множества

MSet_ create_set(MSetType type,char *name){
	MSet_ new_set;
    if(type == MTypeElement) new_set.is_set = false, new_set.is_vector=false, new_set.is_null=false;
    if(type == MTypeSet) new_set.is_set=true, new_set.is_vector=false, new_set.is_null = false;
    if(type == MTypeVector) new_set.is_set=true, new_set.is_vector=true, new_set.is_null=false;
    if(type == MTypeNull) new_set.is_set=false, new_set.is_vector=false, new_set.is_null=true;
    strcpy(new_set.name,name);
    if(type == MTypeNull)
      strcpy(new_set.name,"");
	new_set.entrys = new MSet_[6666];
	new_set.col = 0;
	return new_set;
  }


//добавление подмножества в множество
//add_set - добавляемое множество 
//set - множество, в которое добавляем
MSet_ insert_set(MSet_ add_set, MSet_ set){
	if(!add_set.is_set && !add_set.is_null && !add_set.is_vector && strlen(add_set.name)==0){}else
	set.entrys[set.col++]=add_set;	
	return set;
}


//сравнение множеств
  bool compare_sets(MSet_ a, MSet_ b){
    if(a.is_vector && !b.is_vector) return false;
    if(!a.is_vector && b.is_vector) return false;
    if(a.col!=b.col) return false;
    if(!a.is_set && !b.is_set && strcmp(a.name,b.name)==0) return true;
    if(!a.is_set && !b.is_set && strcmp(a.name,b.name)!=0) return false;
    if((!a.is_set && b.is_set) || (a.is_set && !b.is_set)) return false;
    for(int i=0;i<a.col;i++){
      bool found=false;
      for(int j=0;j<a.col;j++)
	if(compare_sets(a.entrys[i], b.entrys[j])) 
	   if((a.is_vector || b.is_vector) && i==j)
	  found=true; else if(!a.is_vector && !b.is_vector) found=true;
      if(!found) return false;
    }
    return true;
  }

//поиск подмножества mset в множестве set
  bool findSet(MSet_ mset, MSet_ set){
	for(int i = 0;i<set.col;i++)
		if(compare_sets(mset,set.entrys[i])) return true;
    return false;
  }

//вывод множества на экран
  void debugSet(FILE *f,MSet_ mset){
    if(mset.is_set){
      if(mset.is_vector) fprintf(f,"<"); else fprintf(f,"{");
      for(int i=0;i<mset.col;i++){
	MSet_ ms=mset.entrys[i];
	if(!ms.is_set){
	  fprintf(f,"%s",ms.name);
	}
	else
	  debugSet(f,ms);
	if(i!=mset.col-1)
	  fprintf(f,",");
      }
      if(mset.is_vector) fprintf(f,">"); else fprintf(f,"}");
    }
  }

  bool peresek(MSet_ a, MSet_ b){
	  for(int i=0;i<a.col;i++)
		for(int j=0;j<b.col;j++)
				if(compare_sets(a.entrys[i],b.entrys[j])) return true;
	  return false;
  }
//перечисление положений при считывании множества из файла
enum {StateSepReaded,StateStartParsing=101,StateNameReading=102, StateNameReaded=103, StateSetReaded=104, StateSetReading=105, StateElementReaded=106, StateElementReading=107} typedef ParserState;

//ф-ция выводит ошибку на экран
void onError(char *error,int pos){
	printf("Parse error at %d : %s\n",pos,error);
}
char all[10000];
char last_s;
bool isMain;
int i=0;
//преобразование строки char all[10000] в множество
MSet_ parseSet(MSet_ myset){
    MSet_ mset = myset;
    ParserState state = StateStartParsing;
    bool setOpened=false, setVeOpened=false;

    if(last_s=='{') state = StateSetReading, setOpened=true;
    if(last_s=='<') state = StateSetReading, setVeOpened=true;
    if(last_s=='}'|| last_s=='>') state = StateSetReaded;//setOpened=false;

	MSet_ tmp_set = create_set(MTypeSet,"");
	MSet_ ns = create_set(MTypeSet,""), vs=create_set(MTypeSet,"");
    char c,tmp[256]="";
    int last_pos = 0;
    bool isMain1=isMain;
    while(true){
      i++;
      if(i>strlen(all)) break;
      c=all[i];
      switch(c){
      case OpenSymb:
	if(last_s=='}' || last_s=='>' || isalpha(last_s) || isalnum(last_s) || last_s=='_'){
	  onError("expected , ",i);
	}
	state = StateSetReading;	
	tmp_set=create_set(MTypeSet,"");
	last_s = OpenSymb;

	tmp_set=parseSet(tmp_set);
	if((tmp_set.col>0) || (mset.is_vector))
	   mset=insert_set(tmp_set,mset);
	isMain=false;
	break;
      case OpenVeSymb:
	if(last_s=='}' || last_s=='>' || isalpha(last_s) || isalnum(last_s) || last_s=='_'){
	  onError("expected , ",i);
  	}
	state = StateSetReading;

	tmp_set=create_set(MTypeVector,"");
	last_s = c;
	tmp_set=parseSet(tmp_set);

	mset=insert_set(tmp_set,mset);
	break;
      case SeparatorSymb:
	if(last_s=='{' || last_s=='<' || last_s==',' )
	  onError("expected name before separator",i);
	if(state == StateNameReading){
	  if(strcmp(tmp,"")==0)
	    onError("name can't be 0 lenght",i);

	  mset=insert_set(create_set(MTypeElement,tmp), mset);
	  strcpy(tmp,"");
	  state = StateNameReaded;
	};
	last_s=c;
	break;
      case CloseSymb:
	if(setVeOpened){
	  onError("expected >",i);
	}
	if(!setOpened){
	   onError("can't find { before }",last_pos);
	}
	if(state == StateNameReading){

      mset=insert_set(create_set(MTypeElement, tmp),mset);
	  strcpy(tmp,"");
	  last_s = c;

	  return mset;
	}
	if(state == StateNameReaded){
	  onError("expected name before >",i);
	}

	if(state == StateSetReading){
	  if(compare_sets(mset,ns) || compare_sets(mset,vs)){
	  }else{
	    last_s = c;
	    return mset;
	  }
	}

	tmp_set=create_set(MTypeSet,"");
	last_s = c;
	setOpened = false;
	return tmp_set;
	break;
      case CloseVeSymb:
	if(setOpened)
	  onError("expected }",i);
	if(!setVeOpened){
		onError("can't find < before >",last_pos);
	}

	if(state == StateNameReading){
	  mset=insert_set(create_set(MTypeElement, tmp),mset);
	  strcpy(tmp,"");
	  last_s = c;
	  return mset;
	}
	if(state == StateNameReaded){
	  onError("expected name before >",i);
	}
	if(state == StateSetReading){
	  if(compare_sets(mset,ns) || compare_sets(mset,vs)){
	  }else{
	    last_s = c;
	    return mset;
	  }
	}
	tmp_set=create_set(MTypeVector,"");
	last_s = c;
	setVeOpened = false;
	return tmp_set;
	break;
      default:
	if(isalpha(c) || isalnum(c) || c=='_'){
	  if(last_s!=',' && last_s!='{' && last_s!='<' && !isalpha(last_s) && !isalnum(last_s) && last_s!='_'){
		if(setOpened || setVeOpened)
			onError("expected , ",i);
		if(!setOpened)
			onError("expected { ",i);
		else
			onError("expected < ",i);
	  }
	  
	  if(state!=StateSetReading && state!=StateSetReaded && state!=StateNameReading && state!=StateStartParsing && state!=StateNameReaded){
	    onError("expected open set symbol ",last_pos);
	    }
	  state = StateNameReading;
	  sprintf(tmp,"%s%c",tmp,c);
	  last_s=c;
	}else{
		if(c!=' ' && c!='\n' && c!='\r' && c!='\0' && c!=-1){
		    printf("<%c>\n",c);
			onError("unknown symbol ",i);
		}
	}
	break;
      }
    };
    if(setOpened)
      onError("expected } at",i);
    if(setVeOpened)
      onError("expected > at",i);
    return mset;
  }

//генерирует все воможные множества по n элементов из исходного
//возвращаетмножество, содержащее сгенерированные элементы
  MSet_ gen_sets(MSet_ in_set,int n){
	int n_max=in_set.col;//получаем кол-во 
	MSet_ result = create_set(MTypeSet,"");
		int *current = new int[n],i;
		for(i=0;i<n;i++)
			current[i]=0;
		while(1){
			current[n-1]++;
		    for(i=n-1;i>=1;i--)
				if(current[i]>=n_max){
					current[i]=0;
					current[i-1]++;
				}

			MSet_ for_add = create_set(MTypeSet,"");
			bool added=false;
			for(i=0;i<n;i++)
				if(!findSet(in_set.entrys[current[i]],for_add))
					for_add = insert_set(in_set.entrys[current[i]],for_add), added=true;			
			if(!findSet(for_add,result))
				result = insert_set(for_add,result);
			if(current[0]==n_max) break;
		}
		delete current;
	return result;
  }


  //ф-ция для решения задачи
  MSet_ solve(MSet_ in_set){
	MSet_ result = create_set(MTypeSet,"");
	MSet_ help =gen_sets(in_set,(in_set.col+1)/2);//генерируем множество из всех возможных элементов по n/2 элементов из исходного
	//n/2 - половина числа исходных элементов

	//выбираем 2 множества  таких, что:
	//они являются не пересекающимися
	//содержат в себе n/2 элементов
	//иобьединяем их в одно
	for(int i=0;i<help.col;i++) 
		for(int j=0;j<help.col;j++)
			if(i!=j && !peresek(help.entrys[i],help.entrys[j]) && help.entrys[i].col==(in_set.col+1)/2 && help.entrys[j].col==(in_set.col+1)/2){
				MSet_ add = create_set(MTypeSet,"");
				add = insert_set(help.entrys[i], add);
				add = insert_set(help.entrys[j], add);
				result = insert_set(add,result);
			}
	//возвращаем множество полученых пар
	return result;
  }
int main(int argc, char *argv[]){
	//считываем содержисое файла в сроку
	FILE *f = fopen("sample","r");
	strcpy(all,"");
	char c = fgetc(f);
	while(!feof(f)){
		sprintf(all,"%s%c",all,c);
		c = fgetc(f);
	}
	fclose(f);
	last_s=all[0];
	//преобразовываем множество в строку
	MSet_ main_set =  parseSet(create_set(MTypeSet,""));		
	//если число подмножест исходного множетсва - не четное чило
	//выводим "error" на экран и выходим из программы
	if((main_set.col+1)%2!=0){
		printf("error!\n");
		return -1;
	}
	debugSet(stdout,main_set);
	printf("\n");

	//
	MSet_ result = solve(main_set);
	printf("solved\n");
	//выводим в файл пары сгенерированых множеств
	FILE *out=fopen("output","w");
	for(int i=0;i<result.col;i++){
		debugSet(out,result.entrys[i]);
		fprintf(out,"\n");
	}
	fclose(out);
	return 0;
}