Java教程

数据结构-栈与队列--中缀转为后缀表达式

本文主要是介绍数据结构-栈与队列--中缀转为后缀表达式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题分析

什么后缀表达式

  • 我们平时使用的为中缀表达式,操作符在两个操作数之间,而所谓后缀表达式,即操作符在两个操作数之后
  • 比如中缀表达式 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;
}
这篇关于数据结构-栈与队列--中缀转为后缀表达式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!