它们的区别在于操作符与操作数之间的位置关系，对于前缀和后缀表达式语法上不需要括号也能无歧义的解析求得结果，对于计算机来说，在没有括号的情况下运算更加简单，所以在求解表达式问题时通常把中缀表达式转化为前缀或后缀表达式之后再进行运算。主要用到的算法有调度场算法
对于中缀表达式到前缀表达式或者后缀表达式的转换在平常做数据结构题目的时候经常会碰到，通过合理运用栈进行操作，将能够帮助我们高效完成中缀表达式的计算过程，逻辑思路清晰。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
private Stack<String> operator = new Stack<>(); //操作符栈
private Stack<String> result = new Stack<>(); //结果运算栈
private List<String> prefix = new ArrayList<>(); //前缀表达式集合
private List<String> infix = new ArrayList<>(); //中缀表达式集合
private List<String> postifx = new ArrayList<>(); //后缀表达式集合
/**
* 构造函数 传入中缀表达式 进行初始化处理
* @param string
*/
public Main(String string) {
string = string.replaceAll(" ", "");
string = string.replaceAll("×", "*");
//将string把它通过操作符号分开 并放入到中缀表达式的List中
StringTokenizer tokenizer = new StringTokenizer(string, "+-*/()", true);
while (tokenizer.hasMoreElements()) {
infix.add(tokenizer.nextToken());
}
}
/**
* 转变成前缀式
* @return
*/
private List<String> convertPrefix() {
operator.clear();
for (int i = infix.size() - 1; i >= 0; i--) {
if (isNumber(infix.get(i))) {
prefix.add(infix.get(i));
} else if (isOperate(infix.get(i))) {
getPrefix(infix.get(i));
} else {
System.out.println("illegal!!!");
}
}
while (!operator.empty()) {
prefix.add(operator.pop());
}
Collections.reverse(prefix);
return prefix;
}
/**
* 转变成后缀式
* @return
*/
private List<String> convertPostifx() {
operator.clear();
for (String string : infix) {
if (isNumber(string)) {
postifx.add(string);
} else if (isOperate(string)) {
getPostifx(string);
} else {
System.out.println("illegal!!!");
}
}
while (!operator.empty()) {
postifx.add(operator.pop());
}
return postifx;
}
/**
* 获取前缀表达式
* @param string
*/
private void getPrefix(String string) {
if (operator.empty() || string.equals(")")) {
operator.push(string);
} else if (string.equals("(")) {
String tmp;
while (!(tmp = operator.pop()).equals(")")) {
prefix.add(tmp);
}
} else if (operator.peek().equals(")") || comparePriority(string, operator.peek())) {
operator.push(string);
} else {
prefix.add(operator.pop());
getPrefix(string);
}
}
/**
* 获取后缀表达式
* @param string
*/
private void getPostifx(String string) {
if (operator.empty() || string.equals("(")) {
operator.push(string);
} else if (string.equals(")")) {
String tmp;
while (!(tmp = operator.pop()).equals("(")) {
postifx.add(tmp);
}
} else if (operator.peek().equals("(") || comparePriority(string, operator.peek())) {
operator.push(string);
} else {
postifx.add(operator.pop());
getPostifx(string);
}
}
/**
* 计算前缀式的值
* @return
*/
private String calculatePrefix() {
Collections.reverse(prefix);
result.clear();
for (String string : prefix) {
if (isNumber(string)) {
result.push(string);
} else if (isOperate(string)) {
int val1 = Integer.parseInt(result.pop());
int val2 = Integer.parseInt(result.pop());
if (string.equals("*")) {
result.push(String.valueOf(val1 * val2));
}else if (string.equals("/")) {
result.push(String.valueOf(val1 / val2));
}else if (string.equals("+")) {
result.push(String.valueOf(val1 + val2));
}else if (string.equals("-")) {
result.push(String.valueOf(val1 - val2));
}
}
}
return result.pop();
}
/**
* 计算后缀式的值
* @return
*/
private String calculatePostifx() {
result.clear();
for (String string : postifx) {
if (isNumber(string)) {
result.push(string);
} else if (isOperate(string)) {
int val2 = Integer.parseInt(result.pop());
int val1 = Integer.parseInt(result.pop());
if (string.equals("*")) {
result.push(String.valueOf(val1 * val2));
}else if (string.equals("/")) {
result.push(String.valueOf(val1 / val2));
}else if (string.equals("+")) {
result.push(String.valueOf(val1 + val2));
}else if (string.equals("-")) {
result.push(String.valueOf(val1 - val2));
}
}
}
return result.pop();
}
private boolean isNumber(String num) {
return num.matches("\\d+");
}
private boolean isOperate(String op) {
return op.matches("[\\+\\*\\/\\(\\)-]");
}
private boolean comparePriority(String op1, String op2) {
return getPriority(op1) > getPriority(op2);
}
private int getPriority(String string) {
if (string.equals("+") || string.equals("-")) {
return 1;
}
if (string.equals("*") || string.equals("/")) {
return 2;
}
if (string.equals("(") || string.equals(")")) {
return 3;
}
return -1;
}
public static void main(String[] args) {
Main main = new Main("1+((2-3)*(4+5))+((6/2))");
List<String> list1 = main.convertPrefix();
List<String> list2 = main.convertPostifx();
System.out.print("前缀表达式为：");
for (String s : list1) {
System.out.print(s + " ");
}
System.out.print('\n' + "后缀表达式为：");
for (String s : list2) {
System.out.print(s + " ");
}
System.out.print('\n' + "前缀表达式计算结果为：" + main.calculatePrefix());
System.out.print('\n' + "后缀表达式计算结果为：" + main.calculatePostifx());
}
}