Java棧的運(yùn)用之中綴表達(dá)式求值詳解
棧運(yùn)用題:中綴表達(dá)式求值
題目詳情
給定一個(gè)表達(dá)式,其中運(yùn)算符僅包含 +,-,*,/(加 減 乘 整除),可能包含括號,請你求出表達(dá)式的最終值。
注意:
數(shù)據(jù)保證給定的表達(dá)式合法。
題目保證符號 - 只作為減號出現(xiàn),不會(huì)作為負(fù)號出現(xiàn),例如,-1+2,(2+2)*(-(1+1)+2) 之類表達(dá)式均不會(huì)出現(xiàn)。
題目保證表達(dá)式中所有數(shù)字均為正整數(shù)。
題目保證表達(dá)式在中間計(jì)算過程以及結(jié)果中,均不超過 231−1。
題目中的整除是指向 0 取整,也就是說對于大于 0 的結(jié)果向下取整,例如 5/3=1,對于小于 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
解題思路
對于這道題,我們可以使用兩個(gè)棧,一個(gè)棧nums用來存運(yùn)算數(shù),另外一個(gè)棧ops可以用來存運(yùn)算符,但是運(yùn)算符之間是存在優(yōu)先級的,我們還可以使用一個(gè)哈希表來儲(chǔ)存每個(gè)運(yùn)算符的優(yōu)先級,可以使用數(shù)字的大小表示優(yōu)先級的高低。
第一步,遍歷字符串,可能會(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)先級是否大于或等于遍歷遇到的運(yùn)算符,如果優(yōu)先級大,則進(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é)果。
對于運(yùn)算符優(yōu)先級的判斷我們可以通過建立哈希表,將運(yùn)算符映射一個(gè)數(shù)字,其中數(shù)字越大就表示優(yōu)先級越大。


實(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)先級
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();
//判斷符號,對應(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)先級,如棧頂運(yùn)算符優(yōu)先級大,則進(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ǔ)操作符號
stack<char> ops;
//哈希表 用來存儲(chǔ)運(yùn)算符優(yōu)先級
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 == ')')
{
//遇到右括號對棧元素進(jìn)行運(yùn)算,直到遇到(為止
while (ops.size() > 0 && ops.top() != '(') eval();
ops.pop();
} else {
//遇到運(yùn)算符,比較優(yōu)先級,如果優(yōu)先級較高,則進(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á)式求值的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Intellij IDEA使用restclient測試的教程圖解
這篇文章主要介紹了Intellij IDEA使用restclient測試的教程圖解,本文通過圖文并茂的形式給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-01-01
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ā)送郵件,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-12-12
JAVA 根據(jù)身份證計(jì)算年齡的實(shí)現(xiàn)代碼
這篇文章主要介紹了JAVA 根據(jù)身份證計(jì)算年齡的實(shí)例代碼及java根據(jù)出生日期獲得年齡的方法,代碼簡單易懂,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2018-05-05
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)語法詳解
增強(qiáng)型 for 循環(huán)(也稱為 “for-each” 循環(huán))是 Java 從 JDK 5 開始引入的一種便捷循環(huán)語法,旨在簡化對數(shù)組或集合類的迭代操作,這篇文章主要介紹了java 增強(qiáng)型for循環(huán) 詳解,需要的朋友可以參考下2025-04-04
Spring boot項(xiàng)目使用thymeleaf模板過程詳解
這篇文章主要介紹了Spring boot項(xiàng)目使用thymeleaf模板過程詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07

