您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“Java中綴表達(dá)式如何實(shí)現(xiàn)”的有關(guān)知識,在實(shí)際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
什么是中綴表達(dá)式,什么是后綴表達(dá)式?
從小學(xué)開始學(xué)習(xí)的四則運(yùn)算,例如:3+(5*(2+3)+7) 類似這種表達(dá)式就是中綴表達(dá)式。中綴表達(dá)式人腦很容易理解,各個算符的優(yōu)先級,人腦也很容易判斷,先算括弧里的,再算*,再算+,-
但是這種表達(dá)式很不利于計算機(jī)計算,通過某種方式把前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式方便計算機(jī)進(jìn)行計算,如3+(5*(2+3)+7)的后綴表達(dá)式就是3,5,2,3,+,*,7,+, +。這個表達(dá)式計算機(jī)很容易計算,為什么容易計算,通過算法流程2,就會一個深入的理解。
如何把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式?比如說3+(5*(2+3)+7)的轉(zhuǎn)成后綴表達(dá)式的流程如何?
操作符優(yōu)先級:
+,- 小于*,/
+ 等于 -
* 等于 /
左括號和右括號作為特殊操作符特殊處理。(碰到’(’不用判斷優(yōu)先級直接入操作符棧,碰到’)’,也不用判斷優(yōu)先級,直接出操作符棧)
大致算法掌握以下幾個流程:
準(zhǔn)備兩個棧,一個是數(shù)字棧A,一個是操作符棧(+,-,*,/(,))B等
1.0 對于數(shù)字棧A,遇到數(shù)字直接入棧A。
2.0 對于操作符棧B,分幾種情況
2.1 碰到 ‘(‘操作符直接入棧
2.2 碰到 ‘)’操作符,不停的把操作符棧B出棧,直到遇到’)’。(把’(’到’)’之間的彈出的操作符依次入棧A)
2.3 碰到’+,-,* /’比較當(dāng)前元素(假設(shè)當(dāng)前元素current)和B棧棧頂?shù)牟僮鞣?假設(shè)棧頂元素是top)的優(yōu)先級.
2.3.1 如果top >= current, B棧出棧且循環(huán)比較,直到top < current退出循環(huán),且把 current入棧
2.3.2 如果top < current, 直接把current入B棧
3.0 掃描完整個字符串,如果B棧中還有操作符,依次出棧入A
按照上面算法演示3+(5*(2+3)+7)的流程:
1,碰到3,3入A棧 [3,]
2,碰到+,入B棧 [+,]
3,碰到(,入B棧 [+,(]
4,碰到5,入A棧 [3,5]
5,碰到*,*的優(yōu)先級大于 (,入B棧[ +,(,*]
6,碰到(,入B棧[ +,(,*,(]
7,碰到2,入A棧 [3,5,2]
8,碰到+,入B棧[ +,(,*,(,+]
9,碰到3,入A棧 [3,5,2,3]
10,碰到),彈出B棧,直接到 ‘(‘,把彈出的操作符入A棧。B:[ +,(,*] A:[3,5,2,3,+]
11,碰到+, +的優(yōu)先級小于B的棧頂元素 *,所以*從B出棧,入A,并把+入B。B:[ +,(,+] A:[3,5,2,3,+,*]
12,碰到7,入A棧 [3,5,2,3,+,*,7]
13,碰到),彈出B棧,直接到 ‘(‘,把彈出的操作符入A棧。B:[ +] A:[3,5,2,3,+,*,7,+]
14, 掃描完整個字符串,判斷B是否為空,不為空把B棧的元素彈出,入A。當(dāng)前不為空,所以最終A棧的元素為 A:[3,5,2,3,+,*,7,+, +]
所以最終A的后綴表達(dá)式是3,5,2,3,+,*,7,+, +
計算機(jī)拿到這個會怎么計算呢?流程如下:
碰到數(shù)字直接入棧
碰到操作符,直接彈出兩個棧頂元素,通過操作符計算,把結(jié)果壓入棧
通過步驟1,2循環(huán)計算,最終棧里只會有一個元素,這個就是表達(dá)式的結(jié)果。
我們來演練一下:
1,碰到數(shù)字3,5,2,3直接入棧A[3,5,2,3]
2,碰到+,彈出棧頂2,3,相加得5 入棧A[3,5,5]
3,碰到*,彈出棧頂5,5,相乘得25 入棧A[3,25]
4,碰到7,直接入棧A[3,25,7]
5,碰到+,彈出棧頂25,7,相加得32 入棧A[3,32]
6,碰到+,彈出棧頂3,32,相加得35 入棧A[35]
通過上面可以得知,計算機(jī)很容易計算,從左掃描到右就能把結(jié)果得出。
mid2post 求后綴表達(dá)式
calcPostExp 拿到后綴表達(dá)式求值
cmpPriority 優(yōu)先級比較
//優(yōu)先級 bool cmpPriority(char top, char cur)//比較當(dāng)前字符與棧頂字符的優(yōu)先級,若棧頂高,返回true { if ((top == '+' || top == '-') && (cur == '+' || cur == '-')) return true; if ((top == '*' || top == '/') && (cur == '+' || cur == '-' || top == '*' || top == '/')) return true; if (cur == ')') return true; return false; }
求后綴表達(dá)式求值
vector<string> mid2post(string &str) { vector<string>vstr; stack<char>cstack; for (int i = 0;i<str.size();++i)//掃描字符串 { string temp = ""; if (str[i] >= '0' && str[i] <= '9')//若是數(shù)字 { temp += str[i]; while (i + 1<str.size() && str[i + 1] >= '0' && str[i + 1] <= '9') { temp += str[i + 1];//若是連續(xù)數(shù)字 ++i; } vstr.push_back(temp); } else if (cstack.empty() || str[i] == '(')//若??栈蛘咦址麨?#39;(' cstack.push(str[i]); else if (cmpPriority(cstack.top(), str[i]))//若棧頂元素優(yōu)先級較高,棧頂元素出棧 { if (str[i] == ')')//若當(dāng)前字符是右括號,棧中元素出棧,入字符串?dāng)?shù)組中,直到遇到'(' { while (!cstack.empty() && cstack.top() != '(') { temp += cstack.top(); cstack.pop(); vstr.push_back(temp); temp = ""; } cstack.pop(); } else//棧中優(yōu)先級高的元素出棧,入字符串?dāng)?shù)組,直到優(yōu)先級低于當(dāng)前字符 { while (!cstack.empty() && cmpPriority(cstack.top(), str[i])) { temp += cstack.top(); cstack.pop(); vstr.push_back(temp); temp = ""; } cstack.push(str[i]); } } else//當(dāng)前字符優(yōu)先級高于棧頂元素,直接入棧 cstack.push(str[i]); } while (!cstack.empty())//棧中還存在運(yùn)算符時,出棧,存入字符串?dāng)?shù)組 { string temp = ""; temp += cstack.top(); cstack.pop(); vstr.push_back(temp); } return vstr; }
對后綴表達(dá)式進(jìn)行求值,主要是根據(jù)運(yùn)算符取出兩
int calcPostExp(vector<string> & vstr)//對后綴表達(dá)式進(jìn)行求值,主要是根據(jù)運(yùn)算符取出兩個操作數(shù)進(jìn)行運(yùn)算 { int num, op1, op2; stack<int>opstack; for (int i = 0;i<vstr.size();++i) { string temp = vstr[i]; if (temp[0] >= '0' && temp[0] <= '9')//如果當(dāng)前字符串是數(shù)字,利用字符串流轉(zhuǎn)化為int型 { stringstream ss; ss << temp; ss >> num; opstack.push(num); } else if (vstr[i] == "+")//若是操作符,取出兩個操作數(shù),進(jìn)行運(yùn)算,并將結(jié)果存入 { op2 = opstack.top(); opstack.pop(); op1 = opstack.top(); opstack.pop(); opstack.push(op1 + op2); } else if (vstr[i] == "-") { op2 = opstack.top(); opstack.pop(); op1 = opstack.top(); opstack.pop(); opstack.push(op1 - op2); } else if (vstr[i] == "*") { op2 = opstack.top(); opstack.pop(); op1 = opstack.top(); opstack.pop(); opstack.push(op1*op2); } else if (vstr[i] == "/") { op2 = opstack.top(); opstack.pop(); op1 = opstack.top(); opstack.pop(); opstack.push(op1 / op2); } } return opstack.top();//最終的棧頂元素就是求解的結(jié)果 }
“Java中綴表達(dá)式如何實(shí)現(xiàn)”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。