本文是学习B站韩顺平老师的数据结构与算法课程的笔记。关于中缀表达式转逆波兰表达式的代码，和老师的不一样，自己按照思路实现的。思路比较清晰，如果看老师的代码有点懵逼的话，可以参考本文的代码，个人感觉还是非常容易理解的(初步测试通过，不敢保证没bug，若发现bug请留言，谢谢)。
一、是什么
如果要你实现一个计算器程序，会怎么做？即用户输入一串字符串，比如4 * 5 - 8 + 60 + 8 / 2，你会怎么计算这个操作结果？
要想实现这个功能，我们可以定义两个栈，一个用来存放数字，一个用来存放操作符。遍历字符串，如果遍历到的字符是数字，存入存放数字的栈；如果遍历到的字符是操作符，那么先判断存放操作符的栈中是否已经有操作符了，没有就直接入栈，有的话，先比较当前操作符和栈中操作符的优先级，如果当前操作符优先级高于符号栈的操作符，直接入符号栈；如果当前操作符优先级小于或等于栈中的操作符，那就从数字栈中pop出两个数字，从操作符栈pop出操作符，进行计算，将计算后结果再入数字栈，同时将当前操作符入操作符栈；当字符串遍历完了后，pop出数字栈的数字，即为最后的运算结果。
这个4 * 5 - 8 + 60 + 8 / 2字符串，就叫中缀表达式，对我们人来说，中缀表达式是符合习惯的，也是好理解的，但是对于计算机而言，就不太友好，因为计算的时候要去判断操作符的优先级。有一种叫后缀表达式的，也叫逆波兰表达式，对计算机就十分友好，不需要判断优先级就可以计算。比如4 * 5 - 8 + 60 + 8 / 2对应的逆波兰表达式就是4 5 * 8 - 60 + 8 2 / +。
欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
二、中缀表达式转逆波兰表达式
1、分析：
从上面的转换可以看出，逆波兰表达式是已经按照运算符优先级排列了。首先是 4 * 5，所以逆波兰表达式是4 5 *，表示4和5做乘法运算；然后减8，所以是8 -，表示和8做减法运算；再然后是60 +，表示和60做加法；然后是8 2 /，表示8和2相除；最后是一个加号，表示8和2相除的结果再与之前的计算结果相加。
2、中缀转逆波兰表达式思路：
看了上面的分析，人脑肯定是一下子就学会了，但是通过程序要怎么转？思路如下：
(1). 初始化两个栈，numStack用来存放中间计算步骤的结果，symbolStack用来存放操作符；
(2). 从左到右，遍历中缀表达式；
(3). 如果遍历到的是数字，push进numStack；
(4). 如果遍历到的是操作符，比较与symbolStack栈顶操作符的优先级：
- 如果symbolStack为空，直接入栈；
- 如果symbolStack栈顶是左括号，也直接入栈，
- 如果当前操作符优先级高于栈顶操作符(左括号优先级高于加减乘除)，也直接入栈；
- 如果当前操作符优先级小于等于栈顶操作符，就将symbolStack栈顶的操作符pop出，push到numStack中，然后再重复步骤(4)，让当前操作符与symbolStack栈新的栈顶元素比较；
(5). 如果遇到右括号，则循环将symbolStack栈顶运算符pop出，push进numStack，直到遇到左括号为止，此时将这一对括号丢弃；
(6). 重复步骤(2)至步骤(5)，直到将表达式遍历完；
(7). 将symbolStack栈中剩余的元素依次pop出并push到numStack中；
(8). 将numStack中的元素依次pop出，结果的逆序就是该中缀表达式的逆波兰表达式。
3、代码实现：
public class StackUtil {
private StackUtil() {}
/**
* 中缀表达式转逆波兰表达式
*/
public static String getReversePolandStr(String inPerffixStr) {
Stack<String> numStack = new Stack<>();
Stack<String> symbolStack = new Stack<>();
List<String> list = splitStr(inPerffixStr);
for (String string : list) {
if (isNumber(string)) { // 数字直接入numStack栈，这里就是步骤三
numStack.push(string);
} else if (")".equals(string)) { // 遇到右括号进行步骤五
step5(string, numStack, symbolStack);
} else { // 遇到非数字非右括号的，进行步骤四
step4(string, numStack, symbolStack);
}
}
step7(numStack, symbolStack);
return step8(numStack);
}
/**
* 步骤八
* @return
*/
private static String step8(Stack<String> numStack) {
StringBuilder result = new StringBuilder();
List<String> tempList = new ArrayList<>();
while (!numStack.isEmpty()) {
tempList.add(numStack.pop());
}
for (int i=tempList.size()-1; i>=0; i--) {
result.append(tempList.get(i)).append(" ");
}
return result.substring(0, result.length() - 1).toString();
}
/**
* 步骤七
* @param numStack
* @param symbolStack
*/
private static void step7(Stack<String> numStack, Stack<String> symbolStack) {
while (!symbolStack.isEmpty()) {
numStack.push(symbolStack.pop());
}
}
/**
* 步骤五
* @param string
* @param numStack
* @param symbolStack
*/
private static void step5(String string, Stack<String> numStack, Stack<String> symbolStack) {
String symbol = "";
while(!symbol.equals("(")){
symbol = symbolStack.pop();
if ("(".equals(symbol)) {
break;
}
numStack.push(symbol);
}
}
/**
* 步骤四
* @param string
* @param numStack
* @param symbolStack
*/
private static void step4(String string, Stack<String> numStack, Stack<String> symbolStack) {
if (symbolStack.isEmpty() || symbolStack.peek().equals("(")) {
symbolStack.push(string);
} else if (isSuperior(string, symbolStack.peek())) {
symbolStack.push(string);
} else {
String top = symbolStack.pop();
numStack.push(top);
step4(string, numStack, symbolStack);
}
}
/**
* 判断str1的优先级是否高于str2
* @param str1
* @param str2
* @return
*/
private static boolean isSuperior(String str1, String str2) {
String level0 = "(";
String level1 = "*/";
String level2 = "+-";
if (level0.contains(str1) && (level1.contains(str2) || level2.contains(str2))) {
return true;
} else if (level1.contains(str1) && level2.contains(str2)){
return true;
} else {
return false;
}
}
/**
* 传入一个中缀表达式，将其数字和符号一个个的分割开来
* 例如传入的是：4.2*5.56-8+60+8.4/2.1
* 输出的应该是：[4.2, *, 5.56, -, 8, +, 60, +, 8.4, /, 2.1]
* @param inPerffixStr
* @return
*/
private static List<String> splitStr(String inPerffixStr){
inPerffixStr = inPerffixStr.replaceAll(" ", "");
List<String> strList= new ArrayList<>();
if (StringUtils.isBlank(inPerffixStr)) {
return strList;
}
char[] chars = inPerffixStr.toCharArray();
StringBuilder numBuilder = new StringBuilder();
// 如果是小数点和数字，那就拼接起来，直到下一次遍历到的不是小数点或数字时，
// 就将上一次的拼接结果存到集合中，同时清空拼接的StringBuilder，并把本次遍历到的符号也存到集合中，
// 别忘了最后一个数字，需要单独处理
for (int i=0; i<chars.length; i++) {
if(String.valueOf(chars[i]).equals(".")) {
numBuilder.append(chars[i]);
} else if (isNumber(String.valueOf(chars[i]))) {
numBuilder.append(chars[i]);
} else {
strList.add(numBuilder.toString());
numBuilder.delete(0, numBuilder.length());
strList.add(String.valueOf(chars[i]));
}
if (i == chars.length - 1 && numBuilder.length() > 0) {
strList.add(numBuilder.toString());
}
}
return strList;
}
/**
* 判断传入的字符串是否是数字
* @param str
* @return
*/
private static boolean isNumber(String str) {
Pattern pattern = Pattern.compile("^(\\-|\\+)?\\d+(\\.\\d+)?$");
Matcher match = pattern.matcher(str);
return match.find();
}
// 预期：4 5 * 8 - 60 + 8 2 / +
public static void main(String[] args) {
String str = "4*5-8+60+8/2";
//String str = "1+(3-2)*4"; // 1 3 2 - 4 * +
System.out.println(getReversePolandStr(str));
}
}
三、计算逆波兰表达式的结果
1、思路：
- 创建一个栈，用来存放数字；
- 遍历逆波兰表达式，如果是数字，直接入栈；
- 如果是符号，从栈中pop出两个数，做相应的计算，将结果再入栈；
- 最后从栈中pop出来的就是最终结果。
2、代码实现：
public class Calculator {
/**
* 传入一个中缀表达式，计算结果
*
* @param expression
* @return
*/
public static String calculate(String inPerffixStr) {
// 1. 获取逆波兰表达式
String reversePoland = StackUtil.getReversePolandStr(inPerffixStr);
// 2. 将字符串转成数组
String[] strArr = reversePoland.split(" ");
// 3. 创建一个栈，用来存数字
Stack<String> numStack = new Stack<>();
// 4. 遍历数组，如果是数字，直接入栈，如果是符号，就从栈中pop出两个数进行计算，计算结果再入栈
for (String str : strArr) {
if (StackUtil.isNumber(str)) {
numStack.push(str);
} else {
String num1 = numStack.pop();
String num2 = numStack.pop();
numStack.push(calculate(num1, num2, str));
}
}
return numStack.pop();
}
/**
* @param num1
* @param num2
* @param str
* @return
*/
private static String calculate(String num1, String num2, String str) {
String result = "";
Double doubleNum1 = Double.valueOf(num1);
Double doubleNum2 = Double.valueOf(num2);
switch (str) {
case "+":{
result = String.valueOf((doubleNum1.doubleValue() + doubleNum2.doubleValue()));
break;
}
case "-":{
result = String.valueOf((doubleNum2.doubleValue() - doubleNum1.doubleValue()));
break;
}
case "*":{
result = String.valueOf((doubleNum1.doubleValue() * doubleNum2.doubleValue()));
break;
}
case "/":{
result = String.valueOf((doubleNum2.doubleValue() / doubleNum1.doubleValue()));
break;
}
}
return result;
}
public static void main(String[] args) {
String str = "4*(5-2)/2+3";
System.out.println(calculate(str));
}
}
