前序表达式 中序表达式 后序表达式

中序表达式：

中序表达式就是我们日常使用的表达式,由左往右阅读，结构清晰，但需要括号改变优先级，对计算机不友好

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  

中序转后序（调度场算法）

1. 创建一个队列和一个操作数栈
2. 遇到操作数则送入队列
3. 遇到操作符则送入栈
4. 遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
5. 遇到” ）“括号则将栈内从”（ “到” ）“的所有操作符全部取出送入队列
6. 表达式分类完成后，先输出队列内容，再输出栈内容，前者+后者便是后序表达式

实现代码（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;
	}
}