【数据结构】 之 表达式求值

如要下载编译器，请看我的之前博客

笔者现大三，这篇博文及后面的几篇博文都是对大二所做的题目一些总结，哈哈，感觉自己那时候学的还可以，希望自己这点笔记能对你们有点帮助吧，加油！！！其实数据结构也没传说中的那么难，并且以后在我们面试的时候，数据结构可是面试官的法宝，对吧，咱们不能输在起跑线线上，好了，废话不多说，现在让我们来学习表达式求值。我先把老师给我们出的题目给大家看看吧，不知道我们是不是一样的（纯洁的微笑），题目如下：

利用栈实现算术表达式的求值，表达式中可包含加+、减（负） -、乘*、除/、
乘方^、括号( )运算符，操作数可以为浮点数。 可采用直接求中缀表达式的方法，
也可采用先转换成后缀表达式后再求值的方法（参看课件） 。
实现时需注意如下：
（ 1）带小数点的数值生成 （ 理解整数数值的生成，小数部分的处理与之类似）。
（ 2）考虑负号的情况。负号与减号形式上一样，如何区分？
• 输入的表达式串中第 1 个字符是’-’
– 可断定此’-’是负号
• 其余的’-’
– 若紧接在’(’之后的’-’可断定是负号
（ 3）负号的处理
• 方法 1：若已断定是负号，可先压入数值 0 进入操作数栈，如此，可
将负号看作减号。
• 方法 2： 若已断定是负号，则紧接其后的数字字符转换成数值后，要
将其对应的相反数(负数)压入操作数栈。

工程截图：

先建一个工程，头文件就不贴了，源代码里有，如果有需要，下面有下载地址，我们重点讲如何利用栈进行表达式求值的，

求表达式基本思想就是，首先读取输入的字符串，然后分别读出数字和操作符，如果是数字压入数字栈，如果是操作符与之前的操作符比较优先级，如果大，从数字栈中取出俩个数字运算再放入数字栈，如果小，操作符就压入操作符栈，遇到“=”停止，输入数字栈中的栈顶元素即为运算结果，代码如下(other.cpp)：

#include"Sqstack.h"
#include"other.h"

double EvluateExpression(char str[],LinkStack &OPTR,LinkStack1 &OPND)
{
	int i=0,t,j,falg=0;
	double a,b,sum,s;
	char theta,x;
	InitStack(OPND);
	InitStack(OPTR);
	Push(OPTR,'#');	
	if(str[0]=='-')
	{
		Push(OPND,0);
	}
	while(str[i] !='#' || GetTop(OPTR)!='#')
	{
	
		if(str[i]>='0' && str[i]<='9')
		{
			sum=0;
			while(str[i]>='0' && str[i]<='9')                                      //将整数保存到sum中
			{
				sum=sum*10+str[i++]-'0';
			}
			if(str[i]=='.')                                                         //如果有小数点，将j移动下一个运算符之前的字符，从那个字符开始往后依次除10，直到小数点之后的那一位字符，与sum相加
			{
				s=0;
				j=i+1;
				while(str[j]>='0' && str[j]<='9')
				{
					j++;
				}	
				for(t=j-1;t>i;t--)
				{
					s=s/10+str[t]-'0';
				}
				s=s/10;
				//printf("%lf\n",s);
				sum=sum+s;
				i=j;
			}
			Push(OPND,sum);
		}
		else
		{
			if(str[i]=='-' && str[i-1]=='(')
			{
				Push(OPND,0);
			}
			switch(Precede(GetTop(OPTR),str[i]))
			{
			case '<':
				Push(OPTR,str[i]);
				i++;
				break;

			case '>':

				Pop(OPTR,theta);
				Pop(OPND,b);Pop(OPND,a);
				Push(OPND,Operate(a,theta,b));
				break;
			case '=':
				Pop(OPTR,x);
				i++;
				break;
			}
		}
	}
	return GetTop(OPND);
}

char Precede(char a, char b)
{
	int i,j;
	char Ns[7]={'+','-','*','/','(',')','#'};
	char str[7][7]={'>','>','<','<','<','>','>',
		            '>','>','<','<','<','>','>',
					'>','>','>','>','<','>','>',
					'>','>','>','>','<','>','>',
					'<','<','<','<','<','=',' ',
					'>','>','>','>',' ','>','>',
					'<','<','<','<','<',' ',' '};
	for(i=0;i<7;i++)
	{
		if(Ns[i]==a)
			break;
	}
	for(j=0;j<7;j++)
	{
		if(Ns[j]==b)
			break;
	}
	return str[i][j];

}
double Operate(double a,char op,double b)
{
	switch(op)
	{
	case '+':return a+b;break;
	case '-':return a-b;break;
	case '*':return a*b;break;
	case '/':return a/b;break;
	}
}

栈的基本操作函数（Sqstack.cpp）

#include"Sqstack.h"
#include"other.h"

void InitStack(LinkStack &OPTR)
{
	OPTR=NULL;
}
void InitStack(LinkStack1 &s)
{
	s=NULL;
}
void Push(LinkStack &OPTR,char e)
{
	LinkStack p;
	p=new StackNode;
	p->data=e;
	p->next=OPTR;
	OPTR=p;

}
void Push(LinkStack1 &s,double e)
{
	LinkStack1 p;
	p=new StackNode1;
	p->data=e;
	p->next=s;
	s=p;

}
char  GetTop(LinkStack &OPTR)
{
	if(OPTR!=NULL)
		return OPTR->data;
}
double  GetTop(LinkStack1 &s)
{
	if(s!=NULL)
		return s->data;
}
void Pop(LinkStack &s,char &e)
{
	LinkStack p;
	e=s->data;
	p=s;
	s=s->next;
	delete p;
}
void Pop(LinkStack1 &s,double &e)
{
	LinkStack1 p;
	e=s->data;
	p=s;
	s=s->next;
	delete p;
}
void DestoryStack(LinkStack &s)
{
	LinkStack p;
	while(s)
	{
		p=s;
		s=s->next;
		delete p;
	}
}
void DestoryStack(LinkStack1 &s)
{
	LinkStack1 p;
	while(s)
	{
		p=s;
		s=s->next;
		delete p;
	}
}
int StackEmpty(LinkStack s)
{
	if(s==NULL) return ERROR;
}
int StackEmpty(LinkStack1 s)
{
	if(s==NULL) return ERROR;
}

截图：

源码下载地址：http://pan.baidu.com/s/1slRFJzf