牛客网 面试笔试 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 := 0
sign := 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 + 1
countPartition := 1
for 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 = 0
sign = v
}
}
//3.将栈中的数据累加返回
res := 0
for !stack.isEmpty() {
res += stack.Pop() //如果栈非空，对栈中的值求和
}
return res
}
func isDigit(v uint8) bool {
if v >= '0' && v <= '9' {
return true
}
return false
}具体完整代码你可以参考下面视频的详细讲解。
Java编码：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1367926Golang编码：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364952
4.小结
表达式的求值可以通过栈来完成，具体操作方法为：
1. 定义一个栈，栈中保存求值的结果；
2. 依次遍历运算字符串：
1）如果字符是数字，通过变量保存该数字；
2）如果是括号，截取括号中的字符串递归调用；
3）如果是运算符，进行入栈操作：加号直接入栈；减号入栈为负数；乘号则与出栈的值相乘再入栈；除号则与出栈的值相除再入栈（乘除的优先级高，因此需要先出栈操作之后再入栈）。
3. 计算结果:
将栈中的值进行累加，就是表达式的值。
《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：
✅ 链表
✅ 二叉树
✅ 二分查找、排序
✅ 堆、栈、队列
✅ 回溯算法
✅ 哈希算法
✅ 动态规划
无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！
Java编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss161443488Golang编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss63997
对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句：谁言寸草心，报得三春辉。