数据结构：利用栈的操作实现表达式求值

#include "EvaluateExpression.h"
 
char OP[]={'+','-','*','/','(',')','#'};
OPND_Stack OPND;//定义操作数栈变量 
OPTR_Stack OPTR;//定义运算符栈变量 
char x;//运算符出栈时起缓冲作用
int main()
{
	char *str=new char[STACK_INIT_SIZE],theta;//存放表达式
	OPND_Type t=0,a,b;	 
	printf("若你要输入负数如-4则就这样输入(0-4)\n");
	printf("请输入表达式(以#结束)：");
	Init_OPTR_Stack(OPTR); Push_OPTR(OPTR,'#');
	Init_OPND_Stack(OPND); scanf("%s",str);	
	while(*str!='#'||GetTop_OPTR(OPTR)!='#')
	{
		if(!In(*str,OP))
		{
			t=0;
			while(!In(*str,OP))
			{
				if(*str<'0'||*str>'9')
				{
					printf("表达式有非法输入！\n");
					exit(0);
				}
				t*=10;
				t=*str-'0'+t;
				str++;
			}
			Push_OPND(OPND,t);
		}
		else
		{		
			switch(Precede(GetTop_OPTR(OPTR),*str))
			{
				case '<': Push_OPTR(OPTR,*str); str++; break;
				case '=': Pop_OPTR(OPTR,x);   str++; break;
				case '>': Pop_OPTR(OPTR,theta); Pop_OPND(OPND,b); Pop_OPND(OPND,a); Push_OPND(OPND,Operate(a,theta,b)); break;
			}
		}
	}
	printf("结果是: %d\n",GetTop_OPND(OPND));
	return 0;
}

/**************************************
  Name: 表达式求值的实现 
  Author: mail@chenzhiwei.cn
  Date: 2008/12/25
  Copyright http://chenzhiwei.net
  PS:还有些功能没有实现，如负数输入问题，还有运算符连续出现问题
**************************************/
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 100
typedef  char OPTR_Type;
typedef  int  OPND_Type;
#define overflow -2
typedef int  Status;
#define OK 1
#define ERROR 0 
typedef struct{
	OPND_Type *base;
	OPND_Type *top;
	int       stacksize;
}OPND_Stack;//定义操作数栈的结构；
typedef struct{
	OPTR_Type *base;
	OPTR_Type *top;
	int       stacksize;
}OPTR_Stack;//定义运算符栈的结构；
//-------------下为函数声明,其实作为头文件不用声明也行-----------------//
//1.初始化空栈；
Status Init_OPND_Stack(OPND_Stack &S);
Status Init_OPTR_Stack(OPTR_Stack &S);
//2.进栈操作；
Status Push_OPTR(OPTR_Stack &S,OPTR_Type e);
Status Push_OPND(OPND_Stack &S,OPND_Type e);
//3.出栈操作；
Status Pop_OPTR(OPTR_Stack &S,OPTR_Type &e);
Status Pop_OPND(OPND_Stack &S,OPND_Type &e);
//4.返回栈顶元素
OPTR_Type GetTop_OPTR(OPTR_Stack S);
OPND_Type GetTop_OPND(OPND_Stack S);
/*以下是一些基本操作实现；*/
 
Status Init_OPTR_Stack(OPTR_Stack &S)
{
    S.top=(OPTR_Type *)malloc(STACK_INIT_SIZE*sizeof(OPTR_Type));
	S.base=S.top;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}//初始化空栈；
Status Init_OPND_Stack(OPND_Stack &S)
{
    S.top=(OPND_Type *)malloc(STACK_INIT_SIZE*sizeof(OPND_Type));
	S.base=S.top;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}//初始化空栈；
 
Status Push_OPTR(OPTR_Stack &S,OPTR_Type e)
{
    if(S.top-S.base>=S.stacksize)
	{
		printf("内存超限！\n");
		exit(overflow);
	}
	*S.top=e;
	S.top++;
	return OK;
}//进栈操作；
Status Push_OPND(OPND_Stack &S,OPND_Type e)
{
    if(S.top-S.base>=S.stacksize)
	{
		printf("内存超限！\n");
		exit(overflow);
	}
	*S.top=e;
	S.top++;
	return OK;
}//进栈操作；
 
Status Pop_OPTR(OPTR_Stack &S,OPTR_Type &e)
{
    if(S.top==S.base) return ERROR;
	e=*--S.top;
	return OK;
}//出栈操作；
Status Pop_OPND(OPND_Stack &S,OPND_Type &e)
{
    if(S.top==S.base) return ERROR;
	e=*--S.top;
	return OK;
}//出栈操作；
 
OPTR_Type GetTop_OPTR(OPTR_Stack S)
{
	if(S.top==S.base) return '0';
	return *(S.top-1);
}
OPND_Type GetTop_OPND(OPND_Stack S)
{
	if(S.top==S.base) return '0';
	return *(S.top-1);
}
 
Status In(OPTR_Type c,OPTR_Type *p)
{
	while(*p!='\0')
	{
		if(*p==c)
		{
			return 1;
		}
		p++;
	}
	return 0;
}
 
OPTR_Type Precede(char prior,char next)
{
	if(prior=='+'||prior=='-')
	{
		if(next=='*'||next=='('||next=='/')
		   return '<';
		else return '>';
	}
	else if(prior=='*'||prior=='/')
	{
		if(next=='(')
		   return '<';
		else return '>';
	}
	else if(prior=='(')
	{
		if(next=='#')
		   exit(1);
		else if(next==')')
			return '=';
		else return '<';
	}
	else if(prior==')')
	{
		if(next=='(')
		   exit(1);
		else return '>';
	}
	else if(prior=='#') 
	{
		if(next=='#')
			return '=';
		else if(next==')')
			exit(1);
		else return '<';
	}
	else exit(1);
}
 
OPND_Type Operate(OPND_Type a,char c,OPND_Type b)
{
	OPND_Type temp;
	switch(c)
	{
		case '+':temp=a+b;break;
		case '-':temp=a-b;break;
		case '*':temp=a*b;break;
		case '/':temp=a/b;break;
	}
	return temp;
}