中缀转后缀表达式(思路分析) [数据结构][Java]

中缀转后缀表达式(思路分析)

注意: 我们的后缀表达式中是数值在前,运算符在后面,并且我们的后缀表达式中是没有括号的,而我们的中缀表达式中是有小括号的,所以我们将中缀表达式转为后缀表达式的时候会将小括号消除掉 —> 至于如何消除我们下面会具体的进行一个分析

中缀表达式转后缀表达式的思路步骤分析:

①初始化两个栈: 运算符栈s1和存储中间结果的栈s2

• 什么叫做存储中间结果的栈? —> 其实就是存储我们的结果的栈,不过中间结果也是存储到这个栈中的,最后的时候这个栈中就是存储的我们的最终结果

②从左至右扫描中缀表达式

③遇到数值时,将其压入s2栈中

④如果遇到运算符时,比较其与s1栈顶运算符的优先级:

1. 如果s1为空,或者栈顶元素的为左括号"(",则直接将此运算符入栈
2. 否则如果优先级比栈顶运算符的优先级高,也将运算符压入s1栈中
3. 否则(也就是如果优先级比栈顶运算符小或者是等于的时候),将s1栈顶的运算符弹出并压入到s2中,然后再次转到④步骤中与s1中新栈顶运算符相比较(比较优先级)

⑤遇到括号时:

1. 如果是左括号"(",则直接压入s1栈中
2. 如果是右括号")“,这依次弹出s1栈顶的运算符,并压入s2栈中,直到遇到左括号为止, 此时将这一对的括号丢弃(也就是将s1中的左括号”("出栈 , 并且直接跳过右括号)

⑥重复②至⑤步骤,直到处理到表达式的最右边

⑦将s1中剩余的运算符依次弹出并压入到s2中

⑧依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

• 我们的后缀表达式是运算符在数值的后面(相对), 所以后缀表达式的最前面的两个值肯定是两个数值, 而我们的后缀表达式结果是数值栈的所有值依次出栈, 那么其实我们也就是数值栈存储的是我们的最终结果, 并且是优先级越高的越先入栈, 最终逆序之后就是优先级高的运算在前面

具体的代码实现的思路分析:

首先我们第一个要解决的问题就是: 我们使用String类型的变量存储中缀表达式的话, 对于这个String类型变量遍历起来比较繁琐

• 对应的解决思路:
• 首先我们拿到一个String类型的中缀表达式之后,直接对这个String类型的变量进行遍历比较复杂,因为我们还要判断如果扫描到一个数值的时候还要判断这个数值是否是一个多位数,就要对这个String类型变量的下一个位置继续进行一个判断,所以这个过程是比较复杂的,而我们对于ArrayList实例遍历是很方便的,一个多位数对应的就是一个ArrayList实例中的一个元素,所以我们可以编写一个方法,通过这个方法我们可以将我们的String类型的中缀表达式中的各个数据(数值和运算符)全部存储到我们的ArrayList实例中 —> 所以我们选择编写一个自定义方法toInfixExpression() , 这个方法的功能就是将我们的存储中缀表达式的String类型变量中的中缀表达式数据存储到一个ArrayList实例中

然后就是我们可以发现我们上面的思路步骤分析中定义的s2栈并没有执行过出栈的操作,并且最后还是要将保存到s2栈中的数据出栈之后进行一个逆序的操作,这个时候我们细细分析之后就会发现我们完全没有必要创建一个s2栈

• 我们可以将这个s2栈替换成为一个集合对象,我们只需要将我们的中间数据存储到我们的集合对象中就可以了,我们的栈中的数据出栈后执行一个逆序其实就相当与直接将数据存储到集合中进行一个顺序输出, 所以我们直接使用一个集合对象替换s2栈就可以了