import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//先定义一个逆波兰表达式 (3+4)×5-6 ===> 3 4 + 5 × 6 -
String suffixExpression = "30 4 + 5 * 6 -";
//1.先将" 3 4 + 5 * 6 -"===>放入ArrayList中
//2.将ArrayList传递给一个方法，配合栈完成计算
List
<String> rpnList = getListString(suffixExpression);
System.out.println("rpnList" + rpnList);
int res = calculate(rpnList);
System.out.println("计算的结果是="+res);
}
//将一个逆波兰表达式，依次将(数据和运算符)【字符串】放入到ArrayList中
public static List
<String> getListString(String suffixExpression){
//将suffixExpression进行分割
String[] split = suffixExpression.split(" ");//将suffixExpression按照空格进行分割
List
<String> list = new ArrayList
<String>();//定义一个 ArrayList,存放切割后的字符
for (String ele : split){
list.add(ele);
}
return list;
}
/**
* 例如: (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，由此得出最终结果
*/
public static int calculate(List
<String> ls){
//创建栈，只需一个栈即可
Stack
<String> stack = new Stack<>();
//遍历ls
for (String item : ls){
//这里使用正则表达式来取出数
if (item.matches("\\d+")){//匹配的是多位数
// （\d：匹配一个数字字符；+：匹配前面的子表达式一次或多次）
//入栈
stack.push(item);
}else{
//pop出两个数并运算
int num2 = Integer.parseInt(stack.pop());//将字符串转成整数
int num1 = Integer.parseInt(stack.pop());
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("运算符有误");
}
//将res入栈
stack.push("" + res);//将整数转换成字符串
}
}
//最后留在stack中的数据是运算结果
return Integer.parseInt(stack.pop());
}
}
