使用栈实现表达式求值

使用栈实现表达式求值任何一个表达式都是由操作数,运算符,界限符组成的。操作数即是参加运算的数值或者变量,运算符则是加减乘除等组成,为简单起见,这里只实现加减乘除的运算,而常见的界限符则是左右括号和终止符。在运算过程中,要判断两个先后出现的运算符之间的优先顺序。为了实现算法,设置两个工作栈:用于存储运算符的栈opter,以及用于存储操作数及中间结果的栈opval。算法基本思想如下:(1)首先将操作数栈opv

大家好,又见面了,我是你们的朋友全栈君。

为了实现用栈计算算数表达式的值,需设置两个工作栈:用于存储运算符的栈opter,以及用于存储操作数及中间结果的栈opval。

算法基本思想如下:

(1)首先将操作数栈opval设为空栈,而将’#’作为运算符栈opter的栈底元素,这样的目的是判断表达式是否求值完毕。

(2)依次读入表达式的每个字符,表达式须以’#’结尾,若是操作数则入栈opval,若是运算符,则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作,(具体操作如下:(i)若top的优先级小于c,即top<c,则将c直接入栈opter,并读入下一字符赋值给c;(ii)若top的优先级等于c,即top=c,则弹出opter的栈顶元素,并读入下一字符赋值给c,这一步目的是进行括号操作;(iii)若top优先级高于c,即top>c,则表明可以计算,此时弹出opval的栈顶两个元素,并且弹出opter栈顶的的运算符,计算后将结果放入占opval中。)直至opter的栈顶元素和当前读入的字符均为’#’,此时求值结束。

算符间的优先关系如下表所示:

使用栈实现表达式求值

表中需要注意的是θ1为opter的栈顶元素,θ2位从表达式中读取的操作符,此优先级表可以用二维数组实现,具体见代码(表来源:严蔚敏《数据结构》)。

具体代码如下:

#include<iostream>     //输入的表达式要以'#'结尾,如‘5+6*3/(3-1)#’
#include<cstring>
#include<cstdio>
#include<cctype>
#include<stack>
using namespace std;

stack<char> opter;    //运算符栈
stack<double> opval;  //操作数栈

int getIndex(char theta)   //获取theta所对应的索引
{
	int index = 0;
	switch (theta)
	{
	case '+':
		index = 0;
		break;
	case '-':
		index = 1;
		break;
	case '*':
		index = 2;
		break;
	case '/':
		index = 3;
		break;
	case '(':
		index = 4;
		break;
	case ')':
		index = 5;
		break;
	case '#':
		index = 6;
	default:break;
	}
	return index;
}

char getPriority(char theta1, char theta2)   //获取theta1与theta2之间的优先级
{
	const char priority[][7] =     //算符间的优先级关系
	{
		{ '>','>','<','<','<','>','>' },
		{ '>','>','<','<','<','>','>' },
		{ '>','>','>','>','<','>','>' },
		{ '>','>','>','>','<','>','>' },
		{ '<','<','<','<','<','=','0' },
		{ '>','>','>','>','0','>','>' },
		{ '<','<','<','<','<','0','=' },
	};

	int index1 = getIndex(theta1);
	int index2 = getIndex(theta2);
	return priority[index1][index2];
}

double calculate(double b, char theta, double a)   //计算b theta a
{
	switch (theta)
	{
	case '+':
		return b + a;
	case '-':
		return b - a;
	case '*':
		return b * a;
	case '/':
		return b / a;
	default:
		break;
	}
}

double getAnswer()   //表达式求值
{
	opter.push('#');      //首先将'#'入栈opter
	int counter = 0;      //添加变量counter表示有多少个数字相继入栈,实现多位数的四则运算
	char c = getchar();
	while (c != '#' || opter.top() != '#')   //终止条件
	{
		if (isdigit(c))   //如果c在'0'~'9'之间
		{
			if (counter == 1)   //counter==1表示上一字符也是数字,所以要合并,比如12*12,要算12,而不是单独的1和2
			{
				double t = opval.top();
				opval.pop();
				opval.push(t * 10 + (c - '0'));
				counter = 1;
			}
			else
			{
				opval.push(c - '0');     //将c对应的数值入栈opval
				counter++;
			}
			c = getchar();
		}
		else
		{
			counter = 0;   //counter置零
			switch (getPriority(opter.top(), c))   //获取运算符栈opter栈顶元素与c之间的优先级,用'>','<','='表示
			{
			case '<':               //<则将c入栈opter
				opter.push(c);
				c = getchar();
				break;
			case '=':               //=将opter栈顶元素弹出,用于括号的处理
				opter.pop();
				c = getchar();
				break;
			case '>':               //>则计算
				char theta = opter.top();
				opter.pop();
				double a = opval.top();
				opval.pop();
				double b = opval.top();
				opval.pop();
				opval.push(calculate(b, theta, a));
			}
		}
	}
	return opval.top();   //返回opval栈顶元素的值
}

int main()
{
	//freopen("test.txt", "r", stdin);
	int t;     // 需要计算的表达式的个数
	cin >> t;
	getchar();
	while (t--)
	{
		while (!opter.empty())opter.pop();
		while (!opval.empty())opval.pop();
		double ans = getAnswer();
		cout << ans << endl<< endl;
		getchar();
	}
	return 0;
}

结果:

使用栈实现表达式求值

使用栈实现表达式求值

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/148806.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 永久免费内网穿透很简单,一看就明白(长文)

    永久免费内网穿透很简单,一看就明白(长文)对于网络用户来说,一定都经历过出门在外无法直接在外网访问内网、或是难以部署异地远程桌面,因此心急如焚的情况;对于企业来说,无论是财务管理软件难以将分店信息同步到总部进行统计汇总、还是员工出差在外或在家里就不能访问企业内部办公系统,都极大地影响了公司整体效率;对于个人开发者来说,微信小程序或者在线支付系统等开发环境往往需要一个可以外部访问的公网环境进行调试,而大多数的企业网络都被运营商做了转发设置,…

  • SVM资料

    SVM资料解释SMO算法比较好的文档http://wenku.baidu.com/view/aeba21be960590c69ec3769e.html参考博客:http://myjuno.blogbus.com/logs/242581064.htmlSMO算法http://cs229.stanford.edu/materials/smo.pdf外层循环(主程…

  • 浅谈滴滴派单算法

    浅谈滴滴派单算法(图片付费下载自视觉中国)作者|王犇刘春阳徐哲来源|滴滴技术(ID:didi_tech)【导读】说到滴滴的派单算法,大家可能感觉到既神秘又好奇,从出租车扬召到…

  • SecureCRT 中文(附上1.解决SecureCRT乱码问题2.解决Hostname lookup failed: host not found问题)[通俗易懂]

    secureCRT破解版是一款支持SSH1和SSH2的终端仿真程序,这个程序能够在windows系统中登陆UNIX或Linux的服务器主机并且还能进行管理设置,是一款非常强大的ssh传输软件,是用于连接运行包括Windows、UNIX和VMS的理想工具。并且它还有打印功能、可变屏幕尺寸、对不同主机保持不同的特性、颜色设置、自动注册等众多优秀的功能特色。同时还支持Telnet/SSH、TAPI、R…

  • 关于Java向上取整和向下取整(天花板函数)的说明

    关于Java向上取整和向下取整(天花板函数)的说明背景项目应用后期纪要!问题1.小数参数如何向上取整?2.小数参数如何向下取整?说明向上或向下取整的问题只针对小数类型的数据,在Java中主要用来处理double类型或float类型的数据。纪要函数是Math类下的基础函数,操作较为简单,比较容易上手。下面是随笔的Demo,以供参考:packagecom.company.num;/***天花板函数*用例主要说明两个函数*…

  • 《关于VirtualBox在桥接模式下无法联网 解决方案》

    《关于VirtualBox在桥接模式下无法联网 解决方案》博主遇到了这个问题,百度了大半天还是没有解决到,可能是由于下面链接的文章的标题关键词比较偏,很难精确的定位到此文章,于是博主就决定总结归纳了一下,希望对大家有所帮助。。经过无数次的百度,早已厌倦粘贴党,问牛答马党,错误党,大大的浪费了大家的时间,于是博主开了这篇文章..我们在VBOX上面安装了Linux之后,VBOX默认网络设置是使用NAT模式的,这种方式宿

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号