表达式求值

于 2018-07-13 18:38:54 发布
阅读量4.5k 收藏 29
点赞数 6
分类专栏： 算法 文章标签： 算法 表达式求值
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/libingbojava/article/details/81035975
版权

这里对严蔚敏版的数据结构一书中表达式求值算法给出代码实现.

具体参见严蔚敏版数据结构表达式取值章节.

表达式求值 实际使用栈来做, 也就是说 , 表达式求值实际是栈的应用 . 这里采用 " 算符 优先法" 对表达式求值.代码里实现的是基于加减乘除的整数运算 . 没有对表达式出错情况进行处理. 如果读者需要出错处理 , 在Precede()函数里返回0的代表表达式出错 . 读者可依据返回值自行处理 .

本算法使用两个工作栈 , SqStack_OPTR工作栈 , 用来存放运算符 . SqStack_OPND工作栈 , 用来存放操作数或运算结果 . 因为一个表达式根本上就是由运算符和操作数组成 , 所以这里用到了两个工作栈.

表达式以#开始 , 以#结束 . 开始的#不由用户输入 , 代码 里在创建栈是自动加入 . 结束的#号用户手动输入 , 用来表示一个表达式的结束 .

具体的算法思路不在这里解释了 ,写了一下午了, 脖子有点疼 .

给出算符优先级表 , Precede()函数依据算符优先级表来确定两个操作数的关系 .

算符优先关系表
 +-*/()#
+>><<<>>
->><<<>>
*>>>><>>
/>>>><>>
(<<<<<=0
)>>>>0>>
#<<<<<0=

具体代码如下:

#include<iostream>
#include<stdlib.h>
#define STACK_INIT_SIZE 100  //存储空间初始分配量 
#define STACKINCREMENT 10  //存储空间增量
using namespace std;
typedef  struct
{
	int *base;  //栈底指针 ,构造前和销毁后都为NULL
	int *top;  //栈顶指针
	int stacksize ; //当前以分配的存储空间 
 } SqStack_OPND;
 
 
typedef  struct
{
	char *base;  //栈底指针 ,构造前和销毁后都为NULL
	char *top;  //栈顶指针
	int stacksize ; //当前以分配的存储空间 
 } SqStack_OPTR;
 
 
bool   InitStack_OPND(SqStack_OPND &s)
{
	//构造一个空栈
	s.base = (int*) malloc(STACK_INIT_SIZE * sizeof(int) ) ;
	if(!s.base)  return false;
	s.top = s.base;
	s.stacksize = STACK_INIT_SIZE;
	return true;
} 

bool   InitStack_OPTR(SqStack_OPTR &s)
{
	//构造一个空栈
	s.base = (char*) malloc(STACK_INIT_SIZE * sizeof(char) ) ;
	if(!s.base)  return false;
	s.top = s.base;
	s.stacksize = STACK_INIT_SIZE;
	return true;
} 


char  GetTop_OPTR(SqStack_OPTR &s )
{
	//若栈不为空,返回字符e ,否则返回数值0 
	char e;
	if(s.top == s.base)  return 0;
	e = *(s.top-1);
	return e;
}


char  GetTop_OPND(SqStack_OPND &s )
{
	//若栈不为空,返回字符e ,否则返回数值0 
	int e;
	if(s.top == s.base)  return 0;
	e = *(s.top-1);
	return e;
}


bool  Push_OPTR(SqStack_OPTR &s  , char e)
{
	//插入e为新的栈顶元素
	if(s.top - s.base > s.stacksize)	{   //栈满,追加存储空间 
		s.base = (char*) realloc(s.base  , (s.stacksize + STACKINCREMENT)  * sizeof(char) );
		if(!s.base) return false;
		s.top =  s.base + s.stacksize;
		s.stacksize += STACKINCREMENT;
	 } //增加空间完毕 
	 
	 *s.top++ = e;
	 return true;
}


bool  Push_OPND(SqStack_OPND &s  , int e)
{
	//插入e为新的栈顶元素
	if(s.top - s.base > s.stacksize)	{   //栈满,追加存储空间 
		s.base = (int*) realloc(s.base  , (s.stacksize + STACKINCREMENT)  * sizeof(int) );
		if(!s.base) return false;
		s.top =  s.base + s.stacksize;
		s.stacksize += STACKINCREMENT;
	 } //增加空间完毕 
	 
	 *s.top++ = e;
	 return true;
}


bool Pop_OPTR(SqStack_OPTR &s , char &e)
{
	//若栈不为空,删除s的栈顶元素,用e返回其值,并返回true , 否则返回false
	if(s.top == s.base)  return false;
	e = * --s.top;
	return  true; 
}


bool Pop_OPND(SqStack_OPND &s , int &e)
{
	//若栈不为空,删除s的栈顶元素,用e返回其值,并返回true , 否则返回false
	if(s.top == s.base)  return false;
	e = * --s.top;
	return  true; 
}


//定义两个工作栈
//用来寄存运算符的栈   :  OPTR
//用来寄存操作数或运算结果的栈   :  OPND
SqStack_OPTR OPTR ;
SqStack_OPND OPND ;

int e;  //接收栈顶元素 GetTop() 和 Pop()中用到

char Precede(char  e , char c)  //根据算符优先关系表,返回三个优先关系之一 
{
		//规定, e 为01 ,c 为 02
		int convert_e , convert_c; //将e 和 c 转换为数字在进行比较,方便代码书写和理解
		
		//对e 进行转换 
		switch(e)
		{
			case '+' : convert_e = 1 ;  break;
			case '-' : convert_e = 2 ;  break;	
			case '*' : convert_e = 3 ;  break;
			case '/' : convert_e = 4 ;  break;
			case '(' : convert_e = 5 ;  break;
			case ')' : convert_e = 6 ;  break;
			case '#' : convert_e = 7 ;  break;
		} 
		
		
		//对c 进行转换 
		switch(c)
		{
			case '+' : convert_c = 1 ;  break;
			case '-' : convert_c = 2 ;  break;	
			case '*' : convert_c = 3 ;  break;
			case '/' : convert_c = 4 ;  break;
			case '(' : convert_c = 5 ;  break;
			case ')' : convert_c = 6 ;  break;
			case '#' : convert_c = 7 ;  break;
		} 
		
		if(convert_e == 1 && convert_c == 1)  return '>';
		if(convert_e == 1 && convert_c == 2)  return '>';
		if(convert_e == 1 && convert_c == 3)  return '<';
		if(convert_e == 1 && convert_c == 4)  return '<';
		if(convert_e == 1 && convert_c == 5)  return '<';
		if(convert_e == 1 && convert_c == 6)  return '>';
		if(convert_e == 1 && convert_c == 7)  return '>';
		
		
		
		if(convert_e == 2 && convert_c == 1)  return '>';
		if(convert_e == 2 && convert_c == 2)  return '>';
		if(convert_e == 2 && convert_c == 3)  return '<';
		if(convert_e == 2 && convert_c == 4)  return '<';
		if(convert_e == 2 && convert_c == 5)  return '<';
		if(convert_e == 2 && convert_c == 6)  return '>';
		if(convert_e == 2 && convert_c == 7)  return '>';
		
		
		if(convert_e == 3 && convert_c == 1)  return '>';
		if(convert_e == 3 && convert_c == 2)  return '>';
		if(convert_e == 3 && convert_c == 3)  return '>';
		if(convert_e == 3 && convert_c == 4)  return '>';
		if(convert_e == 3 && convert_c == 5)  return '<';
		if(convert_e == 3 && convert_c == 6)  return '>';
		if(convert_e == 3 && convert_c == 7)  return '>';
		
		
		
		if(convert_e == 4 && convert_c == 1)  return '>';
		if(convert_e == 4 && convert_c == 2)  return '>';
		if(convert_e == 4 && convert_c == 3)  return '>';
		if(convert_e == 4 && convert_c == 4)  return '>';
		if(convert_e == 4 && convert_c == 5)  return '<';
		if(convert_e == 4 && convert_c == 6)  return '>';
		if(convert_e == 4 && convert_c == 7)  return '>';
		
		
		if(convert_e == 5 && convert_c == 1)  return '<';
		if(convert_e == 5 && convert_c == 2)  return '<';
		if(convert_e == 5 && convert_c == 3)  return '<';
		if(convert_e == 5 && convert_c == 4)  return '<';
		if(convert_e == 5 && convert_c == 5)  return '<';
		if(convert_e == 5 && convert_c == 6)  return '=';
		if(convert_e == 5 && convert_c == 7)  return '0';  //出现语法错误是返回字符0  因为 (  和 # 不允许相继出现 
		
		
		if(convert_e == 6 && convert_c == 1)  return '>';
		if(convert_e == 6 && convert_c == 2)  return '>';
		if(convert_e == 6 && convert_c == 3)  return '>';
		if(convert_e == 6 && convert_c == 4)  return '>';
		if(convert_e == 6 && convert_c == 5)  return '0';   // 不允许出现 ) ( 的形式 
		if(convert_e == 6 && convert_c == 6)  return '>';
		if(convert_e == 6 && convert_c == 7)  return '>'; 
		
		
		if(convert_e == 7 && convert_c == 1)  return '<';
		if(convert_e == 7 && convert_c == 2)  return '<';
		if(convert_e == 7 && convert_c == 3)  return '<';
		if(convert_e == 7 && convert_c == 4)  return '<';
		if(convert_e == 7 && convert_c == 5)  return '<';
		if(convert_e == 7 && convert_c == 6)  return '0';  //# 和 ( 不允许同时相继出现 
		if(convert_e == 7 && convert_c == 7)  return '=';
} //Precede

char theta;  // 在Precede()函数判出> 的情况下, 存放从OPTR中出栈的运算符

//返回运算结果  theta为操作数  a 和 b 为运算符左值 和 右值 
int  Operate(int a , char theta , int b)
{
	switch(theta)
	{
		case '+' : return a+b;
		case '-' : return a-b;
		case '*' : return a*b;
		case '/' : return a/b;
	}
} 

bool In(char c)
{
	switch(c)
	{
		case '+' :
		case '-' :
		case '*' :
		case '/' :
		case '(' :
		case ')' :
		case '#' : return true;
	}
	return false;
}



int  EvaluateExpression()   //int 是返回表达式运算后的最终结果 
{
	char c;
	InitStack_OPTR(OPTR);   Push_OPTR(OPTR , '#');
	InitStack_OPND(OPND);   c = getchar();
	
	while( c != '#' || GetTop_OPTR(OPTR) != '#')
	{
		if(!In(c)) 
		{
			
			Push_OPND(OPND , c-48); c =getchar();  //不是运算符则进栈 
		}
		else
		{
			switch( Precede(GetTop_OPTR(OPTR) , c) )
			{
				case '<':  //栈顶元素优先权低
				{
					Push_OPTR(OPTR , c) ; c = getchar(); break;
				} 
				
				case '=':  //脱括号并接收下一个字符
				{
					char x; //接收退栈后的值 
					Pop_OPTR(OPTR , x) ;  c = getchar(); break;
				} 
				
				case '>':  //退栈并将结果存入栈
				{
					int a ,b;
					Pop_OPTR(OPTR , theta);
					Pop_OPND(OPND , b); Pop_OPND(OPND ,a);
					Push_OPND(OPND , Operate(a ,theta ,b));
					break;
				} 
			}//switch
		}
	} //while
	return GetTop_OPND(OPND);
} 

int main()
{
	cout<<"输入表达式,得出运算结果,输入以#结束,输入完毕请按回车!"<<endl;
	int result = EvaluateExpression();
	cout<<"表达式结果为:"<<endl;
	cout<<result<<endl;
	return 0;
}

运行结果图:


哈工大数据结构作业-算数表达式求值
11-29
在哈工大的数据结构课程中，学生被分配了一项作业，任务是实现一个算数表达式求值的程序。这个程序不仅需要处理基本的算数运算，如加法、减法、乘法和除法，还要扩展到处理小数计算以及涉及变量的计算。这个项目旨在...
数据结构-表达式求值实验报告.doc
08-27
表达式求值实验报告 数据结构是计算机科学中的一门重要课程，涉及到算法、数据存储、表达式求值等多个方面。在本次实验报告中，我们将着重于表达式求值的实现，包括数据结构设计、算法设计、ADT 描述等方面。 1. ...
8.表达式求值_python/表达式求值_
09-29
在Python编程语言中，表达式求值是一项基本且重要的任务，它涉及到将字符串形式的数学或逻辑表达式转换为实际的计算结果。本教程将深入探讨如何使用Python来实现表达式求值，特别是通过五行代码的简洁实现，以及相关...
算数表达式求值-数据结构实验报告
09-08
这篇报告主要讨论的是一个大一下学期数据结构课程的设计项目，目标是实现一个算数表达式求值的程序。这个程序采用“算符优先法”来处理包含加减乘除及括号的算术表达式，并通过栈这一数据结构来辅助计算。 首先，...
数据结构-实验3-后缀表达式求值.doc
07-11
通常，求后缀表达式值的函数会遍历后缀表达式，每遇到一个数字就压入操作数栈，每遇到一个运算符就从栈中取出相应的操作数进行运算并替换为结果。主函数将串接整个程序并负责输入输出，包括接收用户输入的后缀表达式...
表达式求值（采用栈实现）
10-15
利用栈实现算术表达式的求值，表达式中可包含加+、减（负） -、乘*、除/、 乘方^、括号( )运算符，操作数可以为浮点数。 可采用直接求中缀表达式的方法， 也可采用先转换成后缀表达式后再求值的方法（参看课件） 。 实现时需注意如下： （ 1）带小数点的数值生成 （ 理解整数数值的生成，小数部分的处理与之类似）。 （ 2）考虑负号的情况。负号与减号形式上一样，如何区分？ • 输入的表达式串中第 1 个字符是’-’ – 可断定此’-’是负号 • 其余的’-’ – 若紧接在’(’之后的’-’可断定是负号 （ 3）负号的处理 • 方法 1：若已断定是负号，可先压入数值 0 进入操作数栈，如此，可 将负号看作减号。 • 方法 2： 若已断定是负号，则紧接其后的数字字符转换成数值后，要 将其对应的相反数(负数)压入操作数栈
严蔚敏 数据结构 表达式求值
12-05
严蔚敏 数据结构 表达式求值 vs2008
评论 8
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值