창고 로 사 칙 연산 문 제 를 해결 하 다

이 글 의 해결 방법 은 에서 스 택 에 관 한 응용 소 개 를 참고 하 였 다.
주의해 야 할 것 은 책 에서 접미사 표현 식 접미사 전환 에 관 한 설명 이 명확 하지 않다 는 것 이다.본인 도 이곳 에서 약간의 시간 을 들 여 잘못된 원인 을 퇴고 했 고, 인터넷 에서 도 이 글 을 찾 아 냈 으 며, 접두사 가 접 두 사 를 바 꾸 는 규칙 을 비교적 잘 소개 하 였 다.
원리:
컴퓨터 로 사 칙 연산 을 풀 면 스 택 을 사용 할 수 있다.스 택 의 '선진 후 출' 특성 때문에 접미사 표현 식 을 통 해 네 가지 연산 식 의 결 과 를 계산 할 수 있 습 니 다.접미사 표현 식 의 전환 도 스 택 을 사용 하여 접미사 표현 식 을 조작 하여 전환 할 수 있 습 니 다.뚜렷하게 접미사 표현 식 - 접미사 표현 식, 접미사 표현 식 - 식 으로 결 과 를 얻 을 수 있 습 니 다.창고 까지 사용 해 야 합 니 다.그래서 인 코딩 실현 에서 우 리 는 이 두 과정 을 실현 하 는 함수 (infix to suffix (), suffix to result () 에 중심 을 두 었 다.
주의:
테스트 데이터

각 수 는 한 자리 에 만 달 하 는 수 일 수도 있 고 10 자리 이상 에 달 할 수도 있다

.

음수 나 양수 (음 수 는 양쪽 에 괄호 를 추가 해 야 함)

괄호 안에 여러 개의 괄호 가 존재 할 수 있 습 니 다. 예: (2 + 3) + (4 + 5) + (6 + 7) + 8)

이루어지다

각 연산 자 를 저장 하 는 전역 table 의 우선 순 위 를 정의 합 니 다. + -등 우선 순위, * / 등 우선 순위, () 우선 순위 가 존재 하지 않 습 니 다 (여 기 는 주로 코드 구현 을 위해 우선 순위 취소)

priority 변 수 를 설정 하여 스 택 상단 요 소 를 저장 하 는 우선 순 위 를 설정 합 니 다. 이 는 접미사 가 접 두 사 를 돌 릴 때 사용 되 고 매번 스 택 에서 스 택 을 나 온 후에 새로운 스 택 상단 요 소 를 우선 순위

로 기록 해 야 합 니 다.

접미사 접미사 전환 함수 에는 주로 이 몇 부분 이 포함 되 어 있 습 니 다. 1. 숫자 를 만 나 직접 출력 한 다음 contine 2. 왼쪽 괄호 를 눌 러 서 계속 3. 오른쪽 괄호 는 스 택 에 있 는 왼쪽 괄호 이상 의 모든 연산 자 를 팝 업 한 다음 contine 4. 연산 자 라면 우선 순위 가 스 택 꼭대기 요소 보다 작 거나 같 는 지 판단 합 니 다. 만약 에 왼쪽 괄호 앞 이나 우선 순위 가 스 택 요소 보다 크 거나 같은 스 택 에서 요 소 를 스 택 에서 나 옵 니 다.만약 그렇지 않다 면, 정상적으로 창 고 를 누 르 고, 정상적으로 창 고 를 누 르 는 과정 에서 마이너스 여 부 를 판단 해 야 한다. 5. 접미사 표현 식 을 옮 겨 다 니 며 스 택 에 존재 하 는 모든 요 소 를 스 택 에서 꺼 냅 니 다

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MAXSIZE = 100;
//      
typedef struct 
{
	int    data[MAXSIZE];
	int    top;
} Stack;

int    table[] = {0,0,2,1,0,1,0,2};//         

//    ：              
//    ：
//sta：               
//infix：           
//suffix：            
//length：           
void infix_to_suffix(Stack *sta, char *infix, int *suffix, int *length);

//    ：               
//    ：
//sta：               
//suffix：            
//length：           
int  suffix_to_result(Stack *sta, int *suffix, int length);
void init(Stack *sta);//      

int main()
{
	//                 
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	Stack     sta;
	int       length;
	int       result;         //            
	int       sstr[MAXSIZE];  //       
	char      istr[MAXSIZE];  //       

	printf("     + - * /        
（              ）
");
	scanf("%s", istr);

	init(&sta); //       
	infix_to_suffix(&sta, istr, sstr, &length);
	init(&sta); //         
	result = suffix_to_result(&sta, sstr, length);

	printf("%d
", result);
//	fclose(stdin);
//	fclose(stdout);
	return    0;
}


void infix_to_suffix(Stack *sta, char *infix, int *suffix, int *length)
{
	int    i;				//    
	int    b = 0;			//                
	int    j = 0;			//suffix     
	int    priority = 0;	//          

	//for           i++，                 suffix  i++
	for (i = 0; i < strlen(infix); )
	{
		//       ，    suffix ,  continue
		if (infix[i] >= '0' && infix[i] <= '9')
		{
			b = 0;		//            ！

			while (infix[i] >= '0' && infix[i] <= '9')
			{
				b = b * 10 + (infix[i] - '0');
				i++;
			}
			suffix[j] = b;
			j++;
			continue;
		}

		//        ，                 ,  continue
		if (infix[i] == 41)
		{
			while (sta->data[sta->top] != 40)
			{
				suffix[j] = sta->data[sta->top];
				sta->data[sta->top] = 0;
				sta->top--;
				j++;
			}
			sta->data[sta->top] = 0;
			sta->top--;
			//     ，                
			priority = table[sta->data[sta->top] % 10];
			i++;
			continue;
		}

		//        ，    
		if (infix[i] == 40)
		{
			sta->top++;
			sta->data[sta->top] = infix[i];
			//     ，                
			priority = table[sta->data[sta->top] % 10];
			i++;
			continue;
		}

		//          ，   
		if (infix[i] >= 42 && infix[i] <= 47)
		{
			//                        
			//       ，            ，         
			if (priority >= table[infix[i] % 10])
			{
				while (priority >= table[infix[i] % 10] && sta->data[sta->top] != 40)
				{
					suffix[j] = sta->data[sta->top];
					sta->data[sta->top] = 0;
					sta->top--;
					//        ，                    
					priority = table[sta->data[sta->top] % 10];
					j++;
				}
				sta->top++;
				sta->data[sta->top] = infix[i];
				//     ，                
				priority = table[sta->data[sta->top] % 10];
				i++;
			}
			else 
			{
				//           
				if (infix[i] == 45 && sta->data[sta->top] == 40)
				{
					b = 0;
					while (infix[i+1] >= '0' && infix[i+1] <= '9')
					{
						b = b * 10 + (infix[i+1] - '0');
						i++;
					}
					suffix[j] = b * -1;
					sta->data[sta->top] = 0;
					sta->top--;
					j++;
					i += 2;
					priority = table[sta->data[sta->top] % 10];
					continue;
				}
				sta->top++;
				sta->data[sta->top] = infix[i];
				//     ，                
				priority = table[sta->data[sta->top] % 10];
				
				i++;
			}

		}
	}
	//             
	while (sta->top != -1)
	{
		suffix[j] = sta->data[sta->top];
		sta->top--;
		j++;
	}
	*length = j;
}


int suffix_to_result(Stack *sta, int *suffix, int length)
{
	int    i;
	int    j;
	int    result = 0;

	for (i = 0; i < length; i++)
	{
		//         ，       ，               ，      
		switch (suffix[i])
		{
		case 42:
			result = sta->data[sta->top - 1] * sta->data[sta->top];
			sta->top -= 1;
			sta->data[sta->top] = result;
			break;
		case 43:
			result = sta->data[sta->top - 1] + sta->data[sta->top];
			sta->top -= 1;
			sta->data[sta->top] = result;
			break;
		case 45:
			result = sta->data[sta->top - 1] - sta->data[sta->top];
			sta->top -= 1;
			sta->data[sta->top] = result;
			break;
		case 47:
			result = sta->data[sta->top - 1] / sta->data[sta->top];
			sta->top -= 1;
			sta->data[sta->top] = result;
			break;
		default:
			sta->top++;
			sta->data[sta->top] = suffix[i];
			break;
		}
	}
	return   result;
}

//      
void init(Stack *sta)
{
	int     i;
	for (i = 0; i < MAXSIZE; i++)
	{
		sta->data[i] = 0;
	}
	sta->top = -1;
}