中缀表达式转后缀表达式思路： 1.初始化一个运算符栈s1和存储中间结果的List集合s2； 2.从左至右扫描中缀表达式（这里为了方便把中缀表达式字符串依次存放到数组中）; 3.遇到操作数时，将其加到s2； 4.遇到运算符时，比较其与s1栈顶运算符的优先级： 4.1.若s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈 4.2.若优先级比栈顶运算符优先级高，也将运算符压入s1； 4.3.否则，将s1栈顶的运算符弹出并加到s2中，再次回到4.1与s1中新的栈顶运算符相比较 5.遇到括号时： 5.1.若是左括号“（”，则直接压入s1； 5.2.若是右括号“）”，则依次弹出s1栈顶运算符并加入s2，直到遇左括号为止，此时将这一对括号丢弃； 6.重复2-5，直到表达式最右边 7.将s1中剩余的运算符依次弹出并加入到s2 8.依次输出s2中的元素，结果即为中缀表达式对应的后缀表达式。
代码语言：javascript复制//将中缀表达式转换为后缀表达式并求值
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class InversePolishExpression {
public static void main(String[] args) {
//完成一个将中缀表达式转换为后缀表达式的功能
//直接对str不好操作，因此将str存放到list中并转换为后缀的list
String expression = "10 ((21 3)*4)-50";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println(infixExpressionList);
List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
System.out.println(suffixExpressionList);
int result = PolandExpression.calculate(suffixExpressionList);
System.out.println(result);
}
//方法：将中缀表达式转成对应的List
public static List<String> toInfixExpressionList(String s) {
//定义一个list存放中缀表达式的内容
List<String> ls = new ArrayList<String>();
int i = 0; //这是一个指针，完成对中缀表达式字符串的遍历
String str; //完成对多位数的拼接
char c; //每遍历一个字符就放到c中
do {
//如果c是一个非数字，就加到ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" c);
i ;
} else { //如果是一个数需要考虑多位数
str = ""; //先将str置空
while(i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
str = c;
i ;
}
ls.add(str);
}
} while(i < s.length());
return ls;
}
//ArrayList [1, ,(,(,2, ,3,),*,4,),-,5] =》 ArrayList[1,2,3, ,4,*, ,5,–]
//方法：将中缀表达式对应的list转换为后缀对应的list
public static List<String> parseSuffixExpressionList(List<String> ls) {
//定义两个栈
Stack<String> s1 = new Stack<String>(); //符号栈
//因为在整个运算过程中第二个栈都没有发生弹栈操作，而且最终弹出该栈元素要逆序输出，故将s2实现为链表
List<String> s2 = new ArrayList<String>(); //存储中间结果
//遍历ls
for(String item: ls) {
if(item.matches("-?\d ")) {
s2.add(item);
} else if(item.equals("(")) {
s1.push(item);
} else if(item.equals(")")) {
//如果是右括号，则依次弹出s1栈顶运算符并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
while(!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop(); //将(弹出s1栈，消除一对小括号
} else {
//当item运算符的优先级小于等于s1的栈顶运算符，将s1栈顶的运算符弹出并压入s2中，再次与s1中
// 新的栈顶运算符相比较
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
s1.push(item);
}
}
//将s1中剩余的运算符依次弹出并压入s2
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
}后缀表达式求值思路： 从左向右扫描表达式，遇到数字将数字压入数栈，遇到运算符弹出栈顶的两个数，用运算符对他们进行相应的计算并将结果入栈；重复上述过程直到表达式最右端，最后得出的值即为表达式结果（后缀表达式的剑法和除法运算是栈底元素- or / 栈顶元素）。
代码语言：javascript复制 public static int calculate(List<String> l) {
Stack<String> stack = new Stack<String>();
for (String item : l) {
//使用正则表达式取数
if (item.matches("-?\d ")) { //匹配的是多位数
stack.push(item);
} else {
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int res = 0;
if(item.equals(" ")) {
res = num2 num1;
} else if(item.equals("-")) {
res = num2 - num1;
} else if(item.equals("*")) {
res = num2 * num1;
} else if(item.equals("/")) {
res = num2 / num1;
} else {
throw new RuntimeException("运算符有误");
}
stack.push("" res);
}
}
return Integer.parseInt(stack.pop());
}还需要一个比较运算符优先级的方法
代码语言：javascript复制public class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
public static int getValue(String operation) {
int res = 0;
switch (operation) {
case " ":
res = ADD;
break;
case "-":
res = SUB;
break;
case "*":
res = MUL;
break;
case "/":
res = DIV;
break;
default:
break;
}
return res;
}
}运行结果：
