javascript中解析四則運算表達式的算法和示例

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

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

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

一、熟悉概念

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

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

二、轉(zhuǎn)換流程

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

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

三、轉(zhuǎn)換代碼實現(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)'));

四、逆波蘭表達式求值

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

五、計算代碼

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];
	}
}

六、結語

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

您可能感興趣的文章: