C 언어: 접미사 표현 식 을 접미사 표현 식 으로 변환 하고 결 과 를 계산 합 니 다.

#include
#include
#include
#include
#define ElemType int
using namespace std;
typedef struct Stack{
	ElemType * base;
	ElemType * top;
	int stacksize;
}SqStack;
int In_Op(char a);		//         
int Pop(SqStack * S,ElemType e);	//   
int GetTop(SqStack * S,ElemType e);	//       
int CreateStack(SqStack * S);		//     
int Push(SqStack * S,ElemType e);	//   
void CreateExpression(char * str);	//        
char * TransmitExpression(char * a);//               
int Is_Pop(char x,char y);			//               
ElemType EvaluateExpression(char *a);//            
ElemType Theta(int l,char m,int r);	//       
int main(){
	char str[30];
	char s_str[30];
	CreateExpression(str);
	strcpy(s_str,TransmitExpression(str));
	cout<base = (ElemType *)malloc(sizeof(SqStack)*10);
	if(!S->base) exit(-1);
	S->top = S->base;
	S->stacksize = 10;
	return 1;
}
//       
ElemType GetTop(SqStack * S){
	if(S->top == S->base)
		return 0;
	return *(S->top-1);
}
//   
int Push(SqStack * S,ElemType e){
	if((S->top-S->base)>=S->stacksize){
		S->base = (ElemType *)realloc(S->base,(S->stacksize+5)*sizeof(SqStack));
		if(!S->base)
			exit(-1);
		S->top = S->base + S->stacksize;
		S->stacksize +=5;
	}
	*S->top=e;
	S->top++;
	return 1;
}
//   
int Pop(SqStack * S,ElemType * e){
	if(S->top==S->base)
		return 0;
	*e = *(--S->top);
	return 1;
}
//        
void CreateExpression(char * str){
	gets(str);
}
//         
int In_Op(char a){
	switch(a){
		case '+' : return 1;
		case '-' : return 1;
		case '*' : return 1;
		case '/' : return 1;
		case '(' : return 1;
		case ')' : return 1;
		case '#' : return 1;
		default:return 0;
	}
}
/*
    :               
	  :     
     :      
*/
char * TransmitExpression(char * a){
	int i,j=0;
	char b[20]={0};
	SqStack OPTR;
	ElemType e;
	CreateStack(&OPTR);
	Push(&OPTR,'#'); 
	for(i=0;a[i];i++){
		if(!In_Op(a[i])){
			b[j++]=a[i];//           b 
		}else{
			if(GetTop(&OPTR)=='#'){
				Push(&OPTR,a[i]);	//        ,    。 
				continue; 
			}
			if(Is_Pop(GetTop(&OPTR),a[i])){ //                      
				if(a[i]==')'){	//        
					while(GetTop(&OPTR)!='('){
						Pop(&OPTR,&e);	//               b 
						b[j++]=(char)e;
					}
					Pop(&OPTR,&e); //       
				}else{ 			//         
					while(GetTop(&OPTR)!='#'){//           
						Pop(&OPTR,&e);
						b[j++]=(char)e;
					}
					Push(&OPTR,a[i]);//        
				}
			}else{
				Push(&OPTR,a[i]); //             ，
								//          
			}
		}
	}
	//          ，           
	while(GetTop(&OPTR)!='#'){
		Pop(&OPTR,&e);
		b[j++]=(char)e;
	}
	//       ，     
	char * result = (char *)malloc(sizeof(char)*20);
	strcpy(result,b);// b                
	return result;
}
//              ，                
/*
 	     
      + - * / ( )
  	+  1 1 0 0 0 1
 	-  1 1 0 0 0 1
 	*  1 1 0 0 0 1
 	/  1 1 1 1 0 1
 	(  0 0 0 0 0 0
 	)  1 1 1 1 1 1
*/ 
int Is_Pop(char x,char y){
	if(x=='(')
		return 0;
	if(y=='('&&x!=')')
		return 0;
	if(y=='*'||y=='/'){
		if(x=='+'||x=='-')
			return 0;
	}
	return 1;
}
//            
ElemType EvaluateExpression(char *a){
	int i;
	ElemType l,r,e;
	SqStack OPND;
	CreateStack(&OPND);
	for(i=0;a[i];i++){
		if(!In_Op(a[i])){
			Push(&OPND,int(a[i]-48));
		}else{
			Pop(&OPND,&r);
			Pop(&OPND,&l);
			Push(&OPND,Theta(l,a[i],r));
		}
	}
	return GetTop(&OPND);
}
//       
ElemType Theta(int l,char m,int r){
	switch(m){
		case'+': return l+r;
		case'-': return 1-r;
		case'*': return l*r;
		case'/': return l-r;
	}	
}