概念

前缀表达式(Prefix Notation)是指将运算符写在前面、操作数写在后面、不包含括号的表达式，而且为了纪念其发明者波兰数学家Jan Lukasiewicz所以前缀表达式也叫做波兰表达式。比如- 1 + 2 3

后缀表达式(Postfix Notation)与之相反，是指运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。比如1 2 3 + -

中缀表达式(Infix Notation)就是我们数学课上学到的最常见的将操作符放在操作数中间的算术表达式。

前后缀表达式的出现是为了方便计算机处理，它的运算符是按照一定的顺序出现，所以求值过程中并不需要使用括号来指定运算顺序，也不需要考虑运算符号（比如加减乘除）的优先级。

推算过程

人工转换法

假设有一个中缀表达式a+b*c-(d+e)：

1. 首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))
2. 然后将所有运算符放到括号后面，这样就变成了((a(bc)* )+ (de)+ )-
3. 把所有括号去掉abc*+de+-，最后得出的结果就是后缀表达式。

程序转换法

1. 建立一个栈，然后从左至右的遍历中缀表达式；
2. 碰到数字直接输出，碰到操作符则需要进行优先级的比较，如果栈为空或者栈顶的操作符的优先级比当前的低，则将当前的操作符Push入栈，如果栈顶操作符的优先级大于等于当前的操作符，则POP栈顶操作符并输出，直到出现前一种情况为止；
3. 括号需要特殊处理，如果是(则直接入栈，如果是)，则需要等到找到对应的(为止，并且当两者同时出现时则同时删除。

这段话肯能很难理解清楚，我们还是以a+b*c-(d+e)为例子：

输出 a 栈底 栈顶
输出 a 栈底 + 栈顶
输出 a b 栈底 + 栈顶
输出 a b 栈底 + 栈顶
输出 a b c 栈底 + 栈顶
输出 a b c 栈底 + 栈顶
输出 a b c + 栈底 - 栈顶
输出 a b c + 栈底 - ( 栈顶
输出 a b c + d 栈底 - ( 栈顶
输出 a b c + d 栈底 - ( + 栈顶
输出 a b c + d e 栈底 - ( + 栈顶
输出 a b c + d e + 栈底 - 栈顶
输出 a b c + d e + - 栈底 栈顶

来一段JS版算法：

/**
 * 中缀表达式转后缀表达式
 * @params {string} exp 允许空格的中缀表达式，数字全部为整数
 */
function infixToPostfix(exp) {
	const output = []; // 存放结果的数组
	const stack = []; // 存放操作符和括号的临时栈
	let weights = { '+': 1, '-': 1, '*': 2, '/': 2 }; // 优先级
	for (let i = 0; i < exp.length; i++) {
		const char = exp[i];
		if (char === ' ') continue;
		if (!isNaN(char)) {
			let num = char;
			// 数组越界无需特殊处理
			while (!isNaN(exp[i + 1])) {
				num += exp[++i];
			}
			output.push(num); // 数字直接输出
		} else if (char === '(') {
			stack.push(char); // 左括号先入栈
		} else if (char === ')') {
			// 遇到右括号，循环出栈到output，直至遇到左括号（左括号自身需要丢弃）
			while (stack.length) {
				const pop = stack.pop();
				if (pop === '(') break;
				output.push(pop);
			}
		} else {
			// 如果是操作符，只要栈顶操作符优先级更高就一直出栈到output
			while (weights[stack[stack.length - 1]] >= weights[char]) {
				output.push(stack.pop());
			}
			// 然后继续入栈
			stack.push(char);
		}
	}
	// 循环结束如果栈不为空，全部出栈
	while (stack.length) {
		output.push(stack.pop());
	}
	return output;
}
infixToPostfix('1+25*3-(4+5)'); // 输出：["1", "25", "3", "*", "+", "4", "5", "+", "-"]

那么得到后缀表达式之后该如何计算最终值呢？非常简单：

function countPostfix(input) {
	let output = [];
	input.forEach(item => {
		if(/\d/g.test(item)) output.push(item);
		else {
			let n2 = output.pop();
			let n1 = output.pop();
			output.push(count(n1, n2, item));
		}
	});
	// 这里偷懒，直接使用eval
	function count(n1, n2, op) {return eval(n1+op+n2);}
	return output[0];
}
countPostfix(infixToPostfix('1+2*3-(4+5)')); // 输出 -2

其它

前缀表达式和后缀表达式类似，这里不再做介绍。

引申

某个业务场景下碰到这样的诉求，希望把类似Map<String, List<Long>>这样的字符串转成这样的对象：

{
	type: 'Map',
	generic: [
		{ type: 'String' },
		{
			type: 'List',
			generic: [
				{ type: 'Long' }
			]
		}
	]
}

或者复杂一点的：java.util.Map<Map<String, Boolean>, List<Integer>>。当时第一时间想到的就是用类似逆波兰式的方式处理：

/**
 * 将泛型转换成后缀表达式，例如：
 * 将 java.util.Map<Map<String, Boolean>, List<Integer>>
 * 转成：["java.util.Map", "Map", "String", "Boolean", ",", "*", "List", "Integer", "*", ",", "*"]
 * 思路：将泛型表达式看成一种特殊的加减乘除运算，逗号看成一种运算符：Map * (Map * (String + Boolean) + List * (Integer + String))
 * @param {*} str
 */
function parseGenericToPostfix(str) {
	// 结果：["java.util.Map", "*", "<", "Map", "*", "<", "String", ",", "Boolean", ">", ",", "List", "*", "<", "Integer", ">", ">"]
	const input = str.replace(/</g, '*<') // 在 < 前面加上 *
		.replace(/([<>,*] *)/g, '{$1}')
		.split(/[{}]/)
		.filter(item => !!item)
		.map(item => item.trim());
	const output = [],
		temp = []; // output表示输出，temp表示临时存放操作符的堆栈
	const yxj = {
		',': 1,
		'*': 2
	}; // 优先级
	input.forEach(current => {
		if (current === '<') {
			temp.push(current); // 如果左括号，放入堆栈
		} else if (current === '>') { // 如果是右括号，循环输出，直至匹配到左括号才停止
			while (temp.length > 0) {
				const op = temp.pop();
				if (op === '<') {
					break;
				}
				output.push(op);
			}
		} else if (current === ',' || current === '*') { // 否则，如果是加减乘除，需要针对优先级做不同处理
			while (temp.length >= 0) {
				const op = temp[temp.length - 1];
				// 如果堆栈为空，或者上一个操作符是(，或者当前操作符优先级比栈顶操作符优先级要高
				if (!temp.length || op === '<' || yxj[current] > yxj[op]) {
					temp.push(current);
					break;
				} else {
					output.push(temp.pop());
				}
			}
		} else {
			output.push(current); // 如果是数字，直接输出
		}
	});
	// 输入循环结束后，如果操作符堆栈不为空，还要循环输出
	while (temp.length > 0) {
		output.push(temp.pop());
	}
	return output;
}

/**
 * 读取泛型后缀表达式，将 Map<String, List<Long>> 结果类似于如下格式：
 * {
 *	type: 'Map',
 *	generic: [
 *	  {type: 'String'},
 *	  {
 *		  type: 'List',
 *		  generic: [
 *			  {type: 'Long'}
 *		  ]
 *	  }
 *	]
 * }
 * @param {*} input 泛型表达式
 */
function readGenericPostfix(input) {
	input = parseGenericToPostfix(input);
	const output = [];
	input.forEach(item => {
		if (item === '*' || item === ',') {
			let n2 = output.pop(); // 先出的内容
			let n1 = output.pop(); // 后出的内容
			n2 = typeof n2 === 'string' ? {type: n2} : n2;
			n1 = typeof n1 === 'string' ? {type: n1} : n1;
			if (item === ',') {
				output.push((n1 instanceof Array) ? [...n1, n2] : [n1, n2]);
			} else if (item === '*') {
				n1.generic = n2 instanceof Array ? n2 : [n2];
				output.push(n1);
			}
		} else {
			output.push(item);
		}
	});
	return output[0];
}

但是若干年后突然发现，貌似把简单问题复杂化了，这个场景其实并不需要这么麻烦。