完成一个逆波兰计算器，需求如下：
-
输入一个 逆波兰表达式，使用栈 Stack（JDK 自带），计算器结果
-
支持 小括号 和 多位数
主要这里是讲解数据结构，因此简化为只对整数计算
关于前缀、中缀、后缀表达式可以去看我的这篇博文数据结构与算法——栈（三）有关栈的三种表达式 —— 前缀、中缀、后缀表达式
注意咯：知道逆波兰表达式是什么后，相对来说，实现还是比较容易的，难点其实是在于中缀表达式如何转换为后缀表达式，因为这涉及到运算符的优先级问题。在前面我们实现的时候，其实就是这个运算符优先级问题很刺手。而前缀、后缀表达式里面表达式的优先级，在形成这个表达式时就已经确定了。关于中缀表达式转为后缀表达式的详细讲解请看后续博客。
这里为什么使用 JDK 自带的Stack呢，其实在实现中缀表达式的计算器时，博客中数据结构与算法——栈（二）【使用栈来实现综合计算器-中缀表达式】是把计算器相关运算和方法都放在栈类中的，这只是为了方便操作数据，最终目的还是为了能让我们理解栈这个数据结构，所以实际上，只是利用了栈的数据结构，并非是什么都需要写在栈中的。
实现思路：从前面后缀表达式求值过程来看，由于没有了优先级问题，全程只是在顺序获取元素，然后进行计算。
- 先将后缀表达式转成一个 List（这里的后缀表达式中的数字和运算符用空格隔开，具体看代码，只是为了方便解析来添加集合元素）
- 对这个 List 进行遍历，然后利用栈进行计算
public class ReversePolishCalculator {
public static void main(String[] args) {
ReversePolishCalculator calculator = new ReversePolishCalculator();
// (3+4)*5-6 => 对应的后缀表达式 `3 4 + 5 * 6 -` 用空格作为分隔符
String postfixExpression = "3 4 + 5 * 6 -";
System.out.println("(3+4)*5-6 = " + calculator.cal(postfixExpression));
// (30+4)*5-6 => 对应的后缀表达式 `30 4 + 5 * 6 -`
postfixExpression = "30 4 + 5 * 6 -";
System.out.println("(30+4)*5-6 = " + calculator.cal(postfixExpression));
// 4*5-8+60+8/2 => 对应的后缀表达式 `4 5 * 8 - 60 + 8 2 / +`
postfixExpression = "4 5 * 8 - 60 + 8 2 / +";
System.out.println("4*5-8+60+8/2 = " + calculator.cal(postfixExpression));
// (3+4)-(3-4)*10，对应后缀表达式为：3 4 + 10 3 4 - * -
postfixExpression = "3 4 + 10 3 4 - * -";
System.out.println("(3+4)-(3-4)*10 = " + calculator.cal(postfixExpression));
}
/**
* 计算一个后缀表达式的值
*
* @param postfixExpression
* @return
*/
public int cal(String postfixExpression) {
return start(convert(postfixExpression));
}
/**
* 将后缀表达式转换成 list
* @param postfixExpression
* @return
*/
private List<String> convert(String postfixExpression) {
//表达式中的每个元素都用空格隔开，是为了方便；这里重点不在于怎么去解析出每一个元素了
return Arrays.asList(postfixExpression.split(" "));
}
/**
* 遍历集合元素，并利用栈对其计算
*
* @param postfixElements
* @return
*/
private int start(List<String> postfixElements) {
/*
比如：`(3+4)x5-6` 对应的后缀表达式 `3 4 + 5 x 6 -`
1. 从左到右扫描，将 3、4 压入堆栈
2. 扫描到 `+` 运算符时
将弹出 4 和 3，计算 `3 + 4 = 7`，将 7 压入栈
3. 将 5 入栈
4. 扫描到 `x` 运算符时
将弹出 5 和 7 ，计算 `7 x 5 = 35`，将 35 入栈
5. 将 6 入栈
6. 扫描到 `-` 运算符时
将弹出 6 和 35，计算 `35 - 6 = 29`，将 29 压入栈
7. 扫描表达式结束，29 是表达式的值
*/
Stack<Integer> stack = new Stack<>();//jdk提供的Stack
for (String el : postfixElements) {
// 如果是数字则入栈
if (el.matches("\\d+")) {
stack.push(Integer.parseInt(el));
continue;
}
// 如果是运算符，则弹出两个数
Integer num2 = stack.pop();
Integer num1 = stack.pop();
int res = cal(num1, num2, el.charAt(0)); //计算
stack.push(res);//将计算好的数压入栈中
}
return stack.pop();//当前栈中只有一个数，即最终结果
}
/**
* 计算
*
* @param num1 次顶的数
* @param num2 栈顶的数
* @param oper 运算符
* @return
*/
private int cal(int num1, int num2, char oper) {
switch (oper) {
case ‘+‘:
return num1 + num2;
case ‘-‘:
return num1 - num2;
case ‘*‘:
return num1 * num2;
case ‘/‘:
return num1 / num2;
}
throw new IllegalArgumentException("不支持的运算符：" + oper);
}
}
测试输出
(3+4)*5-6 = 29
(30+4)*5-6 = 164
4*5-8+60+8/2 = 76
(3+4)-(3-4)*10 = 17