[数据结构与算法]数据结构-栈与队列--计算表达式

问题分析

• 上一节我们已经知道该如何将中缀表达式转为后缀表达式（传送门），这里我们将直接将实际计算一个表达式，比如$99+87\times 98$#，要求表达式结尾以’#‘结束；

实现方法

得到后缀表达式

• 这里我们用队列存储后缀表达式结果；
• 另一方面值得注意的是这里的操作数是不知几位的数字，在转后缀的要值得注意（小树我自己踩过的坑 ），解决方法是在遇到操作符前将操作数的每一位存储在一个字符串中，在遇到操作符时，将其存储在队列中，然后将字符串清空，存储下个操作数。具体代码如下：

//判断是否为运算符
bool is_operator(const char temp)
{
	return temp == '+' || temp == '-' || temp == '/' || temp == '*' || temp == '(' || temp == ')';
}

//得到运算符优先级
long long level_operator(char temp)
{
	if (temp == '+' || temp == '-')return 2;
	else if (temp == '*' || temp == '/')return 1;
	else return 0;
}

//中缀转后缀
queue<string>* Infix_convert(string ex)
{
	if (ex.back() != '#')ex.append(1, '#');
	
	//得到表达式长度
	stack<char>op;
	op.push('#');
	//将后缀结果存储在队列中
	queue<string>*re=new queue<string>;
	//记录数字
	string infix_ex;

	for (int i = 0; ex[i] != '#'; i++)
	{
		if (!is_operator(ex[i]))infix_ex.append(1,ex[i]);//将操作数的每一位存储

		else if (ex[i] == ')')
		{
			//将数字字符串储存在队列中
			if (!infix_ex.empty())
			{
				re->push(infix_ex);
				infix_ex.clear();
			}

			for (; op.top() != '('; op.pop())
			{
				//将字符转为字符串
				char temp[2] = { op.top(),0 };
				re->push(temp);
			}
			op.pop();
		}
		else
		{
			//将数字字符串储存在队列中
			if (!infix_ex.empty())
			{
				re->push(infix_ex);
				infix_ex.clear();
			}

			for (; level_operator(op.top()) <= level_operator(ex[i]) && op.top() != '#' && op.top() != '('; op.pop())
			{
				//将字符转为字符串
				char temp[2] = { op.top(),0 };
				re->push(temp);
			}
			op.push(ex[i]);
		}
	}
	//将数字字符串储存在队列中
	if (!infix_ex.empty())
	{
		re->push(infix_ex);
		infix_ex.clear();
	}

	while (!op.empty())
	{
		//将字符转为字符串
		char temp[2] = { op.top(),0 };
		re->push(temp);
		op.pop();
	}

	return re;
}

操作数字符串转为数字

• 这部分很简单，代码如下：

//将字符串转为数字
long long string_to_int(string temp)
{
	int length = temp.size();
	long long re = 0;
	for (int i = 0; i < length; i++)
	{
		long long pi = 1;
		for (int j = length - i - 2; j >= 0; j--)
		{
			pi *= 10;
		}
		re += (long long(char(temp[i])) - 48)*pi;
	}
	return re;
}

计算过程

• 在后缀表达式队列中从队首读取，操作数存储在栈中，当在队列中读取到操作符时，将栈的栈顶前两位取出计算，并将结果存储在栈中，以此往复，代码如下：

//一般计算
long long Basic_eval(long long a, long long b, string op)
{
	if (op == "+")return a + b;
	else if (op == "-")return a - b;
	else if (op == "*")return a * b;
	else if (op == "/")return a / b;
	else throw"Cann't Eval!";
}

//计算表达式
long long Eval(string ex)
{
	//转为后缀表达式
	queue<string>*ex_inf;
	ex_inf = Infix_convert(ex);
	//储存计算结果
	stack<long long>data;
	for (; ex_inf->front() != "#"; ex_inf->pop())
	{
		if (!is_operator_s(ex_inf->front()))data.push(string_to_int(ex_inf->front()));
		else
		{
			long long dataB = data.top();
			data.pop();
			long long dataA = data.top();
			data.pop();
			data.push(Basic_eval(dataA, dataB, ex_inf->front()));
		}
	}
	return data.top();
}

代码总览

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

//判断是否为运算符
bool is_operator(const char temp)
{
	return temp == '+' || temp == '-' || temp == '/' || temp == '*' || temp == '(' || temp == ')';
}

//判断是否为运算符
bool is_operator_s(const string temp)
{
	return temp == "+" || temp == "-" || temp == "/" || temp == "*" || temp == "(" || temp == ")";
}

//得到运算符优先级
long long level_operator(char temp)
{
	if (temp == '+' || temp == '-')return 2;
	else if (temp == '*' || temp == '/')return 1;
	else return 0;
}

//中缀转后缀
queue<string>* Infix_convert(string ex)
{
	if (ex.back() != '#')ex.append(1, '#');

	//得到表达式长度
	stack<char>op;
	op.push('#');
	//将后缀结果存储在队列中
	queue<string>*re=new queue<string>;
	//记录数字
	string infix_ex;

	for (int i = 0; ex[i] != '#'; i++)
	{
		if (!is_operator(ex[i]))infix_ex.append(1,ex[i]);

		else if (ex[i] == ')')
		{
			//将数字字符串储存在队列中
			if (!infix_ex.empty())
			{
				re->push(infix_ex);
				infix_ex.clear();
			}

			for (; op.top() != '('; op.pop())
			{
				//将字符转为字符串
				char temp[2] = { op.top(),0 };
				re->push(temp);
			}
			op.pop();
		}
		else
		{
			//将数字字符串储存在队列中
			if (!infix_ex.empty())
			{
				re->push(infix_ex);
				infix_ex.clear();
			}

			for (; level_operator(op.top()) <= level_operator(ex[i]) && op.top() != '#' && op.top() != '('; op.pop())
			{
				//将字符转为字符串
				char temp[2] = { op.top(),0 };
				re->push(temp);
			}
			op.push(ex[i]);
		}
	}
	//将数字字符串储存在队列中
	if (!infix_ex.empty())
	{
		re->push(infix_ex);
		infix_ex.clear();
	}

	while (!op.empty())
	{
		//将字符转为字符串
		char temp[2] = { op.top(),0 };
		re->push(temp);
		op.pop();
	}

	return re;
}

//将字符串转为数字
long long string_to_int(string temp)
{
	int length = temp.size();
	long long re = 0;
	for (int i = 0; i < length; i++)
	{
		long long pi = 1;
		for (int j = length - i - 2; j >= 0; j--)
		{
			pi *= 10;
		}
		re += (long long(char(temp[i])) - 48)*pi;
	}
	return re;
}

//一般计算
long long Basic_eval(long long a, long long b, string op)
{
	if (op == "+")return a + b;
	else if (op == "-")return a - b;
	else if (op == "*")return a * b;
	else if (op == "/")return a / b;
	else throw"Cann't Eval!";
}

//计算表达式
long long Eval(string ex)
{
	//转为后缀表达式
	queue<string>*ex_inf;
	ex_inf = Infix_convert(ex);
	//储存计算结果
	stack<long long>data;
	for (; ex_inf->front() != "#"; ex_inf->pop())
	{
		if (!is_operator_s(ex_inf->front()))data.push(string_to_int(ex_inf->front()));
		else
		{
			long long dataB = data.top();
			data.pop();
			long long dataA = data.top();
			data.pop();
			data.push(Basic_eval(dataA, dataB, ex_inf->front()));
		}
	}
	return data.top();
}

//主函数
int main()
{

	string ex;
	cout << "请输入表达式：" << endl;
	cin >> ex;
	cout <<"=\t"<< Eval(ex) << endl;
	
	return 0;
}

上一节：数据结构-栈与队列–中缀转后缀表达式