Java棧的運(yùn)用之中綴表達(dá)式求值詳解
棧運(yùn)用題:中綴表達(dá)式求值
題目詳情
給定一個(gè)表達(dá)式,其中運(yùn)算符僅包含 +,-,*,/(加 減 乘 整除),可能包含括號(hào),請(qǐng)你求出表達(dá)式的最終值。
注意:
數(shù)據(jù)保證給定的表達(dá)式合法。
題目保證符號(hào) - 只作為減號(hào)出現(xiàn),不會(huì)作為負(fù)號(hào)出現(xiàn),例如,-1+2,(2+2)*(-(1+1)+2) 之類(lèi)表達(dá)式均不會(huì)出現(xiàn)。
題目保證表達(dá)式中所有數(shù)字均為正整數(shù)。
題目保證表達(dá)式在中間計(jì)算過(guò)程以及結(jié)果中,均不超過(guò) 231−1。
題目中的整除是指向 0 取整,也就是說(shuō)對(duì)于大于 0 的結(jié)果向下取整,例如 5/3=1,對(duì)于小于 0 的結(jié)果向上取整,例如 5/(1−4)=−1。
C++和Java中的整除默認(rèn)是向零取整;Python中的整除//默認(rèn)向下取整,因此Python的eval()函數(shù)中的整除也是向下取整,在本題中不能直接使用。
輸入格式
共一行,為給定表達(dá)式。
輸出格式
共一行,為表達(dá)式的結(jié)果。
數(shù)據(jù)范圍
表達(dá)式的長(zhǎng)度不超過(guò)105。
輸入樣例:
(2+2)*(1+1)
輸出樣例:
8
解題思路
對(duì)于這道題,我們可以使用兩個(gè)棧,一個(gè)棧nums用來(lái)存運(yùn)算數(shù),另外一個(gè)棧ops可以用來(lái)存運(yùn)算符,但是運(yùn)算符之間是存在優(yōu)先級(jí)的,我們還可以使用一個(gè)哈希表來(lái)儲(chǔ)存每個(gè)運(yùn)算符的優(yōu)先級(jí),可以使用數(shù)字的大小表示優(yōu)先級(jí)的高低。
第一步,遍歷字符串,可能會(huì)遇到以下情況:
1)遇到數(shù)字,將數(shù)組儲(chǔ)存到棧nums中。
2)遇到(,直接將(存到棧ops中。
3)遇到),取出棧頂兩個(gè)數(shù),取出棧頂運(yùn)算符,進(jìn)行運(yùn)算,將運(yùn)算結(jié)果存入棧nums中,如果棧ops棧頂不為空并且棧頂元素不為(,則繼續(xù)運(yùn)算,直到棧為空或者棧頂元素為(為止。
4)遇到運(yùn)算符+,-,*,/,檢查棧ops棧頂運(yùn)算符優(yōu)先級(jí)是否大于或等于遍歷遇到的運(yùn)算符,如果優(yōu)先級(jí)大,則進(jìn)行運(yùn)算操作(同上取出棧nums兩個(gè)數(shù),棧ops一個(gè)操作符進(jìn)行運(yùn)算,并將結(jié)果儲(chǔ)存到nums中),然后繼續(xù)檢查,直到棧ops為空或者ops棧頂元素為(,最后將遍歷的運(yùn)算符入棧ops。
第二步,檢查是否運(yùn)算完成。
字符串遍歷完成后,此時(shí)運(yùn)算不一定結(jié)束,檢查棧ops是否為空,不為空繼續(xù)進(jìn)行運(yùn)算操作,直到棧ops為空為止,最終nums剩余的一個(gè)數(shù)就是運(yùn)算結(jié)果。
對(duì)于運(yùn)算符優(yōu)先級(jí)的判斷我們可以通過(guò)建立哈希表,將運(yùn)算符映射一個(gè)數(shù)字,其中數(shù)字越大就表示優(yōu)先級(jí)越大。
實(shí)現(xiàn)代碼
Java版本實(shí)現(xiàn):
import java.util.*; class Main { //棧nums 存運(yùn)算數(shù) private static Deque<Integer> nums = new ArrayDeque<>(); //棧ops 存運(yùn)算符 private static Deque<Character> ops = new ArrayDeque<>(); //哈希表用來(lái)映射運(yùn)算符優(yōu)先級(jí) private static HashMap<Character, Integer> hash = new HashMap<>(); //初始化哈希表 static { hash.put('+', 1); hash.put('-', 1); hash.put('*', 2); hash.put('/', 2); } //判斷某個(gè)字符是否是數(shù)字 private static boolean isDigit(char c) { return c >= '0' &&c <= '9'; } //實(shí)現(xiàn)運(yùn)算方法 private static void eval() { //去除第二個(gè)運(yùn)算數(shù) int b = nums.pollLast(); //取出第一個(gè)運(yùn)算數(shù) int a = nums.pollLast(); //取出運(yùn)算符 char op = ops.pollLast(); //判斷符號(hào),對(duì)應(yīng)進(jìn)行運(yùn)算 if (op == '+') nums.offerLast(a + b); else if (op == '-') nums.offerLast(a - b); else if (op == '*') nums.offerLast(a * b); else if (op == '/') nums.offerLast(a / b); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); char[] cs = s.toCharArray(); for (int i = 0; i < cs.length; i++) { char c = cs[i]; if (isDigit(c)) { //遍歷的字符為數(shù)字,取出完整的數(shù)字放在數(shù)組當(dāng)中 int ret = c - '0'; int j = i + 1; while (j < cs.length && isDigit(cs[j])) { ret = ret * 10 + (cs[j] - '0'); j++; } //更新i i = j - 1; //將數(shù)字入棧 nums.offerLast(ret); } else if (c == '(') { //遇到(,直接入棧ops ops.offerLast(c); } else if (c == ')') { //遇到),進(jìn)行運(yùn)算操作,直到棧頂遇到(為止 while (!ops.isEmpty() && ops.peekLast() != '(') eval(); //遇到(,將(出棧 ops.pollLast(); } else { //遇到運(yùn)算符,則比較優(yōu)先級(jí),如棧頂運(yùn)算符優(yōu)先級(jí)大,則進(jìn)行運(yùn)算,直到棧為空或棧頂運(yùn)算符較小或棧頂運(yùn)算符為( while (!ops.isEmpty() && ops.peekLast() != '(' && hash.get(ops.peekLast()).compareTo(hash.get(c)) >= 0) eval(); //將當(dāng)前運(yùn)算符入棧 ops.offerLast(c); } } //檢查ops棧內(nèi)是否還有運(yùn)算符,如果還有,則表示運(yùn)算還沒(méi)結(jié)束,繼續(xù)運(yùn)算,直到ops棧無(wú)運(yùn)算符為止 while (!ops.isEmpty()) eval(); //輸出nums棧頂元素,即是最終運(yùn)算結(jié)果 System.out.println(nums.peekLast()); } }
C++版本實(shí)現(xiàn):
include <iostream> #include <stack> #include <unordered_map> #include <algorithm> #include <string> using namespace std; //棧1 存儲(chǔ)元素 stack<int> nums; //棧2 存儲(chǔ)操作符號(hào) stack<char> ops; //哈希表 用來(lái)存儲(chǔ)運(yùn)算符優(yōu)先級(jí) unordered_map<char, int> pri = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; void eval() { //取第二個(gè)操作數(shù) int b = nums.top(); nums.pop(); //取第一個(gè)操作數(shù) int a = nums.top(); nums.pop(); //取操作符 char op = ops.top(); ops.pop(); //進(jìn)行運(yùn)算 if (op == '+') nums.push(a + b); else if (op == '-') nums.push(a - b); else if (op == '*') nums.push(a * b); else if (op == '/') nums.push(a / b); //cout << a << " " << op << " " << b << "="; //cout << nums.top() << endl; } int main() { string s; cin >> s; for (int i = 0; i < s.size(); i++) { char c = s[i]; if (isdigit(c)) { //字符為數(shù)字,將該數(shù)字放入到儲(chǔ)存數(shù)字的棧中 int j = i + 1; int ret = s[i] - '0'; while (j < s.size() && isdigit(s[j])) { ret = ret * 10 + (s[j] - '0'); j++; } //更新i i = j - 1; nums.push(ret); } else if (c == '(') { ops.push(c); } else if (c == ')') { //遇到右括號(hào)對(duì)棧元素進(jìn)行運(yùn)算,直到遇到(為止 while (ops.size() > 0 && ops.top() != '(') eval(); ops.pop(); } else { //遇到運(yùn)算符,比較優(yōu)先級(jí),如果優(yōu)先級(jí)較高,則進(jìn)行運(yùn)算 while (ops.size() > 0 && ops.top() != '(' && pri[ops.top()] >= pri[c]) eval(); ops.push(c); } } //如果還有剩余運(yùn)算符 則繼續(xù)運(yùn)算 while (ops.size() > 0) eval(); //棧頂元素即為最終的運(yùn)算結(jié)果 cout << nums.top() << endl; return 0; }
以上就是Java棧的運(yùn)用之中綴表達(dá)式求值詳解的詳細(xì)內(nèi)容,更多關(guān)于Java中綴表達(dá)式求值的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
jasypt 集成SpringBoot 數(shù)據(jù)庫(kù)密碼加密操作
這篇文章主要介紹了jasypt 集成SpringBoot 數(shù)據(jù)庫(kù)密碼加密操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-11-11Mybatis查詢返回Map<String,Object>類(lèi)型的實(shí)現(xiàn)
本文主要介紹了Mybatis查詢返回Map<String,Object>類(lèi)型的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07Java設(shè)計(jì)模式之單例模式實(shí)例詳解【懶漢式與餓漢式】
這篇文章主要介紹了Java設(shè)計(jì)模式之單例模式,簡(jiǎn)單說(shuō)明了單例模式的原理并結(jié)合具體實(shí)例形式分析了單例模式中懶漢式與餓漢式的具體實(shí)現(xiàn)與使用技巧,需要的朋友可以參考下2017-09-09java通過(guò)Idea遠(yuǎn)程一鍵部署springboot到Docker詳解
這篇文章主要介紹了java通過(guò)Idea遠(yuǎn)程一鍵部署springboot到Docker詳解,Idea是Java開(kāi)發(fā)利器,springboot是Java生態(tài)中最流行的微服務(wù)框架,docker是時(shí)下最火的容器技術(shù),那么它們結(jié)合在一起會(huì)產(chǎn)生什么化學(xué)反應(yīng)呢?的相關(guān)資料2019-06-06Spring Boot中單例類(lèi)實(shí)現(xiàn)對(duì)象的注入方式
這篇文章主要介紹了Spring Boot中單例類(lèi)實(shí)現(xiàn)對(duì)象的注入方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-08-08Javaweb基礎(chǔ)入門(mén)HTML之table與form
HTML的全稱(chēng)為超文本標(biāo)記語(yǔ)言,是一種標(biāo)記語(yǔ)言。它包括一系列標(biāo)簽.通過(guò)這些標(biāo)簽可以將網(wǎng)絡(luò)上的文檔格式統(tǒng)一,使分散的Internet資源連接為一個(gè)邏輯整體。HTML文本是由HTML命令組成的描述性文本,HTML命令可以說(shuō)明文字,圖形、動(dòng)畫(huà)、聲音、表格、鏈接等2022-03-03