/*
中缀表达式转成后缀表达式 "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 toInfixList(String exp) {
List 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 toPostList(List list) {
Stack s1 = new Stack<>(); // 符号栈
// 存储中间结果
List 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 list) {
Stack 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 infixList = app.toInfixList(exp); // 第1步
List postList = app.toPostList(infixList); // 第2步
double res = app.calculatePoland(postList); //第3步
System.out.println(infixList);
System.out.println(postList);
System.out.println(res);
}
}
