牛客網 面試筆試 TOP 101 ?

1. 題目

描述

請寫一個整數計算器，支持加減乘三種運算和括號。

數據范圍：0≤∣s∣≤100，保證計算結果始終在整型范圍內

要求：空間復雜度： O(n)，時間復雜度 O(n)

示例1

輸入：

"1+2"

返回值：

3

示例2

輸入：

"(2*(3-4))*5"

返回值：

-10

示例3

輸入：

"3+2*3*4-1"

返回值：

26

2. 解題思路

表達式的求值可以通過棧來完成，具體思路如下：

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

• Python編碼：嗶哩嗶哩_bilibili

• Java編碼：嗶哩嗶哩_bilibili

• Golang編碼：嗶哩嗶哩_bilibili

3. 編碼實現

核心代碼如下：

/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** 返回表達式的值* @param s string字符串 待計算的表達式* @return int整型*/
func solve(s string) int {// write code here// 1. 定義棧、輔助變量stack := NewStack()num := 0sign := uint8('+')// 2. 遍歷字符串中的字符進行計算for i := 0; i < len(s); i++ {v := s[i]// 2.1 如果是空格，跳過if v == ' ' {continue}// 2.2 如果是數字，計算對應的值if isDigit(v) {num = num*10 + int(v-'0')}// 2.3 如果是 左括號 對括號里的內容進行計算（遞歸）if v == '(' {j := i + 1countPartition := 1for countPartition > 0 {if s[j] == '(' {countPartition++}if s[j] == ')' {countPartition--}j++}//遞歸求解括號里的內容，遞歸的字符串為：s[i+1,j-1),左閉右開num = solve(s[i+1 : j-1])i = j - 1 // 控制循環變量值：i 更改 （for循環結束一輪，i值會再加1）}// 2.4 如果是運算符，進行運算（入棧的數字已經是計算過的）if !isDigit(v) || i == len(s)-1 {if sign == '+' {stack.Push(num) //加號 直接入棧} else if sign == '-' {stack.Push(-1 * num) //減號，入棧的是負數} else if sign == '*' {tmp := stack.Pop()stack.Push(tmp * num)} else if sign == '/' {tmp := stack.Pop()stack.Push(tmp / num)} else {}num = 0sign = v}}//3.將棧中的數據累加返回res := 0for !stack.isEmpty() {res += stack.Pop() //如果棧非空，對棧中的值求和}return res
}func isDigit(v uint8) bool {if v >= '0' && v <= '9' {return true}return false
}

具體完整代碼你可以參考下面視頻的詳細講解。

• Python編碼：Python數據結構LeetCode筆試面試算法_嗶哩嗶哩_bilibiliPython數據結構LeetCode筆試面試算法,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1372872

• Java編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367926

• Golang編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364952

4.小結

表達式的求值可以通過棧來完成，具體操作方法為：

1. 定義一個棧，棧中保存求值的結果；

2. 依次遍歷運算字符串：

????????1）如果字符是數字，通過變量保存該數字；

????????2）如果是括號，截取括號中的字符串遞歸調用；

????????3）如果是運算符，進行入棧操作：加號直接入棧；減號入棧為負數；乘號則與出棧的值相乘再入棧；除號則與出棧的值相除再入棧（乘除的優先級高，因此需要先出棧操作之后再入棧）。

3. 計算結果:

????????將棧中的值進行累加，就是表達式的值。

《數據結構與算法》深度精講課程正式上線啦！7 大核心算法模塊全解析：

? ? ? 鏈表

? ? ? 二叉樹

? ? ? 二分查找、排序

? ? ? 堆、棧、隊列

? ? ? 回溯算法

? ? ? 哈希算法

? ? ? 動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建扎實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：Python數據結構LeetCode筆試面試算法_嗶哩嗶哩_bilibiliPython數據結構LeetCode筆試面試算法,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ss897667807

• Java編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ss161443488

• Golang編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ss63997

對于數據結構與算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：誰言寸草心，報得三春輝。