从做到与运算，遇到优先级高的先进行
4 * 5 -8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
5 6 * 8 2 / + => 5 * 6 + 8 / 2
(3 + 4) * 6 + 7 * 3 => 3 4 + 6 * 7 3 * +
(3+4)*5-6
定义一个方法将传入的字符串进行分割,返回一个集合
/**
* TODO 将中缀表达式转为对应的list
* @param s 传入的字符串
* @return {@link List<String>}
*/
public static List<String> toInfixExpressionList(String s){
s = s.replaceAll("\\s+", "");
ArrayList<String> list = new ArrayList<>();
String regEx="\\d+(\\.\\d+)?|\\+|\\-|\\*|\\/|\\(|\\)";
Pattern p = Pattern.compile(regEx);
Matcher m = p.matcher(s);
while(m.find()){
list.add(m.group());
}
return list;
}
将中缀表达式转为逆波澜表达式
定义一个栈和一个集合
存放中间结果的栈:因为不需要pop操作所以不用栈，使用list替代
对传入的集合进行遍历，如果遍历的项是数字就直接加入到集合
如果遍历的项是“（”也直接加入到栈中
如果遍历的项是“）”就开始将栈中的数据进行弹出，并将弹出的数据添加到集合中，直到栈顶为“（”停止
停止之后还需要进行一次出栈操作，将栈中的“（”弹出
如果遍历的项是运算符，就要判断优先级，循环操作栈，如果栈顶的运算符的优先级大于或者等于遍历项的优先级就将栈顶的运算符加入到集合中，最后将便利项压入栈中
判断栈是否为空，如果不为空就将栈中的数据都加入到集合中
/**
* TODO 将中缀表达式转为逆波澜表达式
* @param list {@link List<String>}
* @return {@link List<String>}
*/
public static List<String> parseSuffixExpressionList(List<String> list){
// 初始化栈
// 符号栈
Stack<String> s1 = new Stack<>();
// 存放中间结果的栈:因为不需要pop操作所以不用栈，使用list替代
List<String> s2 = new ArrayList<>();
list.forEach(item -> {
if (item.matches("\\d+(\\.\\d+)?")) {
s2.add(item);
} else if ("(".equals(item)) {
s1.push(item);
} else if (")".equals(item)) {
while (!"(".equals(s1.peek())) {
s2.add(s1.pop());
}
// 将"("弹出s1栈
s1.pop();
} else {
// 当item的优先级<=s1栈顶优先级，将s1栈顶的运算符加入到s2中
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
// 将item压入栈
s1.push(item);
}
});
while (!s1.isEmpty()) {
s2.add(s1.pop());
}
return s2;
}
/**
* @ClassName Operation
* @Description TODO 返回一个运算符对应的优先级
* @Author Chole
* @Date 2020/4/1 13:54
*/
public class Operation {
private static final int ADD = 1;
private static final int SUB = 1;
private static final int MUL = 2;
private static final int DIV = 2;
public static int getValue(String operation){
int result = 0;
switch (operation) {
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
break;
}
return result;
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
?
/**
* @ClassName PolandCalculator
* @Description TODO 逆波兰计算器
* @Author Chole
* @Date 2020/4/1 11:10
*/
public class PolandCalculator {
?
public static void main(String[] args) {
String expression = "15.1+2-3*4-5+1";
List<String> strings = toInfixExpressionList(expression);
System.out.println(strings);
List<String> strings1 = parseSuffixExpressionList(strings);
System.out.println(strings1);
System.out.println(calcute(strings1));
?
?
}
?
/**
* TODO 将中缀表达式转为逆波澜表达式
* @param list {@link List<String>}
* @return {@link List<String>}
*/
public static List<String> parseSuffixExpressionList(List<String> list){
// 初始化栈
// 符号栈
Stack<String> s1 = new Stack<>();
// 存放中间结果的栈:因为不需要pop操作所以不用栈，使用list替代
List<String> s2 = new ArrayList<>();
list.forEach(item -> {
if (item.matches("\\d+(\\.\\d+)?")) {
s2.add(item);
} else if ("(".equals(item)) {
s1.push(item);
} else if (")".equals(item)) {
while (!"(".equals(s1.peek())) {
s2.add(s1.pop());
}
// 将"("弹出s1栈
s1.pop();
} else {
// 当item的优先级<=s1栈顶优先级，将s1栈顶的运算符加入到s2中
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
// 将item压入栈
s1.push(item);
}
});
?
while (!s1.isEmpty()) {
s2.add(s1.pop());
}
?
return s2;
}
?
/**
* TODO 将中缀表达式转为对应的list
* @param s 传入的字符串
* @return {@link List<String>}
*/
public static List<String> toInfixExpressionList(String s){
// 出去掉所有的空格
s = s.replaceAll("\\s+", "");
ArrayList<String> list = new ArrayList<>();
String regEx="\\d+(\\.\\d+)?|\\+|\\-|\\*|\\/|\\(|\\)";
Pattern p = Pattern.compile(regEx);
Matcher m = p.matcher(s);
while(m.find()){
list.add(m.group());
}
return list;
}
?
/**
* TODO 完成计算
* @param list 传入的List
* @return {@link int}
*/
public static double calcute(List<String> list) {
Stack<String> stack = new Stack<>();
list.forEach(item -> {
if (item.matches("\\d+(\\.\\d+)?")){
stack.push(item);
} else {
double num1 = Double.parseDouble(stack.pop());
double num2 = Double.parseDouble(stack.pop());
double res = 0;
if ("-".equals(item)) {
res = num2 - num1;
} else if ("+".equals(item)){
res = num2 + num1;
} else if ("*".equals(item)) {
res = num2 * num1;
} else if ("/".equals(item)) {
res = num2 / num1;
} else {
throw new RuntimeException("运算符有误");
}
stack.push("" + res);
}
});
return Double.parseDouble(stack.pop());
}
?
}
?
原文：https://www.cnblogs.com/renit/p/12614894.html