前序表达式 中序表达式 后序表达式
中序表达式：
中序表达式就是我们日常使用的表达式,由左往右阅读，结构清晰，但需要括号改变优先级，对计算机不友好
eg: (1+4)*3+10/5
前序表达式（波兰表示法Polish notation，或波兰记法）：
一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析，不需要括号来改变优先级，未推广使用。
eg:
中序表达式：(1 + 4) * 3 + 10 / 5
前序表达式： + * + 1 4 3 / 10 5
前序表达式的运算：
eg:
+ * + 1 4 3 / 6 5
运算： + 1 4 => 1 + 4 = 5
* 5 3 => 5 * 3 = 15
新前序： + 15 / 10 5
/ 10 5 => 10 / 5 =2
新前序： + 15 2
=> 15 + 2 = 17 后序表达式（逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法）：
所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级，使用广泛。艾兹格·迪科斯彻引入了调度场算法，用于将中缀表达式转换为后缀形式。因其操作类似于火车编组场而得名。 大多数操作符优先级解析器(解析器用简单的查表操作即可实现，优先级表由开发者自己定制，在不同的应用场景中，开发者可自由改变操作符的优先级)能转换为处理后缀表达式，实际中，一般构造抽象语法树，树的后序遍历即为逆波兰记法。
eg:
中序表达式：(1 + 4) * 3 + 10 / 5
后序表达式： 1 4 + 3 * 10 5 / +
后序表达式的运算：
eg:
1 4 + 3 * 10 5 / +
运算： 1 4 + => 1 + 4 = 5
5 3 * => 5 * 3 = 15
新后序： 15 / 10 5 +
10 5 / => 10 / 5 =2
新后序： 15 2 +
=> 15 + 2 = 17 中序转后序（调度场算法）
- 创建一个队列和一个操作数栈
- 遇到操作数则送入队列
- 遇到操作符则送入栈
- 遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
- 遇到” ）“括号则将栈内从”（ “到” ）“的所有操作符全部取出送入队列
- 表达式分类完成后，先输出队列内容，再输出栈内容，前者+后者便是后序表达式
实现代码（Java版）：
package chapter1_3;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
import edu.princeton.cs.algs4.Queue;
//这个是《算法》里的队列定义包,因为Java里的queue只是一个接口，需要继承重写，这里就懒得麻烦了
/**
* @author : jeasion
* @name
* @comment
*这里先把表达式转换成数组，使操作数和操作符分离，然后进行转换操作
* @return
*/
public class practice10 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入表达式：");
String s = scanner.next();
String[] num = split(s);
s = InfixToPostfix(num);
System.out.println("后序表达式：" + s);
}
public static String[] split(String s) {
String[] nums = s.split("\\+|\\-|\\*|\\/|\\(|\\)");
Queue<String> queue = new Queue<String>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/'
|| s.charAt(i) == '(' || s.charAt(i) == ')') {
queue.enqueue(s.charAt(i) + "");
}
}
ArrayList<String> arrayList = new ArrayList<String>();
String string = queue.dequeue();
if (string.equals("(")) {
arrayList.add(string);
} else
queue.enqueue(string);
for (int i = 0; i < nums.length; i++) {
if (nums[i].equals("")) {
continue;
}
arrayList.add(nums[i]);
if (!queue.isEmpty()) {
string = queue.dequeue();
arrayList.add(string);
if (string.equals(")")) {
string = queue.dequeue();
arrayList.add(string);
}
}
}
String[] res = new String[arrayList.size()];
for (int i = 0; i < arrayList.size(); i++) {
res[i] = arrayList.get(i);
}
System.out.println("表达式转字符串数组:" + arrayList.toString());
return res;
}
public static String InfixToPostfix(String[] s) {
Stack<String> stack = new Stack<String>();
Queue<String> queue = new Queue<String>();
String s1 = "";
for (int i = 0; i < s.length; i++) {
// 如果碰到右括号则遍历栈，并送入队列，直到碰到"("
if (s[i].equals(")")) {
s1 = stack.pop();
while (!s1.equals("(")) {
queue.enqueue(s1);
s1 = stack.pop();
}
continue;
}
// 如果碰到左括号则送入栈
if (s[i].equals("(")) {
stack.push(s[i]);
continue;
}
// 遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
if (s[i].equals("+") || s[i].equals("-")) {// 碰到"+"或 "-"运算符，则进行栈操作
if (stack.isEmpty()) {// 如果栈为空，则直接入栈
stack.push(s[i]);
continue;
}
while (!stack.isEmpty() && !stack.peek().equals("(")) {
queue.enqueue(stack.pop());
}
stack.push(s[i]);
continue;
}
boolean operat = s[i].equals("*") || s[i].equals("/"); // 运算符是乘除
if (operat && stack.isEmpty()) {// 如果栈为空，则直接入栈
stack.push(s[i]);
continue;
}
if (operat) {// 乘除的运算符只能弹出乘除运算符
boolean peek = stack.peek().equals("*") || stack.peek().equals("/"); // 栈里面的运算符也是乘除
while (!stack.isEmpty() && peek) {
queue.enqueue(stack.pop());
}
stack.push(s[i]);
continue;
}
// 剩下的操作数，送入队列
queue.enqueue(s[i]);
}
String res = "";// 初始化s来接收表达式
// 接收队列的值
do {
res += queue.dequeue() + " ";
} while (!queue.isEmpty());
// 接受栈的值
do {
res += stack.pop() + " ";
} while (!stack.isEmpty());
return res;
}
}
