中缀表达式与后缀表达式
本文由 小茗同学 发表于 2018-03-19 浏览(4894)
最后修改 2019-05-16 标签:表达式 算法

概念

前缀表达式(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版算法:

// 中缀表达式转换成后缀表达式,这里假设数字都只有1位且没有空格,例如:'1+2*3-(4+5)'
function houzhui(str) {
	let input = str.split(''), output = [], temp = []; // output表示输出,temp表示临时存放操作符的堆栈
	let yxj = {'+': 1, '-': 1, '*': 2, '/': 2}; // 优先级
	input.forEach(current => {
		if(/\d/g.test(current)) output.push(current); // 如果是数字,直接输出
		else if(current == '(') temp.push(current); // 如果左括号,放入堆栈
		else if(current == ')') { // 如果是右括号,循环输出,直至匹配到左括号才停止
			while(temp.length > 0) {
				let op = temp.pop();
				if(op == '(') break;
				output.push(op);
			}
		} else { // 否则,如果是加减乘除,需要针对优先级做不同处理
			while(temp.length >= 0) {
				let op = temp[temp.length-1];
				// 如果堆栈为空,或者上一个操作符是(,或者当前操作符优先级比栈顶操作符优先级要高
				if(!temp.length || op == '(' || yxj[current] > yxj[op]) {
					temp.push(current);
					break;
				} else output.push(temp.pop());
			}
		}
	});
	// 输入循环结束后,如果操作符堆栈不为空,还要循环输出
	while(temp.length > 0) output.push(temp.pop());
	return output;
}
houzhui('1+2*3-(4+5)'); // 输出:["1", "2", "3", "*", "+", "4", "5", "+", "-"]

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

function countHouzhui(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];
}
countHouzhui(houzhui('1+2*3-(4+5)')); // 输出 -2

其它

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