Java用棧實(shí)現(xiàn)綜合計(jì)算器
棧
棧(stack)又名堆棧,它是一種運(yùn)算受限的線(xiàn)性表 。限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。這一端被稱(chēng)為棧頂,相對(duì)地,把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入?;驂簵#前研略胤诺綏m斣氐纳厦?,使之成為新的棧頂元素;從一個(gè)棧刪除元素又稱(chēng)作出?;蛲藯?,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素。
概念隨便一看,反正就是先進(jìn)后出的一種數(shù)據(jù)結(jié)構(gòu),什么是棧這里不做贅述,下面看一下如何在Java中,利用數(shù)組實(shí)現(xiàn)模擬一個(gè)棧。
Java實(shí)現(xiàn)棧
可以用數(shù)組來(lái)簡(jiǎn)單的模擬出一個(gè)棧的結(jié)構(gòu)。
棧一共兩個(gè)操作,入棧和出棧
我們只需要一個(gè)指針指向棧頂即可完成:
1.出棧的時(shí)候?qū)m斨羔樦赶虻臄?shù)據(jù)取出,指針左移一位指向新的棧頂數(shù)據(jù)
2.入棧的時(shí)候?qū)m斨羔樅笠埔晃?,新的棧頂?shù)據(jù)放入指針?biāo)谖恢?/p>
注意:當(dāng)然,由于數(shù)組存儲(chǔ)空間是定長(zhǎng)的,需要指定棧的大小,出入棧也需要判斷??铡M(mǎn)
用類(lèi)ArrayStack作為棧對(duì)象
1.屬性maxSize存放棧的大小,用于判斷棧是否滿(mǎn)
2.屬性stack[]是用于存放棧的數(shù)組
3.top指針指向棧頂,初始化指向-1(因?yàn)槿霔R群笠疲?/p>
4.方法有——查看棧頂數(shù)據(jù)、判斷棧是否空、判斷棧是否滿(mǎn)、入棧、出棧、打印棧
代碼如下:
class ArrayStack{ /** * 棧的大小 */ private int maxSize; /** * 數(shù)組,模擬棧 */ private int[] stack; /** * top表示棧頂數(shù)據(jù)所在數(shù)組位置的下標(biāo),初始化為-1 */ private int top = -1; /** * 構(gòu)造器,初始化棧 * @param maxSize 棧的大小 */ public ArrayStack(int maxSize){ this.maxSize = maxSize; stack = new int[maxSize]; } /** * 返回當(dāng)前棧頂?shù)闹?,不出? * @return 當(dāng)前棧頂?shù)闹? */ public int topData(){ return stack[top]; } /** * 判斷棧是否滿(mǎn) */ public boolean isFull(){ return top==maxSize-1; } /** * 判斷棧是否空 */ public boolean isNull(){ return top==-1; } /** * 入棧 * @param data 入棧的數(shù)據(jù) */ public void push(int data){ //先判斷棧是否是滿(mǎn)的 if (isFull()){ //如果是滿(mǎn)的,打印錯(cuò)誤,直接返回 System.out.println("棧已滿(mǎn)"); return; } //棧沒(méi)滿(mǎn),入棧 // top++;stack[top]=data; stack[++top] = data; } /** * 出棧 * @return 返回棧頂數(shù)據(jù) */ public int pop(){ //先判斷棧是否為空 if (isNull()){ //如果為空,拋出異常 throw new RuntimeException("棧為空,沒(méi)有可出棧數(shù)據(jù)"); } //不為空?qǐng)?zhí)行出棧 return stack[top--]; } /** * 顯示棧的情況,從棧頂顯示到棧底 */ public void showStack(){ //先判斷是否為空棧 if (isNull()){ System.out.println("棧為空,沒(méi)有數(shù)據(jù)"); return; } //遍歷顯示棧 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n",i,stack[i]); } }
至此,一個(gè)簡(jiǎn)單的棧結(jié)構(gòu)就模擬完成了
那么??梢杂脕?lái)做什么呢?
進(jìn)制轉(zhuǎn)換、判斷括號(hào)是否匹配、算數(shù)表達(dá)式的計(jì)算、中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式
本文來(lái)實(shí)現(xiàn)一個(gè)中綴表達(dá)式的計(jì)算、后綴表達(dá)式計(jì)算以及中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式
棧實(shí)現(xiàn)綜合計(jì)算器
首先分析,表達(dá)式由運(yùn)算數(shù)和運(yùn)算符組成,運(yùn)算符具有優(yōu)先級(jí)問(wèn)題,所以在計(jì)算一個(gè)表達(dá)式時(shí),是根據(jù)運(yùn)算符優(yōu)先級(jí)順序?qū)\(yùn)算數(shù)進(jìn)行對(duì)應(yīng)運(yùn)算符的計(jì)算
那么首先需要一些工具方法對(duì)用于遍歷表達(dá)式時(shí)的判斷,和運(yùn)算表達(dá)式時(shí)的計(jì)算
包括:
1.判斷字符是否是一個(gè)運(yùn)算符
2.判斷字符是否是括號(hào)
3.判斷運(yùn)算符的優(yōu)先級(jí)
4.根據(jù)運(yùn)算符計(jì)算兩個(gè)數(shù)據(jù)
/** * 判斷char字符是否是一個(gè)運(yùn)算符 * @param operator 要檢測(cè)是否是運(yùn)算符的char * @return 是否為運(yùn)算符 */ static boolean isOperator(int operator){ return operator=='+'||operator=='-'||operator=='*'||operator=='/'; } /** * 判斷char字符是否是括號(hào) */ static boolean isBracket(int operator){ return operator=='('||operator==')'; } /** * 返回運(yùn)算符優(yōu)先級(jí)(數(shù)字大優(yōu)先級(jí)高) * @param operator 運(yùn)算符 * @return 表示優(yōu)先級(jí)的int */ static int priority(int operator){ if (operator == '+' || operator == '-'){ return 0; } if (operator == '*' || operator == '/'){ return 1; } return -1; } /** * 根據(jù)運(yùn)算符計(jì)算兩個(gè)數(shù)據(jù) * @param num1 數(shù)據(jù)1 * @param num2 數(shù)據(jù)2 * @param operator 運(yùn)算符(+-*除) * @return 運(yùn)算結(jié)果 */ static int calculate(int num1,int num2,int operator){ int res = 0; switch (operator){ case '+': res = num2 + num1; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; default: break; } return res; }
1.中綴表達(dá)式直接計(jì)算
這里實(shí)現(xiàn)直接計(jì)算一個(gè)中綴表達(dá)式,沒(méi)有寫(xiě)入對(duì)括號(hào)的判斷,所以只能是計(jì)算最簡(jiǎn)單的加減乘除
具體實(shí)現(xiàn)思路,需要兩個(gè)棧,一個(gè)棧放運(yùn)算數(shù),一個(gè)棧放運(yùn)算符
遍歷整個(gè)算數(shù)表達(dá)式的字符串:
會(huì)有兩種情況,遇到運(yùn)算符或者遇到運(yùn)算數(shù)
1.如果遇到運(yùn)算數(shù)就加入到數(shù)棧中
2.如果是運(yùn)算符需要循環(huán)判斷符號(hào)棧的情況,如果符號(hào)棧不為空且當(dāng)前運(yùn)算符優(yōu)先級(jí)小于等于棧頂運(yùn)算符,就彈出兩個(gè)運(yùn)算數(shù)一個(gè)運(yùn)算符進(jìn)行計(jì)算,計(jì)算結(jié)果壓入數(shù)棧;直到符號(hào)棧為空或者當(dāng)前運(yùn)算符優(yōu)先級(jí)大于棧頂,就將當(dāng)前運(yùn)算符入符號(hào)棧
3.算術(shù)表達(dá)式遍歷結(jié)束后,繼續(xù)計(jì)算,循環(huán)彈出兩個(gè)數(shù)一個(gè)符號(hào),計(jì)算結(jié)果入數(shù)棧,直到符號(hào)棧為空,此時(shí)數(shù)棧中剩下一個(gè)數(shù)字就是表達(dá)式的計(jì)算結(jié)果
/** * 計(jì)算中綴表達(dá)式的結(jié)果(不能含有括號(hào)) * @param expression 中綴表達(dá)式 * @return 結(jié)果 */ static int calculateMid(String expression) { //數(shù)字棧 ArrayStack numStack = new ArrayStack(10); //運(yùn)算符棧 ArrayStack operatorStack = new ArrayStack(10); //遍歷字符串進(jìn)行入棧等運(yùn)算操作 for (int i = 0; i < expression.length(); i++) { //遍歷到字符串中的一個(gè)字符 char ch = expression.charAt(i); //判斷是否為運(yùn)算符 if (isOperator(ch)) { //如果是運(yùn)算符,判斷當(dāng)前符號(hào)棧是否為空 //不為空,判斷當(dāng)前符號(hào)優(yōu)先級(jí)和棧中符號(hào)優(yōu)先級(jí)的關(guān)系進(jìn)行操作 //當(dāng)前運(yùn)算符優(yōu)先級(jí)小于等于棧中運(yùn)算符優(yōu)先級(jí),從數(shù)棧中pop兩個(gè)數(shù)據(jù),運(yùn)算符棧中pop一個(gè)運(yùn)算符進(jìn)行計(jì)算,計(jì)算結(jié)果push進(jìn)數(shù)棧,新運(yùn)算符再次進(jìn)行優(yōu)先級(jí)判斷 while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){ int num1 = numStack.pop(); int num2 = numStack.pop(); int operator = operatorStack.pop(); int res = calculate(num1, num2, operator); numStack.push(res); } //直到當(dāng)前運(yùn)算符優(yōu)先級(jí)大于棧中運(yùn)算符優(yōu)先級(jí)或棧為空,再入棧 operatorStack.push(ch); }else { //如果不是運(yùn)算符,判斷是否是數(shù)字 if (Character.isDigit(ch)) { //如果是數(shù)字,準(zhǔn)備記錄下這個(gè)數(shù)字 StringBuilder num = new StringBuilder(String.valueOf(ch)); //找到下一個(gè)字符判斷,進(jìn)行拼接操作,直到下一個(gè)為運(yùn)算符或沒(méi)有下一個(gè)字符為止 while (i+1 < expression.length()&&!isOperator(expression.charAt(i+1))) { //如果還是數(shù)字,先將數(shù)字拼接,再i++ num.append(expression.charAt(i+1)); i++; } numStack.push(Integer.parseInt(num.toString())); }else { //如果不是數(shù)字(到這里就既不是數(shù)字也不是運(yùn)算符)報(bào)錯(cuò)表達(dá)式有誤 throw new RuntimeException("運(yùn)算表達(dá)式有誤,不支持的符號(hào):[ "+ch+" ]"); } } } //遍歷結(jié)束后將棧中繼續(xù)計(jì)算直到數(shù)棧中只有一個(gè)數(shù)字,就是結(jié)果 while (!operatorStack.isNull()){ int num1 = numStack.pop(); int num2 = numStack.pop(); int operator = operatorStack.pop(); int res = calculate(num1, num2, operator); numStack.push(res); } return numStack.pop(); }
2.后綴表達(dá)式計(jì)算
后綴表達(dá)式是也稱(chēng)逆波蘭表達(dá)式,是一種計(jì)算機(jī)更好處理的表達(dá)式結(jié)構(gòu)
因?yàn)楹缶Y表達(dá)式相當(dāng)于按照優(yōu)先級(jí)、括號(hào)等,排好了計(jì)算順序,計(jì)算機(jī)只需要順序向后加載計(jì)算即可
用到一個(gè)數(shù)棧就夠了,只需要遍歷表達(dá)式,遇到數(shù)字直接入棧,遇到符號(hào)直接出棧兩個(gè)數(shù)字進(jìn)行運(yùn)算,將結(jié)果再入棧,直到表達(dá)式遍歷結(jié)束,棧中就剩下一個(gè)數(shù)字就是計(jì)算結(jié)果
代碼如下:
這里將表達(dá)式格式限制為每個(gè)不同元素用空格隔開(kāi),便不需要加載操作數(shù)時(shí)判斷多位數(shù)了
/** * 計(jì)算后綴表達(dá)式 * @param expression 后綴表達(dá)式 * @return 計(jì)算結(jié)果 */ static int calculateSuf(String expression){ //1.將后綴表達(dá)式拆開(kāi)放入集合 String[] expressionList = expression.split(" "); //2.創(chuàng)建數(shù)棧 ArrayStack numStack = new ArrayStack(10); for (String s : expressionList) { //判斷是否是符號(hào) if (isOperator(s.charAt(0))) { //是符號(hào)就出棧兩個(gè)數(shù)據(jù)進(jìn)行計(jì)算 int num1 = numStack.pop(); int num2 = numStack.pop(); int res = calculate(num1, num2, s.charAt(0)); //計(jì)算結(jié)果入棧 numStack.push(res); }else { //不是符號(hào)轉(zhuǎn)換為數(shù)字入棧即可 int num; try { num = Integer.parseInt(s); }catch (NumberFormatException e){ throw new RuntimeException("錯(cuò)誤的表達(dá)式:[ "+s+" ]"); } numStack.push(num); } } return numStack.pop(); }
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
中綴表達(dá)式就是生活中使用的算數(shù)表達(dá)式
比如一個(gè)中綴表達(dá)式:1+((2+3)*4)-5
轉(zhuǎn)換為后綴表達(dá)式為:1 2 3 + 4 * + 5 -
目前,如果要我自己去轉(zhuǎn)換,一般采用樹(shù)來(lái)輔助,更好記憶和理解,將中綴表達(dá)式轉(zhuǎn)換成樹(shù)形結(jié)構(gòu),再后序遍歷這個(gè)樹(shù)就能得到后綴表達(dá)式
這個(gè)轉(zhuǎn)換過(guò)程,用算法來(lái)完成,是稍有些復(fù)雜的,轉(zhuǎn)換算法也是前人長(zhǎng)時(shí)間的智慧結(jié)晶,沒(méi)有看到過(guò)轉(zhuǎn)換方法之前,自己想不到怎么轉(zhuǎn)換還算蠻正常的,重點(diǎn)體會(huì)一下這個(gè)思路就好,其實(shí)整個(gè)思路也是根據(jù)之前計(jì)算中綴表達(dá)式得來(lái)
轉(zhuǎn)換算法思路:
1.初始化兩個(gè)棧,一個(gè)是符號(hào)棧s1,一個(gè)是中間結(jié)果棧s2
2.從左到右掃描中綴表達(dá)式
3.遇到操作數(shù)直接入棧s2
4.遇到運(yùn)算符還是循環(huán)判斷,當(dāng)運(yùn)算符棧不為空且當(dāng)前運(yùn)算符優(yōu)先級(jí)不大于棧頂運(yùn)算符時(shí),就彈出一個(gè)運(yùn)算符壓入中間結(jié)果棧,直到棧為空或當(dāng)前運(yùn)算符優(yōu)先級(jí)大于棧頂運(yùn)算符優(yōu)先級(jí)(這里判斷優(yōu)先級(jí),會(huì)出現(xiàn)左括號(hào),左括號(hào)當(dāng)做最低優(yōu)先級(jí),也就是遇到左括號(hào)就直接運(yùn)算符入棧即可)
5.遇到括號(hào)時(shí),如果是左括號(hào),直接入棧s1;如果是右括號(hào),依次彈出s1中的運(yùn)算符壓入s2,直到遇見(jiàn)左括號(hào)為止,此時(shí)將一對(duì)括號(hào)丟棄
6.直到整個(gè)表達(dá)式遍歷結(jié)束,再將s1中剩余的運(yùn)算符依次彈出壓入s2
此時(shí)s2棧彈出順序的逆序就是后綴表達(dá)式
代碼如下:
static String infixToSuffix(String infix){ //運(yùn)算符棧 ArrayStack operatorStack = new ArrayStack(20); //結(jié)果棧 ArrayStack resStack = new ArrayStack(20); //遍歷掃描中綴表達(dá)式 for (int i = 0; i < infix.length(); i++) { //遍歷到的一個(gè)字符 char ch = infix.charAt(i); //判斷是否為運(yùn)算符 if (isOperator(ch)){ //循環(huán)判斷如果運(yùn)算符棧不為空且當(dāng)前運(yùn)算符優(yōu)先級(jí)不大于棧頂運(yùn)算符 while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){ //彈出運(yùn)算符棧壓入結(jié)果棧 resStack.push(operatorStack.pop()); } //當(dāng)前運(yùn)算符入運(yùn)算符棧 operatorStack.push(ch); } //如果不是運(yùn)算符再判斷是否是運(yùn)算數(shù),是就直接壓入結(jié)果棧 else if (Character.isDigit(ch)){ //如果是數(shù)字,記錄下這個(gè)數(shù)字壓入結(jié)果棧 StringBuilder num = new StringBuilder(String.valueOf(ch)); //找到下一個(gè)字符判斷,進(jìn)行拼接操作,直到下一個(gè)為運(yùn)算符或沒(méi)有下一個(gè)字符為止 while (i+1 < infix.length()&&Character.isDigit(infix.charAt(i+1))) { //如果還是數(shù)字,先將數(shù)字拼接,再i++ num.append(infix.charAt(i+1)); i++; } resStack.push(Integer.parseInt(num.toString())); } //如果不是運(yùn)算符也不是操作數(shù),判斷是否為括號(hào) else if (isBracket(ch)){ //如果是括號(hào),判斷左括號(hào)壓入運(yùn)算符棧 if (ch=='('){ operatorStack.push(ch); } //如果是右括號(hào),依次彈出s1的運(yùn)算符,壓入結(jié)果棧,直到遇見(jiàn)左括號(hào)(丟棄這一對(duì)括號(hào)) else if (ch==')'){ while (true){ int top = operatorStack.pop(); if (top=='('){ break; } resStack.push(top); } } } } //遍歷結(jié)束后,將運(yùn)算符棧中剩余的運(yùn)算符依次彈出壓入結(jié)果棧 while (!operatorStack.isNull()){ resStack.push(operatorStack.pop()); } //遍歷結(jié)果棧返回后綴表達(dá)式字符串(這里是反的) StringBuilder res = new StringBuilder(); while (!resStack.isNull()){ int pop = resStack.pop(); if (isOperator(pop)){ char popChar = (char) pop; res.append(popChar).append(" "); }else { res.append(pop).append(" "); } } //將結(jié)果字符串反轉(zhuǎn)返回后綴表達(dá)式 String s = res.toString(); String[] s1 = s.split(" "); StringBuilder builder = new StringBuilder(); for (int i = s1.length-1; i >= 0; i--) { builder.append(s1[i]).append(" "); } return builder.toString(); }
思考:
最后出棧順序的倒敘才是后綴表達(dá)式,那么是否可以用隊(duì)列來(lái)代替s2棧呢?
是完全可以的,s2在整個(gè)過(guò)程只有入棧操作,更換為隊(duì)列進(jìn)行入隊(duì),最終棧先進(jìn)后出是逆序,隊(duì)列先進(jìn)先出就是順序的。
到此這篇關(guān)于Java用棧實(shí)現(xiàn)綜合計(jì)算器的文章就介紹到這了,更多相關(guān)Java綜合計(jì)算器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
一文學(xué)會(huì)如何在SpringBoot中使用線(xiàn)程池執(zhí)行定時(shí)任務(wù)
在開(kāi)發(fā)現(xiàn)代應(yīng)用程序時(shí),定時(shí)任務(wù)是一項(xiàng)常見(jiàn)的需求,SpringBoot提供了一個(gè)強(qiáng)大的定時(shí)任務(wù)框架,可以輕松地執(zhí)行各種定時(shí)任務(wù),結(jié)合線(xiàn)程池的使用,可以更好地管理任務(wù)的執(zhí)行,提高系統(tǒng)的性能和穩(wěn)定性,本文將介紹如何在Spring Boot中使用線(xiàn)程池執(zhí)行定時(shí)任務(wù)2023-06-06使用Spring Expression Language (SpEL)全面解析表達(dá)式
這篇文章主要介紹了使用Spring Expression Language (SpEL)全面解析表達(dá)式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-02-02Apache Commons fileUpload文件上傳多個(gè)示例分享
這篇文章主要為大家分享了Apache Commons fileUpload文件上傳4個(gè)示例,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-10-10springboot整合Dubbo與Feign的實(shí)現(xiàn)?(無(wú)注冊(cè)中心)
本文主要介紹了springboot整合Dubbo與Feign的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04Java?awt-對(duì)話(huà)框簡(jiǎn)單實(shí)現(xiàn)方式
這篇文章主要介紹了Java?awt-對(duì)話(huà)框簡(jiǎn)單實(shí)現(xiàn)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-12-12java Iterator.remove()實(shí)例方法分析
在本篇文章里小編給大家整理了一篇關(guān)于java Iterator.remove()實(shí)例方法分析,有興趣的朋友們跟著學(xué)習(xí)下。2021-01-01JavaWeb JDBC + MySql 通訊錄實(shí)現(xiàn)簡(jiǎn)單的增刪改查功能案例詳解
這篇文章主要介紹了JavaWeb JDBC + MySql 通訊錄實(shí)現(xiàn)簡(jiǎn)單的增刪改查功能,結(jié)合具體案例形式詳細(xì)分析了JavaWeb JDBC + MySql數(shù)據(jù)庫(kù)連接、增刪改查等相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下2019-08-08為什么不推薦使用BeanUtils屬性轉(zhuǎn)換工具示例詳解
這篇文章主要介紹了為什么不推薦使用BeanUtils屬性轉(zhuǎn)換工具,本文通過(guò)示例代碼給大家詳細(xì)介紹,對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-07-07