问题分析

什么后缀表达式

• 我们平时使用的为中缀表达式，操作符在两个操作数之间，而所谓后缀表达式，即操作符在两个操作数之后；
• 比如中缀表达式 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 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 E × + A C × − AB/C-DE\times +AC\times - AB/C−DE×+AC×−计算过程如下：

操作	后缀表达式
T 1 = A / b T_1=A/b T1​=A/b	T 1 C − D E × + A C × − T_1C-DE\times +AC\times - T1​C−DE×+AC×−
T 2 = T 1 − C T_2=T_1-C T2​=T1​−C	T 2 D E × + A C × − T_2DE\times +AC\times - T2​DE×+AC×−
T 3 = D × E T_3=D\times E T3​=D×E	T 2 T 3 + A C × − T_2T_3+AC\times - T2​T3​+AC×−
T 4 = T 2 + T 3 T_4=T_2+T_3 T4​=T2​+T3​	T 4 A C × − T_4AC\times - T4​AC×−
T 5 = A × C T_5=A\times C T5​=A×C	T 4 T 5 − T_4T_5- T4​T5​−
T 6 = T 4 − T 5 T_6=T_4-T_5 T6​=T4​−T5​	T 6 T_6 T6​

实现方法

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

优先级	操作符
1	一 目 减 （ 负 号 ） , ! 一目减（负号）,! 一目减（负号）,!
2	∗ , / , *,/,% ∗,/,
3	= , − =,- =,−
4	< , < = , > , > = <,<=,>,>= <,<=,>,>=
5	= = , ! = ==,!= ==,!=
6	且 且 且
7	或 或 或

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

标记	堆栈	输出	备注
A A A	空 空 空	A A A
× \times ×	× \times ×	A A A	栈为空，入栈
( ( (	× ( \times( ×(	A A A	括号开始，入栈
B B B	× ( \times( ×(	A B AB AB
+ + +	× ( + \times(+ ×(+	A B AB AB	括号未结束，入栈
C C C	× ( + \times(+ ×(+	A B C ABC ABC
) ) )	× \times ×	A B C + ABC+ ABC+	括号结束，符号出栈
× \times ×	× \times ×	A B C + × ABC+\times ABC+×	都为乘号，优先级相同，出栈，新乘号入栈
D D D	× \times ×	A B C + × D ABC+\times D ABC+×D
空 空 空	空 空 空	A B C + × D × ABC+\times D\times ABC+×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;
}