/*
中缀表达式转成后缀表达式 "12+((22+31)*4)-5" ==> 12 22 31 + 4 * + 5 -
第一步，将中缀表达式转成中缀字符串 list, 方便遍历 [12, +, (, (, 22, +, 31,), *, 4, ), -, 5]
第二步，将中缀字符串 list 转成后缀表达式对应的 list [12, +, (, (, 22, +, 31,), *, 4, ), -, 5] -> [12, 22, 31, +, 4, *, +, 5, -]
具体步骤：初始化两个栈，s1 运算符栈，s2 存储中间结果的栈
遍历中缀表达式字符串 list
若是数字，直接入栈 s2;
若是 "(", 直接入栈 s1;
若是 ")", 依次弹出符号栈 s1 的栈顶运算符，并入栈 s2，直到遇到左括号，将左括号再出栈，把一对括号消除掉;
若是操作符 (加减乘除), 比较它和 s1 栈顶操作符的优先级大小:
a. 若 s1 为空，或者栈顶运算符为 "(", 则直接将此运算符入栈；b. 否则，若其优先级比栈顶运算符的优先级高，也将此运算符入栈;
c. 否则，将 s1 栈顶的运算符弹出，并入栈到 s2 中，继续从 a 循环。遍历结束后，把 s1 中剩余的运算符依次弹出，并加入 s2。依次弹出 s2 中的元素，结果的逆序即为中缀表达式对应的后缀表达式。*/
public class InfixToPostfixDemo {
// 第 1 步. 将中缀表达式转成中缀字符串列表，方便遍历。// "12+((22+31)*4)-5" ==> [12, +, (, (, 22, +, 31,), *, 4, ), -, 5]
public List<String> toInfixList(String exp) {List<String> res = new ArrayList<>();
int i = 0;
// 保存遍历过程中产生的数字，连续的数字字符拼接成一个数
StringBuilder sb = new StringBuilder();
while (i < exp.length()) {if (!Character.isDigit(exp.charAt(i))) {res.add(exp.charAt(i) + ""); // 如果当前字符不是数字，直接加入结果
i++;
} else {sb.delete(0, sb.length());// 先清除
while (i < exp.length() && Character.isDigit(exp.charAt(i))) {sb.append(exp.charAt(i));
i++;
}
res.add(sb.toString());
}
}
return res;
}
// 第 2 步 将中缀表达式字符串列表，转成后缀表达式字符串列表.
// [12, +, (, (, 22, +, 31,), *, 4, ), -, 5] -> [12, 22, 31, +, 4, *, +, 5, -]
public List<String> toPostList(List<String> list) {Stack<String> s1 = new Stack<>(); // 符号栈
// 存储中间结果
List<String> s2 = new ArrayList<>(); // 在整个转换过程中，没有 pop 操作，在后面还要逆序输出，所以用 list 代替栈
for (String item : list) {if (item.matches("\\d+")) s2.add(item); // 如果是数字，加入 s2
else if (item.equals("(")) s1.push(item); // 如果是左括号，入栈 s1
else if (item.equals(")")) { // 如果是右括号，则依次弹出符号栈 s1 栈顶的运算符，并压入 s2，直到遇到左括号位置，将这一对括号消除掉
while (!s1.peek().equals("(")) {s2.add(s1.pop());
}
s1.pop(); // 丢弃左括号，继续循环，也就消除了一对括号} else { // 此时，遇到的是加减乘除运算符
// 当前操作符优先级 <=s1 的栈顶运算符的优先级，则将 s1 的运算符弹出，并加入到 s2 中
while (!s1.empty() && priority(s1.peek()) >= priority(item)) s2.add(s1.pop());
s1.push(item);
}
}
// 将 s1 中剩余的运算符依次弹出，并加入 s2
while (!s1.empty()) {s2.add(s1.pop());
}
return s2;
}
private int priority(String op) {if ("+".equals(op) || "-".equals(op)) return 1;
if ("*".equals(op) || "/".equals(op)) return 2;
return 0; // 如果是左括号返回 0
}
// 对后缀表达式字符串列表进行计算
public double calculatePoland(List<String> list) {Stack<Double> stack = new Stack<>();
for (String s : list) {
double n1, n2;
switch (s) {
case "*":
n1 = stack.pop();
n2 = stack.pop();
stack.push(n1 * n2);
break;
case "/":
n1 = stack.pop();
n2 = stack.pop();
stack.push(n2 / n1);
break;
case "+":
n1 = stack.pop();
n2 = stack.pop();
stack.push(n1 + n2);
break;
case "-":
n1 = stack.pop();
n2 = stack.pop();
stack.push(n2 - n1);
break;
default:
stack.push(Double.parseDouble(s));
break;
}
}
return stack.pop();}
public static void main(String[] args) {String exp = "12+((22+31)*4)-5";
InfixToPostfixDemo app = new InfixToPostfixDemo();
List<String> infixList = app.toInfixList(exp); // 第 1 步
List<String> postList = app.toPostList(infixList); // 第 2 步
double res = app.calculatePoland(postList); // 第 3 步
System.out.println(infixList);
System.out.println(postList);
System.out.println(res);
}
}