最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

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

 更新時(shí)間:2022年11月22日 08:36:57   作者:未見花聞  
本文來介紹一題中綴表達(dá)式求值的問題,就是給定一個(gè)中綴計(jì)算式,編寫程序?qū)⑦@個(gè)式子運(yùn)算結(jié)果給計(jì)算出來,其實(shí)和后綴表達(dá)式的思路差不多,都是棧的運(yù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) 之類表達(dá)式均不會(huì)出現(xiàn)。

題目保證表達(dá)式中所有數(shù)字均為正整數(shù)。

題目保證表達(dá)式在中間計(jì)算過程以及結(jié)果中,均不超過 231−1。

題目中的整除是指向 0 取整,也就是說對(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á)式的長度不超過105。

輸入樣例:

(2+2)*(1+1)

輸出樣例:

8

解題思路

對(duì)于這道題,我們可以使用兩個(gè)棧,一個(gè)棧nums用來存運(yùn)算數(shù),另外一個(gè)棧ops可以用來存運(yùn)算符,但是運(yùn)算符之間是存在優(yōu)先級(jí)的,我們還可以使用一個(gè)哈希表來儲(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í)的判斷我們可以通過建立哈希表,將運(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<>();
    
    //哈希表用來映射運(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)算還沒結(jié)束,繼續(xù)運(yùn)算,直到ops棧無運(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;


//哈希表 用來存儲(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)文章

  • 2021年最新Redis面試題匯總(2)

    2021年最新Redis面試題匯總(2)

    在程序員面試過程中redis相關(guān)的知識(shí)是常被問到的話題。這篇文章主要介紹了幾道Redis面試題,整理一下分享給大家,感興趣的小伙伴們可以參考一下
    2021-07-07
  • Intellij IDEA使用restclient測試的教程圖解

    Intellij IDEA使用restclient測試的教程圖解

    這篇文章主要介紹了Intellij IDEA使用restclient測試的教程圖解,本文通過圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-01-01
  • java實(shí)現(xiàn)多線程之定時(shí)器任務(wù)

    java實(shí)現(xiàn)多線程之定時(shí)器任務(wù)

    本篇文章主要介紹了java實(shí)現(xiàn)多線程之定時(shí)器任務(wù),小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-02-02
  • Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件

    Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件

    這篇文章主要介紹了Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-12-12
  • JAVA 根據(jù)身份證計(jì)算年齡的實(shí)現(xiàn)代碼

    JAVA 根據(jù)身份證計(jì)算年齡的實(shí)現(xiàn)代碼

    這篇文章主要介紹了JAVA 根據(jù)身份證計(jì)算年齡的實(shí)例代碼及java根據(jù)出生日期獲得年齡的方法,代碼簡單易懂,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友參考下吧
    2018-05-05
  • springcloud檢索中間件?ElasticSearch?分布式場景的使用

    springcloud檢索中間件?ElasticSearch?分布式場景的使用

    單機(jī)的elasticsearch做數(shù)據(jù)存儲(chǔ),必然面臨兩個(gè)問題:海量數(shù)據(jù)存儲(chǔ)問題、單點(diǎn)故障問題,本文重點(diǎn)給大家介紹springcloud檢索中間件?ElasticSearch?分布式場景的運(yùn)用,感興趣的朋友跟隨小編一起看看吧
    2023-10-10
  • java 增強(qiáng)型for循環(huán)語法詳解

    java 增強(qiáng)型for循環(huán)語法詳解

    增強(qiáng)型 for 循環(huán)(也稱為 “for-each” 循環(huán))是 Java 從 JDK 5 開始引入的一種便捷循環(huán)語法,旨在簡化對(duì)數(shù)組或集合類的迭代操作,這篇文章主要介紹了java 增強(qiáng)型for循環(huán) 詳解,需要的朋友可以參考下
    2025-04-04
  • Java多線程并發(fā)編程 并發(fā)三大要素

    Java多線程并發(fā)編程 并發(fā)三大要素

    這篇文章主要介紹了Java多線程并發(fā)編程 并發(fā)三大要素,需要的朋友可以參考下
    2017-05-05
  • Spring boot項(xiàng)目使用thymeleaf模板過程詳解

    Spring boot項(xiàng)目使用thymeleaf模板過程詳解

    這篇文章主要介紹了Spring boot項(xiàng)目使用thymeleaf模板過程詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-07-07
  • Java中解壓縮文件的方法詳解(通用)

    Java中解壓縮文件的方法詳解(通用)

    在軟件開發(fā)和數(shù)據(jù)處理領(lǐng)域,文件的解壓縮和壓縮是常見的任務(wù),下面這篇文章主要給大家介紹了關(guān)于Java中解壓縮文件的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2024-06-06

最新評(píng)論

香河县| 丰台区| 玛曲县| 华容县| 南平市| 康马县| 陈巴尔虎旗| 凤阳县| 松滋市| 兴隆县| 永春县| 富民县| 福海县| 辰溪县| 南开区| 卓尼县| 龙井市| 东光县| 安岳县| 碌曲县| 建德市| 玉环县| 房山区| 江安县| 崇左市| 迁安市| 且末县| 蒲城县| 都江堰市| 平顶山市| 崇仁县| 苍山县| 曲靖市| 巴马| 襄汾县| 故城县| 丹东市| 郸城县| 仙居县| 尚义县| 武冈市|