#include <iostream>
#include <string>
#include <conio.h>
#include <windows.h>
using namespace std;


string cac1(char c,int n){
	int x=c;
	string res="";
	for(int i=0;i<n;i++)
		res += '0';
	int now=0;
	while(x){
		if(x&1)
			res[n-now-1] = '1';
		x >>= 1;
		now++;
	}
	return res;
}



string chn1(string s,int n){
	string output="";
	for(int i=0;i<s.length();i++){
		output += cac1(s[i],n);
	}
	return output;
}



string cac2(char c){
	int x=c;
	string res="";
	while(x){
		if(x%3 == 0)
			res = "00"+res;
		if(x%3 == 1)
			res = "01"+res;
		if(x%3 == 2)
			res = "10"+res;
		x /= 3;
	}
	res += "11";
	return res;
}



string chn2(string s){
	string output="";
	for(int i=0;i<s.length();i++){
		output += cac2(s[i]);
	}
	return output;
}


int cac3(string s){
	int res=0;
	int b=1;
	for(int i=s.length()-2;i>=0;i-=2){
		if(s[i] == '0'  &&  s[i+1] == '0')
			res += b*0;
		if(s[i] == '0'  &&  s[i+1] == '1')
			res += b*1;
		if(s[i] == '1'  &&  s[i+1] == '0')
			res += b*2;
		b *= 3;
	}
	return res;
}


string rchn(string s){
	string output="";
	string now="";
	for(int i=0;i<s.length();i+=2){
		if(s[i] == '1'  &&  s[i+1] == '1'){
			output += (char)cac3(now);
			now = "";
		}
		else{
			now += s[i];
			now += s[i+1];
		}
	}
	return output;
}



void pre(){
	system("cls");
	printf("此程序的目的为验证对于字符存储的三进制优化可行性\n\
请按下对应按键并按照相应的步骤进行验证，下面是对于1和2的解释：\n\n\
\
  [1] 请输入一个不超过int范围的正整数n，并换行输入待压缩的字符串s，n的大小应与字符串s中字符ASCLL码相匹配\n\
      程序会输出未压缩和压缩过的2进制字符及其长度\n\n\
\
  [2] 请输入待解压的2进制字符串，程序会输出解压后的字符串\n\n\
\
  [q] 退出");
}



int main(){
	while(true){
		pre();
		char push=getch();
		if(push == '1'){
			system("cls");
			int n;
			cout<<"[n]";
			cin>>n;
			string s;
			cout<<"[s]";
			cin>>s;
			string output1="",output2="";
			output1 = chn1(s,n);
			output2 = chn2(s);
			cout<<output1.length()<<" ["<<output1<<"]"<<endl<<endl;
			cout<<output2.length()<<" ["<<output2<<"]"<<endl<<endl;
			system("pause");
		}
		else if(push == '2'){
			system("cls");
			string s;
			cout<<"[s]";
			cin>>s;
			string output;
			output = rchn(s);
			cout<<output.length()<<" "<<output<<endl<<endl;
			system("pause");
		}
		else if(push == 'q'){
			break;
		}
		else{
			cout<<'\a';
		}
	}
	return 0;
}