算法表达式求值.cpp

#include
#include
#include
#include 
#define MaxSize 100
//声明运算符栈类型 
typedef struct
{
	char data[MaxSize];
	int top;
}SqStack1;
//声明操作数栈类型 
typedef struct
{
	double data[MaxSize];
	int top;
}SqStack2;
//初始化运算符栈 
void InitStack1（SqStack1 *&s）
{
	s=（SqStack1 *）malloc（sizeof（SqStack1））;
	s->top=-1;
}
//初始化操作数栈 
void InitStack2（SqStack2 *&s）
{
	s=（SqStack2 *）malloc（sizeof（SqStack2））;
	s->top=-1;
}
//销毁运算符栈 
void DestroyStack1（SqStack1 *&s）
{
	free（s）;
}
//销毁操作数栈 
void DestroyStack2（SqStack2 *&s）
{
	free（s）;
}
//运算符进栈 
bool Push1（SqStack1 *&schar e）
{
	if（s->top==MaxSize-1）
	{
		return false;
	}
	s->top++;
	s->data[s->top]=e;
	return true;
}
//操作数进栈 
bool Push2（SqStack2 *&sdouble e）
{
	if（s->top==MaxSize-1）
	{
		return false;
	}
	s->top++;
	s->data[s->top]=e;
	return true;
}
//运算符出栈 
bool Pop1（SqStack1 *&schar &e）
{
	if（s->top==-1）
	{
		return false;
	}
	e=s->data[s->top];
	s->top--;
	return true;
}
//操作数出栈 
bool Pop2（SqStack2 *&sdouble &e）
{
	if（s->top==-1）
	{
		return false;
	}
	e=s->data[s->top];
	s->top--;
	return true;
}
//取运算符栈顶元素 
bool GetTop1（SqStack1 *&schar &e）
{
	if（s->top==-1）
	{
		return false;
	}
	e=s->data[s->top];
	return true;
}
//取操作数栈顶元素 
bool GetTop2（SqStack2 *&sdouble &e）
{
	if（s->top==-1）
	{
		return false;
	}
	e=s->data[s->top];
	return true;
}
//判断运算符栈是否为空 
bool StackEmpty（SqStack1 *s）
{
	return（s->top==-1）;
}
//将运算符表达式exp转换成后辍表达式postexp 
void trans1（char *expchar postexp[]）
{
	char e;
	SqStack1 *Optr;          //定义运算符栈
	InitStack1（Optr）;        //初始化运算符栈
	int i=0;                 //i作为postexp的下标
	while（*exp!=‘\0‘）        //循环至exp扫描完
	{
		switch（*exp）
		{
			case ‘（‘:                       //判定为左括号
				Push1（Optr‘（‘）;            //左括号进栈
			    exp++;                      //继续扫描
			    break;			
			case ‘）‘:                       //判定为右括号
				Pop1（Optre）;               //出栈元素e
			    while（e!=‘（‘）               //不为左括号时循环
				{
					postexp[i++]=e;         //将e存放到postexp中
					Pop1（Optre）;           //继续出栈元素e
			    }
			    exp++;                      //继续扫描
		    	break;			 
			case ‘+‘:                       //判定为加或减
			case ‘-‘:
				while（!StackEmpty（Optr））    //栈不为空时循环
				{
					GetTop1（Optre）;        //取栈顶元素e
					if（e!=‘（‘）              //e不是左括号
					{
						postexp[i++]=e;     //将e存放到postexp中
						Pop1（Optre）;       //出栈元素e
					}
					else
					{
						break;
					}
				}
				Push1（Optr*exp）;           //将加或减进栈
				exp++;                      //继续扫描
				break;
			case ‘*‘:                       //判定为乘或除
			case ‘/‘:
				while（!StackEmpty（Optr））    //栈不为空时循环
				{
					GetTop1（Optre）;        //取栈顶元素e
					if（e==‘*‘||e==‘/‘）      
					{
						postexp[i++]=e;     //将e存放到postexp中
						Pop1（Optre）;       //出栈元素e
					}
					else
					{
						break;
					}
				}
				Push1（Optr*exp）;           //将乘或除进栈