参考链接
结合原文章，做了一定修改，增加Java源码实现
1. 概述
对于四则运算表达式的计算，是输入数据结构中栈的应用，即重点是中缀表达式转换为后缀表达式
2. 后缀表达式计算
- 为了解释后缀表达式的好处，我们先来看看，计算机是如何计算后缀表达式的
- 后缀表达式实例
9 3 1 - 3 * + 10 2 / + - 计算规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行计算，然后计算结果进栈，一直到最终获得结果。
-
计算过程：
imageimage
image
image
3. 中缀表达式转后缀表达式
我们把平时标准的四则运算表达式比如
9+(3-1)*3+10/2叫做中缀表达式。
中缀表达式：9+(3-1)*3+10/2转换后缀表达式9 3 1 - 3 * + 10 2 / +
- 转换规则：
- 当当前字符为
数字时，直接输出； - 当当前字符为
(时，将其压栈； - 当当前字符为
)时，则弹出堆栈中最上的(之前的所有运算符并输出，然后删除堆栈中的(； - 当当前字符为运算符时，则依次弹出堆栈中优先级
大于等于当前运算符的(到”(“之前为止)，输出，再将当前运算符压栈；
最后弹出所有栈中的内容输出
-
转换过程
image
image
image
image
image
4. 源代码实现
package data_structure;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* 栈的应用
* https://blog.csdn.net/u011857433/article/details/79993385
* 四则运算表达式求职，中缀表达式与后缀表达式转换
*/
public class ReversePoland {
public static void main(String[] args) {
// Calculation1("9 3 1 - 3 * + 10 2 / +");
System.out.println(Calculation2("9 + ( 3 - 1 ) * 3 + 10 / 2"));
}
/**
* 计算后缀表达式
* @param inputString 9 3 1 - 3 * + 10 2 / + 以空格分隔
*/
public static int Calculation1(String inputString){
String[] input = inputString.split(" ");
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < input.length; i++) {
String s = input[i];
if (isNumber(s)) //如果是数字，则入栈
stack.push(Integer.valueOf(s));
else {
//遇到运算符，则从栈中弹出两个数字，进行运算
int n1 = stack.pop();
int n2 = stack.pop();
int res = 0;
switch (s){
case "+":res = n1 + n2;break;
case "-":res = n2 - n1;break;
case "*":res = n1 * n2;break;
case "/":res = n2 / n1;break;
}
stack.push(res);
}
}
return stack.pop();
}
/**
* 将中缀表达式转化为后缀表达式
* @param string 9 + ( 3 - 1 ) * 3 + 10 / 2
* @return
*/
public static String Calculation2(String string){
Stack<String> stack = new Stack();
String[] chars = string.split(" ");
String res = "";
for (int i = 0; i < chars.length; i++) {
String s = String.valueOf(chars[i]);
if (isNumber(s)){
if (res.length()==0)
res += s;
else
res += " "+s;
}else {
if (s.equals("(")){
stack.push(s);
}else {
if (s.equals(")")){
String t = "";
String s1 = "";
while (!(t = stack.pop()).equals("(")){
s1 += " "+t;
}
res += s1;
}else {
int priority = getPriority(s);
String s1 = "";
boolean flag = false;
while (!stack.empty()){
flag = false;
s1 = stack.pop();
if (s1.equals("(")){
// stack.push("(");
break;
}
if (getPriority(s1) >= priority){
res += " " + s1;
flag = true;
}
}
if (!s1.equals("") && !flag)
stack.push(s1);
stack.push(s);
}
}
}
}
while (!stack.empty()){
res += " " + stack.pop();
}
return res;
}
//获取运算符的优先级
public static int getPriority(String s){
Map<String,Integer> map = new HashMap<>();
map.put("+",0);
map.put("-",0);
map.put("*",1);
map.put("/",1);
map.put("(",2);
map.put(")",2);
return map.get(s);
}
public static boolean isNumber(String c){
Pattern pattern = Pattern.compile("^(0|[1-9][0-9]*)$");
Matcher matcher = pattern.matcher(c);
boolean res = matcher.find();
return res;
}
}
