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

发布时间:2024-08-13 11:01

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

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

利用栈实现算术表达式的求值,表达式中可包含加+、减(负) -、乘*、除/、
乘方^、括号( )运算符,操作数可以为浮点数。 可采用直接求中缀表达式的方法,
也可采用先转换成后缀表达式后再求值的方法(参看课件) 。
实现时需注意如下:
( 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;
}


截图:

【数据结构】 之 表达式求值_第1张图片


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


ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号