스 택 에서 사용 할 접미사 표현 식 접미사 표현 식 (C 언어)

나 는 인터넷 에서 몇 가지 사 고 를 뽑 았 다. 여기 서 의 사 고 는 우선 순위 의 비교 에 있어 대체적으로 같 고 방법 이 다양 하 다. 여 기 는 더 이상 상세 하 게 설명 하지 않 는 다. - - - - - - - - -1. 숫자 직접 출력 2. 왼쪽 괄호 를 만 나 바로 스 택 에 들 어 갑 니 다. 오른쪽 괄호 를 만 나 스 택 의 왼쪽 괄호 를 만 나 스 택 에 들 어간 연산 자 는 모두 스 택 에서 출력 합 니 다. 그리고 왼쪽 괄호 는 스 택 에서 나 오지 만 출력 하지 않 습 니 다.3. 곱 하기 번호 와 나 누 기 번 호 를 만 나 서 스 택 에 직접 들 어 갑 니 다. 우선 순위 가 더 낮은 연산 자 를 만 날 때 까지 순서대로 스 택 에 들 어 갑 니 다.4. 추가 번호 와 마이너스 번 호 를 만 났 을 때 스 택 이 비어 있 으 면 바로 스 택 에 들 어 갑 니 다. 그렇지 않 으 면 스 택 에 있 는 우선 순위 가 높 은 연산 자 를 순서대로 스 택 (주의: 추가 번호 와 감 호 는 같은 우선 순위 에 속 하기 때문에 스 택 이 비어 있 거나 왼쪽 괄호 를 만 날 때 까지 스 택 을 중단 합 니 다.(왼쪽 괄호 가 오른쪽 괄호 와 일치 해 야 팝 업 되 기 때 문 입 니 다.)5. 가 져 온 후 스 택 에 남 은 연산 기 호 를 순서대로 스 택 으로 출력 합 니 다.
- - - - - - - - - - - - 1. 먼저 우 리 는 집합 sList 를 만들어 예 중의 데이터 와 조작 기 호 를 저장 하고 스 택 opStack 을 만들어 중간 에 있 는 조작 기 호 를 저장 하 며 dList 를 집합 하여 마지막 전환 결 과 를 저장 해 야 합 니 다.2. sList 에서 하나의 요소 A 를 추출 한 다음 에 다음 과 같은 판단 을 한다. (1) A 가 숫자 라면 dList (2) A 가 연산 자 라면 opStack 스 택 꼭대기 의 요소 와 연산 우선 순위 비교 (2 - 1) A 의 우선 순위 가 스 택 꼭대기 연산 자 우선 순위 보다 높 으 면 A 를 스 택 에 넣 는 opStack (2 - 2) A 의 우선 순위 가 스 택 꼭대기 연산 자의 우선 순위 보다 낮 거나 같 으 면그러면 스 택 꼭대기 의 요 소 를 dList 에 저장 하고 스 택 꼭대기 의 연산 자 우선 순위 가 현재 연산 자 (또는 괄호 를 만 났 을 때) 보다 낮 을 때 까지 이 절 차 를 반복 한 다음 에 A 가 스 택 에 들 어 갑 니 다. 3. A 가 왼쪽 괄호 라면 "(" 직접 스 택 에 들 어 갑 니 다. 오른쪽 괄호 라면 ")"왼쪽 괄호 가 나 올 때 까지 opStack 의 연산 자 를 꺼 내 dList 에 저장 합 니 다. 왼쪽 괄호 가 나 올 때 까지 왼쪽 괄호 는 dList 에 저장 되 지 않 습 니 다. 오른쪽 괄호 를 만 날 때 까지 왼쪽 괄호 는 영원히 꺼 지지 않 습 니 다. 4. 표현 식 해석 이 끝 날 때 까지 상기 절 차 를 계속 반복 합 니 다.의 코드:

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

#define STACK_INIT_SIZE 20
#define STACK_DILA_SIZE 10

typedef char elemtype;

typedef struct
{
	elemtype * base;
	elemtype * top;
	int stacksize;
}sqstack;

void initstack(sqstack*s)
{
	s->base = (elemtype*)malloc(STACK_INIT_SIZE * sizeof(elemtype));
	if (!s->base)
	{
		exit(0);
	}
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
}

void push(sqstack*s, elemtype x)
{
	if (s->top - s->base >= s->stacksize)
	{
		s->base = (elemtype*)realloc(s->base, (STACK_DILA_SIZE + STACK_INIT_SIZE) * sizeof(elemtype));
		if (!s->base)
		{
			exit(0);
		}
		s->top = s->base + STACK_INIT_SIZE;
		s->stacksize = +STACK_DILA_SIZE;
	}
	*(s->top) = x;
	s->top++;
}

void pop(sqstack*s, elemtype*x)
{
	if (s->base == s->top)
	{
		return;
	}
	s->top--;
	*x = *s->top;
}

int stacklen(sqstack*s)
{
	return (s->top - s->base);
}

void clearstack(sqstack*s)
{
	s->top = s->base;
}

void destroystack(sqstack*s)
{
	s->top = NULL; 
	s->base = NULL;
	s->stacksize = 0;
	free(s->base);
}
int main()
{
	sqstack*s = (sqstack*)malloc(sizeof(sqstack));
	initstack(s);
	char c, x;
	scanf_s("%c", &c, sizeof(c));
	while (c != '#')
	{
		while (c >= '0'&&c <= '9')
		{
			printf("%c", c);
			scanf_s("%c", &c, sizeof(c));
			if (c < '0'||c > '9')
			{
				printf(" ");
			}
		}		
		 if (')' == c)
		{
			pop(s, &x);
			while ('(' != x)
			{
				printf("%c", x);
				pop(s, &x);
			}
		}
		else if ('+' == c || '-' == c)
		{
			if (!stacklen(s))
			{
				push(s, c);
			}
			else
			{
				do
				{
					pop(s, &x);
					if ('(' == x)
					{
						push(s, x);
					}
					else
					{
						printf("%c", x);
					}
				} while (stacklen(s) && '(' != x);
				push(s, c);
			}
		}
		else if ('*' == c || '/' == c || '(' == c)
		{
			push(s, c);
		}
		else if ('#' == c)
		{
			break;
		}
		scanf_s("%c", &c, sizeof(c));
	}
	while (stacklen(s))
	{
		pop(s, &x);
		printf("%c", x);
	}
	return 0;
}