亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時(shí)間:2014年08月11日 11:02:07   投稿:junjie  
這篇文章主要介紹了javascript中解析四則運(yùn)算表達(dá)式的算法和示例,本文介紹了中綴表示法、逆波蘭表示法這2種算法,并分別給出了代碼實(shí)例,需要的朋友可以參考下

在編寫代碼時(shí)我們有時(shí)候會(huì)碰到需要自己解析四則運(yùn)算表達(dá)式的情況,本文簡(jiǎn)單的介紹使用JavaScript實(shí)現(xiàn)對(duì)簡(jiǎn)單四則運(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)度場(chǎng)算法)

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é)語(yǔ)

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

相關(guān)文章

最新評(píng)論