问题分析

什么后缀表达式

• 我们平时使用的为中缀表达式，操作符在两个操作数之间，而所谓后缀表达式，即操作符在两个操作数之后；
• 比如中缀表达式 A × B / C A\times B/C A×B/C变成后缀表达式 A B × C / AB\times C/ AB×C/。

为什么要使用后缀表达式

• 在我们的认知中，我们接触一般都是中缀表达式，例如： A + B A+B A+B、 A / B − C + D × E − A × C A/B-C+D\times E-A\times C A/B−C+D×E−A×C等；
• 但在计算机中，如果是像 A + B A+B A+B这样简单的计算不用太多思考，但对于像 A / B − C + D × E − A × C A/B-C+D\times E-A\times C A/B−C+D×E−A×C这样甚至还要稍复杂的表达式，我们要考虑到计算符优先级的问题，将其转为 ( ( ( ( A / B ) − C ) + ( D × E ) ) − ( A × C ) ) ((((A/B)-C)+(D\times E))-(A\times C)) ((((A/B)−C)+(D×E))−(A×C))才能进行计算；
• 尤其涉及到计算符优先级的表达式时，如果直接计算中缀表达式就显得有些复杂了，这里我可以将其转换为后缀表达式进行计算，以 A / B − C + D × E − A × C A/B-C+D\times E-A\times C A/B−C+D×E−A×C为例：

• A B / C − D E × + A C × − AB/C-DE\times +AC\times - AB/C−DE×+AC×−计算过程如下：

实现方法

• 我们应该先了解各种操作符的优先级

• 我们可以用数据机构-栈来存储操作符，以表达式 A × ( B + C ) × D A\times (B+C)\times D A×(B+C)×D为例 ，过程如下表：

• 在栈中栈顶元素与将要入栈的操作符（不包括括号或者停位符#）优先级进行比较，优先级高就先输出。

• 以下代码以 + − × / +-\times / +−×/表达式为例

操作符优先级获取

• 这里直接上代码

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

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

中缀转后缀表达式

• 这里的函数没有返回结果，而是在函数中直接输出，代码如下：

//中缀转后缀
//中缀转后缀
void Infix_convert(string ex)
{
	//得到表达式长度
	int length = ex.size();
	stack<char>op;
	//防止栈空出错
	op.push('#');

	for (int i = 0; i < length; i++)
	{
		if (!is_operator(ex[i]))cout << ex[i];
		else if (ex[i] == ')')
		{
			for (; op.top() != '('; op.pop())
			{
				cout << op.top();
			}
			op.pop();
		}
		else
		{
			for (; level_operator(op.top()) <= level_operator(ex[i])&&op.top()!='#'&&op.top()!='('; op.pop())
			{
				cout << op.top();
			}
			op.push(ex[i]);
		}
	}
	//将栈中的剩余操作符输出
	while (op.top() != '#')
	{
		cout << op.top();
		op.pop();
	}
	cout << endl;
}

代码总览

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

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

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

//中缀转后缀
void Infix_convert(string ex)
{
	//得到表达式长度
	int length = ex.size();
	stack<char>op;
	//防止栈空出错
	op.push('#');

	for (int i = 0; i < length; i++)
	{
		if (!is_operator(ex[i]))cout << ex[i];
		else if (ex[i] == ')')
		{
			for (; op.top() != '('; op.pop())
			{
				cout << op.top();
			}
			op.pop();
		}
		else
		{
			for (; level_operator(op.top()) <= level_operator(ex[i])&&op.top()!='#'&&op.top()!='('; op.pop())
			{
				cout << op.top();
			}
			op.push(ex[i]);
		}
	}
	//将栈中的剩余操作符输出
	while (op.top() != '#')
	{
		cout << op.top();
		op.pop();
	}
	cout << endl;
}

int main()
{

	string exp;
	cout << "请输入表达式" << endl;
	cin >> exp;
	Infix_convert(exp);
	

	return 0;
}