1、前缀表达式
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
// - × + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
将中缀表达式转换为前缀表达式
1.初始化两个栈:运算符栈s1，储存中间结果的栈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中的元素并输出，结果即为中缀表达式对应的前缀表达式
2、中缀表达式
中缀表达式就是常见的运算表达式
// (3+4)×5-6
3、后缀表达式
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
// 3 4 + 5 × 6 -
后缀表达式计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
将中缀表达式转换为后缀表达式
1.初始化两个栈：运算符栈s1和储存中间结果的栈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中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
中缀表达式转换为后缀表达式代码实现
@Test
public void convert() {
String expression = "( 3 + 4 ) * 5 - 6";
List<String> result = InfillToSuffix.convert(expression);
System.out.println(result);
}
//输出：[-, 6, *, 5, +, 4, 3]，其逆序即需要的后缀表达式
public class InfillToSuffix {
public static List<String> convert(String Infill) {
Stack<String> s1 = new Stack<String>();
Stack<String> s2 = new Stack<String>();
List<String> result = new ArrayList<String>();
String[] split = Infill.split(" ");
for (int i = 0; i < split.length; i++) {
if (split[i].matches("\\d+")) {
s2.push(split[i]);
} else if (split[i].equals("(")) {
s1.push(split[i]);
} else if (split[i].equals(")")) {
while (!s1.peek().equals("(")) {
s2.push(s1.pop());
}
s1.pop();
} else {
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(split[i])) {
s2.push(s1.pop());
}
s1.push(split[i]);
}
}
while (s1.size() != 0) {
s2.push(s1.pop());
}
while (s2.size() != 0) {
result.add(s2.pop());
}
return result;
}
}
public class Operation {
private static int ADDITION = 1; //加
private static int SUBTRACTION = 1; //减
private static int MULTIPLICATION = 2; //乘
private static int DIVISION = 2; //除
//返回对应优先级
public static int getValue(String operation) {
int result;
switch (operation) {
case "+":
result = ADDITION;
break;
case "-":
result = SUBTRACTION;
break;
case "*":
result = MULTIPLICATION;
break;
case "/":
result = DIVISION;
break;
default:
System.out.println("不存在该运算符");
result = 0;
}
return result;
}
}
