スタックの応用——四則演算(逆ポーランド式)

4221 ワード

データ構造

逆ポーランド式

プレフィックス式、中式、後式(逆ポーランド式)はいずれも四則演算の表現であり、四則演算式で値を求める.すなわち、数学式の求値(1)a−b＊c＋d:中式(Infix Notation)は、演算記号が2つの演算対象の中間にあるためである.(2)＋−a＊b c:プレフィクス表現(Prefix Notation)は、ポーランド式ともいい、演算子は演算対象の前にあり、ポーランド式とも呼ばれます.(3)a b c*-d+:サフィックス式(Suffix Notation)は、逆ポーランド式とも呼ばれ、演算子は演算対象の後ろにあり、逆ポーランド式とも呼ばれます.

接尾辞式の利点(1)は、接頭辞式よりも変換しやすく、一番左に数字があります.(2)括弧を使わず、演算順に演算子の優先度を決定します.(3)コンピュータの計算方式により適合する.計算機は左から右にサフィックス表現を読み取ることにより、出会った演算対象をスタックに押し込むことができ、演算子に出会うと2つの演算対象を弾いて計算を完了し、結果をスタックに押し込むことができます.最後にスタックに残ったのは計算結果です.

int Compute(char s[81])
{
	int *sval;	//     
	char *sop;	//     
	int valtop=-1;
	int optop=-1;
	int x1,x2;
	char op;
	sval=(int *)malloc(N*sizeof(int));
	sop=(char *)malloc(N*sizeof(char));
	sop[++optop]='@';
	int i=0;
	while(s[i]){		
		if(s[i]>='0'&&s[i]<='9')//       :  ，   ，   ，    
		{	
			int y=0;
			while('0'<=s[i]&&s[i]<='9')
			{			
				y=y*10+s[i]-'0';	//               
				i++;
			}
			
			sval[++valtop]=y;	//Y          
			
			i--;
		}
		else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')		//    
		{
			while(Level(s[i])<=Level(sop[optop]))		//                      
			{
				x1=sval[valtop--];
				x2=sval[valtop--];
				op=sop[optop--];
				sval[++valtop]=Cal(x1,x2,op);
			}
			sop[++optop]=s[i];
		}
		else if(s[i]=='(')
		{
			sop[++optop]='(';	
		}
		else if(s[i]==')'){
			while(sop[optop]!='('){
				x1=sval[valtop--];
				x2=sval[valtop--];
				op=sop[optop--];
				sval[++valtop]=Cal(x1,x2,op);
			}
			optop--;
		}
		
		i++;
	}
	while(optop)
	{
		x1=sval[valtop--];
		x2=sval[valtop--];
		op=sop[optop--];
		sval[++valtop]=Cal(x1,x2,op);
	}
	return sval[valtop];
}

演算子優先度判定

nt Level(char a)		//           
{
	switch(a){
		case'+':
		case'-':return 1;break;
		case'*':
		case'/':return 2;break;	
		case'@':return 0;break;
		
	}
}

計算する

int Cal(int x1,int x2,char op)
{
	switch(op){
		case'+':return x2+x1;
		case'-':return x2-x1;
		case'*':return x2*x1;
		case'/':return x2/x1;
	}
}

完全四則演算コード

#include
#include
#include
#define N 81
//  (1+2)*3+2-1        	 
int Level(char a);		//           
int Cal(int x1,int x2,char op);
int Compute(char s[81]);

int main(void)
{
	char s[81];
	int value;
	printf("          ：
");
	gets(s);
	value=Compute(s);
	printf("%s=%d
",s,value);
}

int Compute(char s[81])
{
	int *sval;	//     
	char *sop;	//     
	int valtop=-1;
	int optop=-1;
	int x1,x2;
	char op;
	sval=(int *)malloc(N*sizeof(int));
	sop=(char *)malloc(N*sizeof(char));
	sop[++optop]='@';
	int i=0;
	while(s[i]){		
		if(s[i]>='0'&&s[i]<='9')//       :  ，   ，   ，    
		{	
			int y=0;
			while('0'<=s[i]&&s[i]<='9')
			{			
				y=y*10+s[i]-'0';	//               
				i++;
			}
			
			sval[++valtop]=y;	//Y          
			
			i--;
		}
		else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')		//    
		{
			while(Level(s[i])<=Level(sop[optop]))		//                      
			{
				x1=sval[valtop--];
				x2=sval[valtop--];
				op=sop[optop--];
				sval[++valtop]=Cal(x1,x2,op);
			}
			sop[++optop]=s[i];
		}
		else if(s[i]=='(')
		{
			sop[++optop]='(';	
		}
		else if(s[i]==')'){
			while(sop[optop]!='('){
				x1=sval[valtop--];
				x2=sval[valtop--];
				op=sop[optop--];
				sval[++valtop]=Cal(x1,x2,op);
			}
			optop--;
		}
		
		i++;
	}
	while(optop)
	{
		x1=sval[valtop--];
		x2=sval[valtop--];
		op=sop[optop--];
		sval[++valtop]=Cal(x1,x2,op);
	}
	return sval[valtop];
}

int Level(char a)		//           
{
	switch(a){
		case'+':
		case'-':return 1;break;
		case'*':
		case'/':return 2;break;	
		case'@':return 0;break;
		
	}
} 
int Cal(int x1,int x2,char op)
{
	switch(op){
		case'+':return x2+x1;
		case'-':return x2-x1;
		case'*':return x2*x1;
		case'/':return x2/x1;
	}
}

テーブルのオートフィールドをリセットします.