设计一个算法,求在一个有效算术表达式中最大的括号嵌套深度,有效算术表达式用字符串表示,且表达式中的括号符合配对规则,引入栈或队列的基本算法完成此算法,在文件夹homework中的demo02.cpp文件中补全代码 例如输入"(1+(2*3)+((8)/4))+1",输出3,因为数字8在嵌套的3层括号中
时间: 2023-05-24 09:01:44 浏览: 54
下面是实现算法的代码:
```
#include <iostream>
#include <stack>
using namespace std;
int maxDepth(string str) {
stack<char> s;
int maxDepth = 0, curDepth = 0; // 分别为最大深度和当前深度
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') { // 遇到左括号入栈
s.push(str[i]);
curDepth++; // 当前深度加1
if (curDepth > maxDepth) // 如果当前深度大于最大深度
maxDepth = curDepth; // 更新最大深度
} else if (str[i] == ')') { // 遇到右括号出栈
s.pop();
curDepth--; // 当前深度减1
}
}
return maxDepth;
}
int main() {
string str = "(1 (2*3) ((8)/4)) 1";
cout << maxDepth(str) << endl; // 输出3
return 0;
}
```
对于输入的字符串,我们使用一个栈来判断括号的嵌套深度,遇到左括号就入栈并将当前深度加1,而遇到右括号就出栈并将当前深度减1。同时,我们也需要记录最大深度,随着遍历的进行不断更新。最后返回最大深度即可。
注意:本实现中没有对无效算术表达式(不符合配对规则的括号)进行判断和报错处理,需要自行添加。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)