欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java棧的運(yùn)用之中綴表達(dá)式求值詳解

 更新時(shí)間:2022年11月22日 08:36:57   作者:未見(jiàn)花聞  
本文來(lái)介紹一題中綴表達(dá)式求值的問(wèn)題,就是給定一個(gè)中綴計(jì)算式,編寫(xiě)程序?qū)⑦@個(gè)式子運(yùn)算結(jié)果給計(jì)算出來(lái),其實(shí)和后綴表達(dá)式的思路差不多,都是棧的運(yùn)用問(wèn)題,感興趣的可以了解一下

棧運(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ù)密碼加密操作

    這篇文章主要介紹了jasypt 集成SpringBoot 數(shù)據(jù)庫(kù)密碼加密操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2020-11-11
  • Mac?M1安裝JDK的實(shí)戰(zhàn)避坑指南

    Mac?M1安裝JDK的實(shí)戰(zhàn)避坑指南

    這篇文章主要給大家介紹了關(guān)于Mac?M1安裝JDK避坑的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2023-02-02
  • Mybatis查詢返回Map<String,Object>類(lèi)型的實(shí)現(xiàn)

    Mybatis查詢返回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-07
  • Java跳出多重嵌套循環(huán)過(guò)程解析

    Java跳出多重嵌套循環(huán)過(guò)程解析

    這篇文章主要介紹了Java跳出多重嵌套循環(huán)過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-12-12
  • Java設(shè)計(jì)模式之單例模式實(shí)例詳解【懶漢式與餓漢式】

    Java設(shè)計(jì)模式之單例模式實(shí)例詳解【懶漢式與餓漢式】

    這篇文章主要介紹了Java設(shè)計(jì)模式之單例模式,簡(jiǎn)單說(shuō)明了單例模式的原理并結(jié)合具體實(shí)例形式分析了單例模式中懶漢式與餓漢式的具體實(shí)現(xiàn)與使用技巧,需要的朋友可以參考下
    2017-09-09
  • java多線程教程之如何使用線程池詳解

    java多線程教程之如何使用線程池詳解

    這篇文章主要給大家介紹了關(guān)于java多線程之如何使用線程池的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-11-11
  • java通過(guò)Idea遠(yuǎn)程一鍵部署springboot到Docker詳解

    java通過(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-06
  • Java框架Quartz中的Trigger簡(jiǎn)析

    Java框架Quartz中的Trigger簡(jiǎn)析

    這篇文章主要介紹了Java框架Quartz中的Trigger簡(jiǎn)析,所有類(lèi)型的trigger都有TriggerKey這個(gè)屬性,表示trigger的身份;除此之外,trigger還有很多其它的公共屬性,這些屬性,在構(gòu)建trigger的時(shí)候可以通過(guò)TriggerBuilder設(shè)置,需要的朋友可以參考下
    2023-11-11
  • Spring Boot中單例類(lèi)實(shí)現(xiàn)對(duì)象的注入方式

    Spring Boot中單例類(lèi)實(shí)現(xiàn)對(duì)象的注入方式

    這篇文章主要介紹了Spring Boot中單例類(lèi)實(shí)現(xiàn)對(duì)象的注入方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-08-08
  • Javaweb基礎(chǔ)入門(mén)HTML之table與form

    Javaweb基礎(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

最新評(píng)論