使用栈实现表达式求值

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

为了实现用栈计算算数表达式的值,需设置两个工作栈:用于存储运算符的栈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;}

结果:

点这里可以跳转到人工智能网站

发表评论