javascript中解析四則運(yùn)算表達(dá)式的算法和示例
在編寫代碼時(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)文章
Auto.js自動(dòng)收取自己和好友螞蟻森林能量腳本
這篇文章主要為大家詳細(xì)介紹了Auto.js自動(dòng)收取自己和好友螞蟻森林能量腳本,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-06-06js動(dòng)態(tài)添加表格逐行添加、刪除、遍歷取值的實(shí)例代碼
最近做項(xiàng)目遇到這樣的需求,要求表格添加一行,表格刪除一行,表格遍歷取值等。下面小編給大家?guī)砹薺s動(dòng)態(tài)添加表格逐行添加、刪除、遍歷取值的實(shí)例代碼,需要的朋友參考下2018-01-01超鏈接怎么正確調(diào)用javascript函數(shù)
本文介紹使用超鏈接調(diào)用javasript函數(shù)且不會(huì)影響GIF圖片動(dòng)畫的方法,有遇到相同問題的小伙伴可以參考一下。2016-05-05Webpack打包時(shí)將文件內(nèi)聯(lián)方法實(shí)現(xiàn)
本文主要介紹了Webpack打包時(shí)將文件內(nèi)聯(lián)方法實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01分享一道筆試題[有n個(gè)直線最多可以把一個(gè)平面分成多少個(gè)部分]
今天地鐵上和一個(gè)同事閑聊,給我說的一道題,回來想了想,寫出來的,說來慚愧,我用的是行測(cè)方面數(shù)字推理里面的知識(shí)歸納出來的,當(dāng)然這個(gè)可以用遞歸寫出來,說說我的代碼,以及遞歸的思路2012-10-10詳解使用JWT實(shí)現(xiàn)單點(diǎn)登錄(完全跨域方案)
這篇文章主要介紹了詳解使用JWT實(shí)現(xiàn)單點(diǎn)登錄(完全跨域方案),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08js事件機(jī)制----捕獲與冒泡機(jī)制實(shí)例分析
這篇文章主要介紹了js事件機(jī)制----捕獲與冒泡機(jī)制,結(jié)合實(shí)例形式分析了js事件機(jī)制中捕獲與冒泡機(jī)制相關(guān)原理、操作技巧與注意事項(xiàng),需要的朋友可以參考下2020-05-05javascript Xml增刪改查(IE下)操作實(shí)現(xiàn)代碼
比較不錯(cuò)的實(shí)現(xiàn)代碼,大家可以仔細(xì)的看下,思路。2009-01-01