Java棧的運用之中綴表達式求值詳解

更新時間：2022年11月22日 08:36:57 作者：未見花聞

本文來介紹一題中綴表達式求值的問題，就是給定一個中綴計算式，編寫程序?qū)⑦@個式子運算結(jié)果給計算出來，其實和后綴表達式的思路差不多，都是棧的運用問題，感興趣的可以了解一下

棧運用題：中綴表達式求值

題目詳情

給定一個表達式，其中運算符僅包含 +,-,*,/（加減乘整除），可能包含括號，請你求出表達式的最終值。

注意：

數(shù)據(jù)保證給定的表達式合法。

題目保證符號 - 只作為減號出現(xiàn)，不會作為負號出現(xiàn)，例如，-1+2,(2+2)*(-(1+1)+2) 之類表達式均不會出現(xiàn)。

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

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

題目中的整除是指向 0 取整，也就是說對于大于 0 的結(jié)果向下取整，例如 5/3=1，對于小于 0 的結(jié)果向上取整，例如 5/(1−4)=−1。

C++和Java中的整除默認是向零取整；Python中的整除//默認向下取整，因此Python的eval()函數(shù)中的整除也是向下取整，在本題中不能直接使用。

輸入格式

共一行，為給定表達式。

輸出格式

共一行，為表達式的結(jié)果。

數(shù)據(jù)范圍

表達式的長度不超過10⁵。

輸入樣例：

(2+2)*(1+1)

輸出樣例：

8

解題思路

對于這道題，我們可以使用兩個棧，一個棧nums用來存運算數(shù)，另外一個棧ops可以用來存運算符，但是運算符之間是存在優(yōu)先級的，我們還可以使用一個哈希表來儲存每個運算符的優(yōu)先級，可以使用數(shù)字的大小表示優(yōu)先級的高低。

第一步，遍歷字符串，可能會遇到以下情況：

1）遇到數(shù)字，將數(shù)組儲存到棧nums中。

2）遇到（，直接將（存到棧ops中。

3）遇到），取出棧頂兩個數(shù)，取出棧頂運算符，進行運算，將運算結(jié)果存入棧nums中，如果棧ops棧頂不為空并且棧頂元素不為（，則繼續(xù)運算，直到棧為空或者棧頂元素為（為止。

4）遇到運算符+，-，*，/，檢查棧ops棧頂運算符優(yōu)先級是否大于或等于遍歷遇到的運算符，如果優(yōu)先級大，則進行運算操作（同上取出棧nums兩個數(shù)，棧ops一個操作符進行運算，并將結(jié)果儲存到nums中），然后繼續(xù)檢查，直到棧ops為空或者ops棧頂元素為（，最后將遍歷的運算符入棧ops。

第二步，檢查是否運算完成。

字符串遍歷完成后，此時運算不一定結(jié)束，檢查棧ops是否為空，不為空繼續(xù)進行運算操作，直到棧ops為空為止，最終nums剩余的一個數(shù)就是運算結(jié)果。

對于運算符優(yōu)先級的判斷我們可以通過建立哈希表，將運算符映射一個數(shù)字，其中數(shù)字越大就表示優(yōu)先級越大。

實現(xiàn)代碼

Java版本實現(xiàn)：

import java.util.*;

class Main {
    //棧nums 存運算數(shù)
    private static Deque<Integer> nums = new ArrayDeque<>();
    //棧ops 存運算符
    private static Deque<Character> ops = new ArrayDeque<>();
    
    //哈希表用來映射運算符優(yōu)先級
    private static HashMap<Character, Integer> hash = new HashMap<>();
    
    //初始化哈希表
    static {
        hash.put('+', 1);
        hash.put('-', 1);
        hash.put('*', 2);
        hash.put('/', 2);
    }
    
    //判斷某個字符是否是數(shù)字
    private static boolean isDigit(char c) {
        return c >= '0' &&c <= '9';
    }
    
    //實現(xiàn)運算方法
    private static void eval() {
        //去除第二個運算數(shù)
        int b = nums.pollLast();
        //取出第一個運算數(shù)
        int a = nums.pollLast();
        //取出運算符
        char op = ops.pollLast();
        
        //判斷符號，對應進行運算
        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ù)組當中
                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 == ')') {
                //遇到)，進行運算操作，直到棧頂遇到(為止
                while (!ops.isEmpty() && ops.peekLast() != '(') eval();
                //遇到(，將(出棧
                ops.pollLast();
            } else {
                //遇到運算符，則比較優(yōu)先級，如棧頂運算符優(yōu)先級大，則進行運算，直到棧為空或棧頂運算符較小或棧頂運算符為(
                while (!ops.isEmpty() && ops.peekLast() != '(' && hash.get(ops.peekLast()).compareTo(hash.get(c)) >= 0) eval();
                
                //將當前運算符入棧
                ops.offerLast(c);
            }
        }
        
        //檢查ops棧內(nèi)是否還有運算符，如果還有，則表示運算還沒結(jié)束，繼續(xù)運算，直到ops棧無運算符為止
        while (!ops.isEmpty()) eval();
        
        //輸出nums棧頂元素，即是最終運算結(jié)果
        System.out.println(nums.peekLast());
    }
}

C++版本實現(xiàn)：

include <iostream>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

//棧1 存儲元素
stack<int> nums;
//棧2 存儲操作符號
stack<char> ops;


//哈希表 用來存儲運算符優(yōu)先級
unordered_map<char, int> pri = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void eval()
{
    //取第二個操作數(shù)
    int b = nums.top();
    nums.pop();
    //取第一個操作數(shù)
    int a = nums.top();
    nums.pop();
    
    //取操作符
    char op = ops.top();
    ops.pop();
    
    //進行運算
    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ù)字放入到儲存數(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 == ')') 
        {
            //遇到右括號對棧元素進行運算，直到遇到(為止
            while (ops.size() > 0 && ops.top() != '(') eval();
            ops.pop();
        } else {
            //遇到運算符，比較優(yōu)先級，如果優(yōu)先級較高，則進行運算
            while (ops.size() > 0 && ops.top() != '(' && pri[ops.top()] >= pri[c]) eval();
            ops.push(c);
        }
    }
    
    //如果還有剩余運算符 則繼續(xù)運算
    while (ops.size() > 0) eval();
    //棧頂元素即為最終的運算結(jié)果
    cout << nums.top() << endl;
    return 0;
}

以上就是Java棧的運用之中綴表達式求值詳解的詳細內(nèi)容，更多關于Java中綴表達式求值的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: