March 10.2022 --补充（POLAND NOTATION）

本文主要是介绍March 10.2022 --补充（POLAND NOTATION），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

March 10.2022 --补充（POLAND NOTATION）

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法。逆波兰表达式把运算量写在前面,把算符写在后面。

前中后缀表达式

前缀表达式：波兰表达式 不含括号的的算数表达式，将运算符写在前面，操作数写在后面
```
*-ab+cd
```
中缀表达式：我们通常理解的表达式必须含括号，操作符处于操作数的中间
```
（a-b）*(c+d)
```
后缀表达式：逆波兰表达式 不含括号，运算符放在两个运算对象的后面。
```
ab-cd+*
```
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下
1. 从左至右扫描，将3和4压入堆栈；
2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
3. 将5入栈；
4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5. 将6入栈；
6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

package Zhan;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
//如果要使用List 包 那必须要导包！！ alt + enterpublic class PolandNotation {public static void main(String[] args) {//逆波兰表达式 (3+4)*5-6; 其中该式子的逆波兰表达式可以写为 3 4 + 5 * 6 -；String sufficExpression ="30 40 + 5 * 6 -";//思路//1.先将 该计算表达式的逆波兰表达式字符串 放到 Arratlist中//2.将 Arraylist 传给一个方法，遍历 Arraylist 配合栈完成计算List<String> list=  getlistString(sufficExpression);System.out.println("list"+list);int res =calculate(list);System.out.println("计算的结果是"+res);}private static List<String> getlistString(String sufficExpression) {//将后缀表达式按照空格来拆分，拆分成字符串数组String[] split = sufficExpression.split(" ");//创建一个字符串形式的数组列表 用于接收 被拆分的字符串数组ArrayList<String> list = new ArrayList<>();for(String ele:split){list.add(ele);}return list;}//完成对逆波兰表达式的计算// 1.从左往右扫描， 将 3 和 4 压入栈中；//2.遇到 + 号运算符 弹出 4 和 3 （其中 4为栈顶元素，3为次栈顶元素），计算出 3+4 的值，得到7 将结果7入栈//3.将5 入栈//4.遇到 * 运算符 ，弹出5 和 7  计算出 5*7=35 将35入栈//5.遇到6 将6入栈//6.遇到 - 运算符，计算出来 35-6的值 得到最终结果//扫描的过程其实就是对list 的遍历public static int  calculate(List<String> ls){//创建一个栈Stack<String> stack = new Stack<>();//遍历 lsfor(String item:ls){if(item.matches("\\d+")){// 正则表达式如果遍历到的是一个或者多位数 则 入栈stack.push(item);}else { //遍历到的是一个运算符 则pop出两个数字 第一个出栈的是num2 第二个出栈的数命名为num1int num2 = Integer.parseInt(stack.pop());int num1 = Integer.parseInt(stack.pop());//由于出栈的元素的类型为 string  需要转化为int  类型所以调用Integer.parseInt方法 将字符串类型转化为 int 类型方便计算int res = 0;if(item.equals("+")){res = num1+num2;}else if(item.equals("-")){//在此处请注意 出栈的顺序res = num1 - num2;}else if(item.equals("*")){res = num1*num2;}else if(item.equals("/")){res = num1 / num2;}else {throw new RuntimeException("你输入的格式有误，请重新输入");}//请注意 这里使用了一个小技巧：即通过在前后加空格的方法，将整数类型转化为字符串类型stack.push(""+res);}}return Integer.parseInt(stack.pop());}
}