javascript中解析四則運(yùn)算表達(dá)式的算法和示例

更新時(shí)間：2014年08月11日 11:02:07 投稿：junjie

這篇文章主要介紹了javascript中解析四則運(yùn)算表達(dá)式的算法和示例,本文介紹了中綴表示法、逆波蘭表示法這2種算法,并分別給出了代碼實(shí)例,需要的朋友可以參考下

在編寫代碼時(shí)我們有時(shí)候會(huì)碰到需要自己解析四則運(yùn)算表達(dá)式的情況，本文簡單的介紹使用JavaScript實(shí)現(xiàn)對(duì)簡單四則運(yùn)算表達(dá)式的解析。

一、熟悉概念

中綴表示法（或中綴記法）是一個(gè)通用的算術(shù)或邏輯公式表示方法，操作符是以中綴形式處于操作數(shù)的中間（例：3 + 4）。也就是我們最常用的算術(shù)表達(dá)式，中綴表達(dá)式對(duì)于人類來說比較容易理解，但是不易于計(jì)算機(jī)解析。

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數(shù)學(xué)家揚(yáng)·武卡謝維奇1920年引入的數(shù)學(xué)表達(dá)式方式，在逆波蘭記法中，所有操作符置于操作數(shù)的后面，因此也被稱為后綴表示法。逆波蘭記法不需要括號(hào)來標(biāo)識(shí)操作符的優(yōu)先級(jí)。逆波蘭表示法容易使用堆棧結(jié)構(gòu)對(duì)表達(dá)式進(jìn)行解析并計(jì)算，所以，這里我們解析四則元素表達(dá)式，是先從中綴表達(dá)式，轉(zhuǎn)換為逆波蘭表達(dá)式。然后再計(jì)算值。

二、轉(zhuǎn)換流程

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式（調(diào)度場算法）

1.輸入隊(duì)列彈出一個(gè)記號(hào)
2.如果記號(hào)為數(shù)字，添加到輸出隊(duì)列中
3.如果是一個(gè)操作符（+-*/）則比較它與輸出堆棧中棧頂?shù)牟僮鞣?，如果?yōu)先級(jí)小于或等于棧頂?shù)牟僮鞣敲磳ｍ數(shù)牟僮鞣麖棾霾⒓尤胼敵鲫?duì)列（循環(huán)，直到上述條件不滿足），最后將本次的操作符壓入堆棧。
4.如果是一個(gè)左括號(hào)，壓入堆棧
5.如果是一個(gè)右括號(hào)，從棧中不斷的彈出操作符，并加入輸出隊(duì)列，知道棧頂?shù)脑貫樽罄ㄌ?hào)。彈出左括號(hào)，不加入輸出隊(duì)列。如果沒有發(fā)現(xiàn)左括號(hào)，說明原來的表達(dá)式中括號(hào)不對(duì)稱，有錯(cuò)誤。
6.如果輸入隊(duì)列為空，而棧中尚有操作符時(shí)，如果棧頂?shù)牟僮鞣麨樽罄ㄌ?hào)，則說明原表達(dá)式有不匹配的括號(hào)。將棧中的操作符逐個(gè)彈出，加入輸出隊(duì)列。
7.完成

三、轉(zhuǎn)換代碼實(shí)現(xiàn)

function isOperator(value){
	var operatorString = "+-*/()";
	return operatorString.indexOf(value) > -1
}

function getPrioraty(value){
	switch(value){
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			return 0;
	}
}

function prioraty(o1, o2){
	return getPrioraty(o1) <= getPrioraty(o2);
}

function dal2Rpn(exp){
	var inputStack = [];
	var outputStack = [];
	var outputQueue = [];

	for(var i = 0, len = exp.length; i < len; i++){
		var cur = exp[i];
		if(cur != ' ' ){
			inputStack.push(cur);
		}
	}
	console.log('step one');
	while(inputStack.length > 0){
		var cur = inputStack.shift();
		if(isOperator(cur)){
			if(cur == '('){
				outputStack.push(cur);
			}else if(cur == ')'){
				var po = outputStack.pop();
				while(po != '(' && outputStack.length > 0){
					outputQueue.push(po);
					po = outputStack.pop();
				}
				if(po != '('){
					throw "error: unmatched ()";
				}
			}else{
				while(prioraty(cur, outputStack[outputStack.length - 1]) && outputStack.length > 0){
					outputQueue.push(outputStack.pop());
				}
				outputStack.push(cur);
			}
		}else{
			outputQueue.push(new Number(cur));
		}
	}
	console.log('step two');
	if(outputStack.length > 0){
		if(outputStack[outputStack.length - 1] == ')' || outputStack[outputStack.length - 1] == '('){
			throw "error: unmatched ()";
		}
		while(outputStack.length > 0){
			outputQueue.push(outputStack.pop());
		}
	}
	console.log('step three');
	return outputQueue;

}

console.log(dal2Rpn('1 + 2'));
console.log(dal2Rpn('1 + 2 + 3'));
console.log(dal2Rpn('1 + 2 * 3'));
console.log(dal2Rpn('1 + 2 * 3 - 4 / 5'));
console.log(dal2Rpn('( 1 + 2 )'));

console.log(dal2Rpn('( 1 + 2 ) * ( 3 - 4 ) / 5'));
console.log(dal2Rpn('( 1 + 2 ) * (( 3 - 4 ) / 5)'));

四、逆波蘭表達(dá)式求值

1.從輸入隊(duì)列中彈出一個(gè)記號(hào)
2.如果是操作數(shù)，加入輸出堆棧
3.如果是一個(gè)操作符，從輸出堆棧中彈出兩個(gè)操作數(shù)并進(jìn)行計(jì)算，并將計(jì)算得到的值壓入輸出堆棧。
4.循環(huán)操作，如果輸入隊(duì)列為空，且輸出堆棧只有一個(gè)數(shù)則這個(gè)數(shù)為結(jié)果，否則是出現(xiàn)了多余的操作數(shù)。

五、計(jì)算代碼

function evalRpn(rpnQueue){
	var outputStack = [];
	while(rpnQueue.length > 0){
		var cur = rpnQueue.shift();

		if(!isOperator(cur)){
			outputStack.push(cur);
		}else{
			if(outputStack.length < 2){
				throw "unvalid stack length";
			}
			var sec = outputStack.pop();
			var fir = outputStack.pop();

			outputStack.push(getResult(fir, sec, cur));
		}
	}

	if(outputStack.length != 1){
		throw "unvalid expression";
	}else{
		return outputStack[0];
	}
}

六、結(jié)語

逆波蘭表示法，在初次接觸的時(shí)候感覺不太習(xí)慣，但是熟悉之后，會(huì)發(fā)現(xiàn)，其實(shí)思路特別簡單，不像中綴表示法，還有各種優(yōu)先級(jí)啊，還有小括號(hào)之類的，邏輯特別麻煩，還是逆波蘭表示法比較簡潔，完全不用考慮優(yōu)先級(jí)，也沒用小括號(hào)，中括號(hào)還有大括號(hào)攪局。

您可能感興趣的文章: