实习2-魔王算法（增强版）[2].cpp

魔王语言 改进班的

#include "stdio.h"
#include "stdlib.h"//动态分配函数库
#define status void
#define overflow -1
typedef struct Slnode   //定义栈的节点类型
{char data;
struct Slnode  *next;
struct Slnode  *prior;
}Slnode;
typedef struct        //定义栈类型
{Slnode *head;
Slnode *tail;
Slnode *now;
}Slstack;
/*主要算法：获得数据到栈oldds中，
将 oldds中的数据转移到work_a_ds栈，有括号的部分转移到函数tran_b()中处理（在work_b_ds中）
将work_b_ds中累积的元素按照规则2进行处理，将结果反回推入work_a_ds中
将work_a_ds中累积的元素按照规则1进行处理，将结果推入newds中
newds中元素即为所要得结果；*/
Slstack oldds,work_a_ds,work_b_ds,newds,work_cc_ds;//四个链式的栈,work_cc_ds()用于第二次进行规则2的处理，是后来加上的
char work[10],work2[10][10];
void main()                             //主函数
{status initstack(Slstack &s);         //初始化栈
char forpop(Slstack &s);                //从栈底至栈顶推出栈元素
status input(void);                    //输入数据到栈oldds
char pop(Slstack &s);                   //从栈顶至栈底推出栈元素
status push(Slstack &s,char e);        //栈的基本操作函数：将元素推入栈
status tran_a(void);                   /*将 oldds中的数据转移到work_a_ds栈，有括号的部分转移到函数tran_b()中处理（在work_b_ds中）；*/
status tran_cc(void);
status tran_b(void);                      //将work_b_ds中累积的元素按照规则2进行处理，将结果推入work_a_ds中
status tran_c(void);                    //将work_a_ds中累积的元素按照规则1进行处理，将结果推入newds中
initstack(oldds);
initstack(work_a_ds);
initstack(work_b_ds);
initstack(work_cc_ds);
initstack(newds);
printf("                   学号03101308，姓名樊儒昆,数据结构课程设计第二篇\n");
printf(" 请输入数据，结束请加字符#,注意输入过程中不要按回车");
input();
tran_a();
tran_c();
tran_cc();
}
status initstack(Slstack &s)//初始化栈
{s.head=(Slnode *)malloc(sizeof(Slnode));
if(!s.head)
exit (overflow);
s.head->next=NULL;
s.head->prior=NULL;
s.tail=s.head;
s.now=s.head;
//printf("initstack right\n");
}
char forpop(Slstack &s)//从栈底至栈顶推出栈元素
{char e;
e=s.now->next->data;
//printf("%c   forpop right\n",	s.now->next->data);
s.now=s.now->next;	
return e;
}
status push(Slstack &s,char e)//栈的基本操作函数：将元素推入栈
{
	Slnode *newbase;
	newbase=(Slnode *)malloc(sizeof(Slnode));
	if(!newbase)
		printf("wrong");
	
	newbase->data=e;
	newbase->prior=s.tail;
	newbase->next=NULL;
	s.tail->next=newbase;
	s.tail=newbase;	
	//printf("%c   push right\n",	newbase->data);
}
char pop(Slstack &s)//从栈顶至栈底推出栈元素
{
	
	Slnode *p;
	char e;
	e=s.tail->data;
	s.tail->prior->next=NULL;
	p=s.tail;
	s.tail=s.tail->prior;
	free(p);
	//if(s.tail->prior==NULL)
	//flag=0;
	return(e);
	
}

status tran_b(void) //将work_b_ds中累积的元素按照规则2进行处理，将结果推入work_a_ds中
{  	while(work_b_ds.head->next->data!=work_b_ds.tail->data)
{push(work_a_ds,work_b_ds.head->next->data);
push(work_a_ds,work_b_ds.tail->data);
work_b_ds.tail=work_b_ds.tail->prior;
}
push(work_a_ds,work_b_ds.tail->data);
}
status input(void)//输入数据到栈oldds
{char ch;
while((ch=getchar())!='#')
{// printf("%c",ch);
push(oldds,ch);
}
ch='#';
push(oldds,ch);
//printf("input right\n");
}

status tran_c(void)//将work_a_ds中累积的元素按照规则1进行处理，将结果推入newds中
{ 
	char ch;
	
	int i=0,j=0;
	
	
	getchar();  
	printf("请输入需要被替换的字母，结束请输入*\n");
	work[i]=getchar();
	do
	{
		getchar();
		printf("您输入的是%c\n",work[i]);
		printf("请输入要替换成什么");
		//gets(work2[i]);
		scanf("%s",work2[i]);
		printf("您输入的是");
		puts(work2[i]);
		//printf(" \n");
		//printf("您输入的是%c\n",work2[i][3]);
		
		printf("请输入需要被替换的字母，结束请输入*\n");
		getchar();
		i++;
		work[i]=getchar();
	}
	while(work[i]!='*');
	
	printf("输入完毕，谢谢\n");
	int k=0;
	int m=0;
	
	char flag='1';
	while(work_a_ds.now->data!='#')
	{
		ch=forpop(work_a_ds);
		//printf("%c的的的\n",ch);
		//printf("%c   真的是work_a_ds right\n",work_a_ds.now->data);
		
		//printf("现在%c\n",work[0]);
		for(k=0;work[k]!='*';k++)
			
			{if(ch==work[k])
				{//printf("yaohudeshi%c\n",ch);
				flag='0';
				for(m=0;work2[k][m]!='\0';m++)
					{//printf("真实%c",work2[k][m]);
					push(work_cc_ds,work2[k][m]);
					}
				break;
				}
			else
				{flag='1';
				
				}
			}
		
		
		
		if(flag=='1')
			{push(work_cc_ds,ch);
			//printf("真实贵%c\n",ch);
			flag='0';
		
		
			}
		
		
	}	 
	
}
status tran_cc(void)//将work_a_ds中累积的元素按照规则1进行处理，将结果推入newds中
{ 
	
	int k=0;
	int m=0;
	char ch;
	char flag='1';
	while(work_cc_ds.now->data!='#')
	{
		ch=forpop(work_cc_ds);
		//printf("%c的的的\n",ch);
		//printf("%c   真的是work_a_ds right\n",work_a_ds.now->data);
		
		//printf("现在%c\n",work[0]);
		for(k=0;work[k]!='*';k++)
			
			{if(ch==work[k])
				{//printf("yaohudeshi%c\n",ch);
				flag='0';
				for(m=0;work2[k][m]!='\0';m++)
					{//printf("真实%c",work2[k][m]);
					push(newds,work2[k][m]);
					}
				break;
				}
			else
				{flag='1';
				
				}
			}
		
		
		
		if(flag=='1')
			{push(newds,ch);
			//printf("真实贵%c\n",ch);
			flag='0';
		
		
			}
		
		
	}	 
	printf(" \n");
	printf(" 结果是");
	char newtem='a';
	newds.now=newds.head;
	while(newds.now->next->data!='#')
		
	{ 	newtem=newds.now->next->data;
	printf("%c   ",newtem);
	newds.now=newds.now->next;
	}
	printf(" \n");	
	
}


status tran_a(void)/*将 oldds中的数据转移到work_a_ds栈，
有括号的部分转移到函数tran_b()中处理（在work_b_ds中）；*/
{char ch;
char chb;
ch=forpop(oldds);

while(ch!='#')
{		if(ch!='(')
{push(work_a_ds,ch);
//printf("%c   tran_a right\n",	ch);
//printf("%c   work_a_ds right\n",	work_a_ds.now->next->data);
}  
else if (ch=='(')
{//printf("信息已收到");
chb=forpop(oldds);
while(chb!=')')
{  push(work_b_ds,chb);
//printf("%c   work_b_ds OK\n",chb);
chb=forpop(oldds);
}
tran_b();


}
ch=forpop(oldds);
}
ch='#';
push(work_a_ds,ch);

}