数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学C++ 中括号的分值
假设我们有一个平衡的括号字符串 S，我们需要根据以下规则计算字符串的分值 -
- () 的分值为 1
- AB 的分值为 A + B，其中 A 和 B 是两个平衡的括号字符串。
- (A) 的分值为 2 * A，其中 A 是一个平衡的括号字符串。
因此，如果输入类似于“(()(()))”，那么输出将为 6。
为了解决此问题，我们将按照以下步骤操作 -
- ans := 0，定义一个栈 st
- 对于 i 的范围从 0 到字符串 S 的长度
- 如果 S[i] 是左括号，那么将 -1 插入栈
- 否则
- 如果栈顶为 -1，那么从栈中删除并插入 1
- 否则
- x := 0
- 当栈顶不为 -1 时
- 将 x 增加 st 的值，从 st 中删除
- x := x * 2
- 从 st 中删除，并插入 x
- 当栈不为空时
- 将 ans 增加 st 中的值，并删除栈顶元素
- 返回 ans。
让我们看一下以下实现来加深理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int scoreOfParentheses(string S) {
int ans = 0;
stack <int> st;
for(int i = 0; i < S.size(); i+=1){
if(S[i] == '('){
st.push(-1);
}else{
if(st.top() == -1){
st.pop();
st.push(1);
}else{
int x = 0;
while(st.top() != -1){
x += st.top();
st.pop();
}
x *= 2;
st.pop();
st.push(x);
}
}
}
while(!st.empty()){
ans += st.top();
st.pop();
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.scoreOfParentheses("(()(()))"));
}输入
"(()(()))"
输出
6
更新于： 05-05-2020
295 次浏览
广告