데이터 구조 --- 스 택 운용 의 작은 예

3873 단어
문제: 10 진 정 수 를 입력 하고 16 진 을 출력 합 니 다.
    16 진수 로 전환 하려 면 먼저 기수 16 을 나 누고 얻 은 모델 을 전환 후의 가장 낮은 숫자 로 해 야 한다. 얻 은 업 체 는 기수 16 을 나 눈 다음 에 모델 을 얻 으 면 다음 자리 의 수 이다.......................................................이렇게 하면 우 리 는 스 택 의 특성 을 이용 하여 먼저 나 와 서 모델 을 저장 하고 마지막 에 모두 인쇄 할 것 이 라 고 생각 하기 쉽다.다음 사용 순서 스 택 구현:
#include <stdio.h>
#include <stdlib.h>
#define N 20
typedef int datatype;
typedef struct stack{
datatype data[N];
int top;
}sqstack;

int main()
{
	int n;
	scanf("%d",&n);
	sqstack *s;
	s = (sqstack *)malloc(sizeof(sqstack));
	s -> top =-1;
	while(n>0)
	{
		s -> data[++s->top]=n%16;
		n= n/16;
	}
	while(-1 !=s->top)
	{
	  if(s -> data[s ->top] > 9)
		  printf("%c",s -> data[s -> top]-10 + 'a');
	  else
		  printf("%d",s-> data[s -> top]);
	 s -> top --;
	}
	puts("");
	return 0;
}

문제: 표현 식 의 계산 결 과 를 구하 십시오.
      먼저 두 개의 스 택 을 만들어 야 합 니 다. 연산 자 스 택 과 연산 자 스 택 을 만 들 려 면 연산 자의 우선 순 위 를 고려 해 야 합 니 다.
     규칙: 1. 왼쪽 에서 오른쪽으로 스 캔 표현 식 입 니 다. 조작 수 를 만나면 스 택 에 들 어 갑 니 다.
                2. 연산 자 를 만 났 을 때 그의 우선 순위 가 스 택 꼭대기 요소 의 우선 순위 보다 높 으 면 스 택 에 들 어 갑 니 다.반대로 창고 꼭대기 원소 와 조작 수의 창고 꼭대기 원 소 를 꺼 내 계산 하고 결 과 를 조작 수 창고 에 저장 한 다음 에 계속 합 니 다.
                3. 왼쪽 괄호 는 일률적으로 연산 자 창고 에 들 어가 고 오른쪽 괄호 는 일률적으로 연산 자 창고 에 들 어가 지 않 습 니 다. 연산 자 창고 꼭대기 요소 와 연산 자 창고 꼭대기 의 두 조작 수 를 꺼 내 계산 하고 결 과 를 조작 수 창고 에 눌 러 서 왼쪽 괄호 를 꺼 낼 때 까지 알 수 있 습 니 다.다음 규칙 에 따라 코드 구현:
       
#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"

#define  N  32

int Pri(char op)
{
	switch ( op )
	{
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 2;
	}

	return 0;
}

int Compute(int left, int right, char op)
{
	switch ( op )
	{
	case '+':
		return left + right;
	case '-':
		return left - right;
	case '*':
		return left * right;
	case '/':
		return left / right;
	}

	return 0;
}

void del_op(linkstack *operand, linkstack *operator, char op)
{
	int left, right;
	char sign;

	while (!EmptyLinkstack(operator) && Pri(op) <= Pri(GetTop(operator)))
	{
		right = PopLinkstack(operand);
		left = PopLinkstack(operand);
		sign = PopLinkstack(operator);
		PushLinkstack(operand, Compute(left, right, sign));
	}
	PushLinkstack(operator, op);

	return;
}

int main()
{
	char str[N], *p = str, sign;
	int sum = 0, left, right;
	linkstack *operand, *operator;

	operand = CreateLinkstack();
	operator = CreateLinkstack();

	scanf("%s", str);
	while (*p != '\0')
	{
		if ('0' <= *p && *p <= '9')
		{
			while ('0' <= *p && *p <= '9')
			{
				sum = 10*sum + *p - '0';
				p++;
			}
			PushLinkstack(operand, sum);
			sum = 0;
		}
		else
		{
			del_op(operand, operator, *p);
			p++;
		}
	}

	while ( ! EmptyLinkstack(operator) )
	{
		right = PopLinkstack(operand);
		left = PopLinkstack(operand);
		sign = PopLinkstack(operator);
		PushLinkstack(operand, Compute(left, right, sign));
	}
	printf("%s = %d
", str, GetTop(operand)); return 0; }

좋은 웹페이지 즐겨찾기