数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用 C++ 在括号字符串中查找平衡点。
在这里，我们将学习如何在括号字符串中找到平衡点。平衡点是指索引 I，在该索引之前左括号的数量等于其之后右括号的数量。假设括号字符串类似于“(()))(()()())))”，仔细观察，我们可以得到
因此，从 0 到 9 的左括号数量为 5，从 9 到 14 的右括号数量也为 5，所以这是平衡点。
为了解决这个问题，我们必须遵循以下几个步骤：
- 存储字符串中每个索引 i 之前的左括号数量。
- 存储字符串中每个索引 I 之前的右括号数量，但应从最后一个索引开始。
- 检查某个索引的左括号数量和右括号数量是否相同。
示例
#include<iostream>
#include<cmath>
using namespace std;
int findEqualPoint(string str) {
int total_length = str.length();
int open[total_length+1] = {0}, close[total_length+1] = {0};
int index = -1;
open[0] = 0;
close[total_length] = 0;
if (str[0]=='(') //check whether first bracket is opening or not, if so mark open[1] = 1
open[1] = 1;
if (str[total_length-1] == ')') //check whether first bracket is closing or not, if so mark close[end] = 1
close[total_length-1] = 1;
for (int i = 1; i < total_length; i++) {
if ( str[i] == '(' )
open[i+1] = open[i] + 1;
else
open[i+1] = open[i];
}
for (int i = total_length-2; i >= 0; i--) {
if ( str[i] == ')' )
close[i] = close[i+1] + 1;
else
close[i] = close[i+1];
}
if (open[total_length] == 0)
return total_length;
if (close[0] == 0)
return 0;
for (int i=0; i<=total_length; i++)
if (open[i] == close[i])
index = i;
return index;
}
int main() {
string str = "(()))(()()())))";
cout << "Index of equal point: " << findEqualPoint(str);
}输出
Index of equal point: 9
更新于：2019年10月29日
288 次查看
广告