biaodashi.cpp

自己写的数据结构代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>

#define OK 1
#define ERROR -1
typedef char SElemType;

typedef char Status;
#define STACK_INIT_SIZE 100000
#define STACKINCREMENT 2

struct SqStack
{
	SElemType *base;
	SElemType *top;
	int stacksize;
};

struct SqStack1
{
	int *base;
	int *top;
	int stacksize;
};

SqStack OPTR;
SqStack1 OPND;

char Precede(char c1,char c2)
{
	if(c1=='+' || c1=='-')
	{
		if(c2=='+' || c2=='-' || c2==')' || c2=='=')  return '>';
		else										  return '<';
	}
	else if(c1=='*' || c1=='/')
	{
		if(c2=='(') return '<';
		else return '>';
	}
	else if(c1=='(')
	{
		if(c2==')')  return '=';
		else         return '<';
	}
	else if(c1==')')  return '>';
	else if(c1=='=')  
	{
		if(c2=='=') return '=';
		else        return '<';
	}
	else return '\0';
}

int In(char c)
{
	if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='=')
		return 1;
	else return 0;
}

int Operrate(int m,char b,int n)
{
	switch(b)
	{
	case '+':return m+n;
	case '-':return m-n;
	case '*':return m*n;
	case '/':return m/n;
	}
	return 0;
}

//操作数

int InitStack1(SqStack1 &S)
{
	S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}

int Push1(SqStack1 &S,int e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
		
		S.top=S.base+S.stacksize;
		S.stacksize=S.stacksize+STACKINCREMENT;
	}
	*S.top++=e;	
	return OK;
}

int Pop1(SqStack1 &S,int &e)
{
	if(S.top==S.base) return ERROR;	
	e=* --S.top;
	return OK;
}

int GetTop1(SqStack1 S)
{
	if(S.top==S.base) return ERROR;
	return *(S.top-1);
}

//算符

int InitStack(SqStack &S)
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}

int Push(SqStack &S,SElemType e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		
		S.top=S.base+S.stacksize;
		S.stacksize=S.stacksize+STACKINCREMENT;
	}
	*S.top++=e;	
	return OK;
}

int Pop(SqStack &S,SElemType &e)
{
	if(S.top==S.base) return ERROR;	
	e=* --S.top;
	return OK;
}

Status GetTop(SqStack S)
{
	if(S.top==S.base) return ERROR;
	return *(S.top-1);
}

int Calculate()
{
	char c,theta,p;
	int a,b,i=0,ans,x;
	InitStack(OPTR);
	Push(OPTR,'=');
	InitStack1(OPND);
	c=getchar();
	while(c!='=' || GetTop(OPTR)!='=')
	{
		if(!In(c) && c>='0' && c<='9')
		{
			Push1(OPND,c-'0');
			c=getchar();
			
			while(c>='0' && c<='9')
			{
				Pop1(OPND,x);
				Push1(OPND,x*10+c-'0');
				c=getchar();
			}
		}
		else if(In(c))
		{
			switch(Precede(GetTop(OPTR),c))
			{
			case '<':
				Push(OPTR,c);
				c=getchar();
				break;
			case '=':
				Pop(OPTR,p);
				c=getchar();
				break;
			case '>':
				Pop(OPTR,theta);
				Pop1(OPND,b);
				Pop1(OPND,a);
				
				ans=Operrate(a,theta,b);
				Push1(OPND,ans);
				break;
			}
		}
		else
		{
			c=getchar();
		}
	}
	return GetTop1(OPND);
}

int main()
{
	int ans;
	ans=Calculate();
	printf("%d\n",ans);
	return 0;
}