데이터 구조 (역 폴란드 식 --- 스 택 으로 구현)

데이터 구조
창고.
스 택 이 라 고도 부 르 는데 이것 은 연산 이 제 한 된 선형 표 로 그 제한 은 표 의 한 끝 에 만 삽입 하고 삭제 하 는 연산 을 허용 하 는 것 이다.사람들 은 이 끝 을 스 택 지붕 이 라 고 부 르 고 스 택 지붕 의 첫 번 째 요 소 는 스 택 지붕 요소 라 고 부 르 며 상대 적 으로 다른 한 끝 을 스 택 바닥 이 라 고 부른다.스 택 에 새로운 요 소 를 삽입 하 는 것 을 스 택 에 들 어가 거나 스 택 에 들 어 가 는 것 이 라 고도 합 니 다. 이 요 소 를 스 택 꼭대기 요소 위 에 올 려 새로운 스 택 꼭대기 요소 로 만 드 는 것 입 니 다.한 스 택 에서 요 소 를 삭제 하 는 것 을 스 택 에서 나 오 거나 스 택 에서 나 오 는 것 이 라 고도 합 니 다. 스 택 꼭대기 요 소 를 삭제 하여 아래 의 인접 요 소 를 새로운 스 택 꼭대기 요소 로 만 듭 니 다.창고 의 실현:https://blog.csdn.net/wfea_lff/article/details/103343438
역 폴란드 식
역 폴란드 식 은 접미사 표현 식 이 라 고도 부 릅 니 다. 우리 가 평소에 쓰 는 표현 식 은 접미사 표현 식 입 니 다.
역 폴란드 식 작용
접미사 표현 식 은 인간 의 사고 구조 에 비해 비교적 간단 하고 컴퓨터 에 있어 서 중 서 표현 식 은 매우 복잡 한 구조 이다.상대 적 으로 역 폴란드 식 은 컴퓨터 로 볼 때 비교적 간단 하고 이해 하기 쉬 운 구조 다.컴퓨터 가 보편적으로 사용 하 는 메모리 구 조 는 스 택 구조 이기 때문에 선진 적 인 순서 예 를 실행 합 니 다. 접두사 표현 식: (1 + 2) 3 / 4 는 위의 접두사 표현 식 을 역 폴란드 식 접두사 표현 식 으로 바 꿉 니 다. 12 + 34 / 접두사 표현 식 의 연산 과정 을 처음부터 옮 겨 다 니 고 연산 자 를 만나면 연산 자 앞의 두 숫자 를 이 연산 자 를 조작 합 니 다.계산 결 과 를 계속 뒤로 옮 겨 다 니 며, 같은 이치 로 연산 자 를 만나면 이전의 조작 을 한다.
접미사 식 의 실현
전환 과정 은 스 택 의 선진 적 인 후 출 특성 을 이용 하여 1. 스 택 s1 두 개 를 만 들 고, s2 s1 은 연산 자 s2 를 저장 하여 중간 결 과 를 저장 합 니 다. 2. 접미사 식 문 자 를 규칙 에 따라 s1 과 s2 규칙 에 저장 합 니 다. 1) 숫자 를 만 났 을 때 s2 에 저장 합 니 다. 표현 식 연산 자 를 만 났 을 때, 이전에 s1 스 택 꼭대기 에 저장 한 연산 자 를 우선 순위 (1) 로 합 니 다.만약 에 연산 자가 스 택 꼭대기 의 연산 자 보다 우선 순위 가 낮 거나 같 으 면 스 택 꼭대기 의 연산 자 를 스 택 에서 나 와 s2 에 합 친 다음 에 현재 스 택 에서 나 온 s1 의 스 택 지붕 과 표현 식 연산 자의 우선 순 위 를 계속 비교 하여 상기 작업 을 계속 완성 합 니 다.표현 식 연산 자 보다 낮은 스 택 꼭대기 에 있 을 때 까지 표현 식 연산 자 를 s1 에 저장 하고 표현 식 의 다음 문자 (2) s1 에 데이터 요소 가 없 으 면 연산 자 를 스 택 s1 3 에 직접 넣 어 '(' 와 ')' 문 제 를 처리 합 니 다 (1) 만 났 다 면 '(', 스 택 s1 (2) 에 직접 들 어가 면 ')'s1 의 스 택 지붕 을 끊임없이 스 택 에 넣 고 s2 에 옮 겨 다 닐 때 까지' ('시 멈 추고' ('스 택 에서 버 리 기 (3)' ('와')'s2 에 들 어 갈 수 없습니다. 하나의 중간 양 에 해당 합 니 다. 3. 표현 식 이 끝 날 때 까지 2 안의 모든 과정 을 반복 합 니 다. 4. s2 의 스 택 지붕 을 스 택 에서 차례대로 나 와 s1 중 5. s1 의 스 택 지붕 을 순서대로 스 택 에서 나 와 출력 하면 접미사 표현 식 (역 폴란드 식) 을 얻 을 수 있 습 니 다.
코드 구현:

#include 
#include 
#include 

//----------------------    --------------------------

typedef char ElemType;

#define STACKSIZE 10

typedef struct Stack   //       
{
	ElemType  *data;
	ElemType  top;
	int stacksize;
}*StackPtr;

int Init_Stack(StackPtr stack)          //   
{
	if(stack == NULL)  exit(0);
	stack->data = (ElemType*)malloc(sizeof(ElemType)*STACKSIZE);
	stack->stacksize = STACKSIZE;
	stack->top = 0;
	return true;
}

int Push_Stack(StackPtr stack,ElemType val)      //  
{
	if(stack == NULL)  exit(0);
	stack->data[stack->top] = val;
	stack->top++;
	return true;
}

int Pop_Stack(StackPtr stack)          //  
{
	if(stack==NULL)  exit(0);
	stack->top--;
	return true;
}

int GetTop(StackPtr stack)          //    
{
	if(stack == NULL)  exit(0);
	return stack->data[stack->top-1];
}

int Empty_Stack(StackPtr stack)          //  
{
	if(stack == NULL)  exit(0);
	if(stack->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

static int Apply_Stack(StackPtr stack)             //    
{
	ElemType* p = (ElemType*)malloc(sizeof(ElemType)*stack->stacksize*2);
	if(p == NULL)  return false;
	for(int i=0;i<stack->top;i++)
	{
		p[i] = stack->data[i];
	}
	free(stack->data);
	stack->data = p;
	p = NULL;
	stack->stacksize*=2;
	return true;
}

static int Full_Stack(StackPtr stack)         //  
{
	if(stack->stacksize == stack->top&&stack->top != 0)
	{
		Apply_Stack(stack);
		return true;
	}
	else
	{
		return false;
	}
}

int Clear_Stack(StackPtr stack)            //  
{
	if(stack == NULL)  exit(0);
	stack->top = 0;
	return true;
}

int Destroy_Stack(StackPtr stack)          //  
{
	if(stack == NULL)  exit(0);
	free(stack->data);
	stack->data = NULL;
	stack->top = 0;
	stack->stacksize = 0;
	return true;
}

//------------------------------------------------------

//--------------------      ------------------------

int OperPre(char oper)         //     
{
	int tmp;
	switch(oper)
	{
	case '+':
	case '-':
		tmp = 1; break;
	case '*':
	case '/':
		tmp = 2;break;
	default:
		tmp = 3;
	}
	return tmp;
}

void RPNotation(char *buff)         //      
{
	Stack s1,s2;                    //      s1，s2
	Init_Stack(&s1);                //    
	Init_Stack(&s2);
	
	while(1)                        //     
	{
		if(isdigit(*buff))           //     s2
		{
			Push_Stack(&s2,*buff);
		}

		if(!isdigit(*buff))      
		{
			while(OperPre(*buff)<=OperPre(GetTop(&s1)))
			{
				if(s1.top == 0) break;          // s1        
				if(GetTop(&s1)=='(')  break;    //  ‘（’  
				Push_Stack(&s2,GetTop(&s1));    // s1     s2
				Pop_Stack(&s1);                 //s1  
			}

			if(*buff != ')')                    //   ‘）’      if      
			{
				Push_Stack(&s1,*buff);
			}
		}

		if(*buff == ')')                   //  ‘（’，‘）’  
		{
			while(GetTop(&s1) != '(')      // ‘（’        s2 
			{
				Push_Stack(&s2,GetTop(&s1));
				Pop_Stack(&s1);
			}
			Pop_Stack(&s1);	                //       ， ‘（’  
		}

		buff++;
		if(*buff == '
') break;            //    
	}
	
	while(s2.top != 0)                     // （ ）s2  （ ）s1
	{
		Push_Stack(&s1,GetTop(&s2));
		Pop_Stack(&s2);
	}
	printf("     ：
");
	while(s1.top != 0)                     //  （ ）s1  
	{
		printf("%c",GetTop(&s1));
		Pop_Stack(&s1);
	}
	printf("
");
}

int main()
{
	char buff[128];
	printf("     ：
");
	fgets(buff,127,stdin);
	RPNotation(buff);
	return 0;
}