牛客网面试笔试 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