【C言語】【データ構造】スタックの応用(進数変換、括弧一致検査、行編集プログラム、式評価)

スタックの応用——進数変換、括弧マッチング検査、行編集プログラム、式評価順序スタックの基本操作
進数変換:入力された非負の10進数のいずれかに対して、その等値の8進数を印刷出力します.

int main()
{
	SqStack S;
	int x, e;
	
	printf("            ：
");
	if(InitStack(S) != 1) printf("Creatd Error!
");
	scanf("%d", &x);
	while(x)
	{
		Push(S, x%8);
		x = x/8;
	}
	while(S.base != S.top)
	{
		Pop(S,e);
		printf("%d", e);
	}
}

かっこマッチングチェック:式には、丸カッコと角カッコの2つのカッコが含まれていると仮定します.ネストされた順序は任意です.すなわち、()や[([[])]などが正しいフォーマットであり、[(]または[(())または(()])が正しくないフォーマットです.前述のカッコを含む式を入力し、カッコが一致しているかどうかを確認します.

void check()
{ //             ，        
	SqStack s;
	SElemType ch[80],*p,e;
	if(InitStack(s)) //       
	{
		printf("      
");
		gets(ch);
		p=ch;
		while(*p) //     
		switch(*p)
		{
			case '(':
			case '[':	Push(s, *p); p++;
						break; //      ， p++
			case ')':
			case ']':	if(!StackEmpty(s)) //    
						{
							Pop(s, e); //       
							if(*p==')'&&e!='('|| *p==']'&&e!='[') 	
									//         *p   
							{
								printf("isn't matched pairs
");
								exit(ERROR);
							}
							else
							{
								p++;
								break; //   switch  
							}
						}
						else //   
						{
							printf("lack of left parenthesis
");
							exit(ERROR);
						}
			default:	p++; //        ，     
		}
		if(StackEmpty(s)) //         
			printf("matching
");
		else
			printf("lack of right parenthesis
");
	}
}

行編集プログラム:ユーザーが端末から入力したプログラムやデータを受け入れ、入力中にユーザーがエラーを入力することを許可し、エラーが発見されたときに直ちに訂正することができる.たとえば、ユーザーが入力した文字が間違っていることに気づいた場合、前の文字が無効であることを示すために、チェックアウト記号「#」を追加できます.現在入力されているローのエラーが多く、または修正が困難であることが判明した場合は、現在のローの文字が無効であることを示す退行記号「@」を入力します.

void LineEdit()
{
	SqStack s;
	char ch,c;
	int n,i;
	InitStack(s);
	scanf("%d",&n);
	ch=getchar();		//   get  
	for(i=1;i<=n;i++)
	{
		ch=getchar();
		while(ch!='
')
		{
			switch(ch)
			{
				case '#':	Pop(s,c);
							break; 			//         
				case '@':	ClearStack(s);
							break; 			//   s   
				default :	Push(s,ch); 	//       
			}
			ch = getchar();		 //           
		}
		StackTraverse(s,visit); 	//               
		ClearStack(s); 			//   s   
	}
	DestroyStack(s);
}

式評価:負の数を(0-正の数)で表し、=で終了する「+」、「-」、「*」、「/」の4つの演算を含む式を入力します.式の値を出力する必要があります.

unsigned char op[7] = {'+', '-', '*', '/', '(', ')', '='};
unsigned char opcmp[7][7] = {'>', '>', ', ', ', '>', '>',
 							'>', '>', ', ', ', '>', '>',
 							'>', '>', '>', '>', ', '>', '>',
 							'>', '>', '>', '>', ', '>', '>',
 							', ', ', ', ', '=', ' ',
 							'>', '>', '>', '>', ' ', '>', '>',
 							', ', ', ', ', ' ', '='};

SqStack OPTR, OPND;		//OPTR     ，OPND          

Status In(char c, unsigned char op[])	//        
{
	int i;
	for(i=0; i<7; i++)
	{
		if(c==op[i]) return OK;
	}
	return ERROR;
}

char Precede(char c1, char c2)		//              
{
	int i,j;
	for(i=0; i<7; i++)
		if(c1 == op[i]) break;
	for(j=0; j<7; j++)
		if(c2 == op[j]) break;
	return opcmp[i][j];
}

void Operate(char a1, char theta1, char b1)		//  
{
	int i;
	char outcome;
	for(i=0; i<4; i++)
		if(theta1 == op[i]) break;
	switch(i)
	{
		case 0: outcome = a1 + b1 - '0'; break;
		case 1: outcome = a1 - b1 + '0'; break;
		case 2: outcome = (a1-'0') * (b1-'0') + '0'; break;
		case 3: outcome = (a1-'0') / (b1-'0') + '0'; break;
	}
	Push(OPND, outcome);
}

int main()
{
	char c, e, x, theta;
	char a, b;
	
	if(!InitStack(OPTR) || !InitStack(OPND)) printf("Created Error!
");
	Push(OPTR, '=');
	c = getchar();
	while(c!='=' || GetTop(OPTR, e)!='=')
	{
		if(!In(c, op))
		{
			Push(OPND, c);
			c = getchar();
		}
		else
		{
			switch(Precede(GetTop(OPTR, e) , c))
			{
				case': Push(OPTR, c); c = getchar(); break;
				case'=': Pop(OPTR, x); c = getchar(); break;
				case'>': Pop(OPTR, theta); 
						Pop(OPND, b); Pop(OPND, a); 
						Operate(a, theta, b); break;
			}
		}
	}
	printf("%c", GetTop(OPND, e));
}