题目：
小Y上数据结构课的时候摸鱼，听到老师在讲用栈做括号匹配，于是乎边随意写了一个合法的括号序列。但是光是写括号太无聊了，他现在想知道这个括号序列的价值。他是这样定义一个括号序列的价值的：
1、一对括号价值一分（比如”()”得一分）
2、两个合法的括号序列的拼接而成的括号序列的价值是他们的价值的和（比如”()()”价值为1+1=2）
3、嵌套的括号的序列的价值是，所嵌套的括号序列的价值的翻倍（比如”((()))”价值为1*2*2=4）
下课了，qz看到小Y写的括号序列，他一眼就推测出了规则并得到了括号序列的价值。那么问题来了，小Y写下的括号序列的价值是多少呢？
输入
一个只包含’(‘和’)’的合法的括号序列S，代表小Y写下的括号序列，一个合法的括号序列是这样定义的:
1、（）是合法的括号序列
2、若字符串A和B是合法的括号序列，那么AB也是合法的括号序列
3、若字符串A是合法的括号序列，那么(A)也是合法的括号序列
2<= |S| <=50
输出
一个字符串S，代表小Y所写的括号序列
输入样例
输出样例
题解：
用栈进行处理，对‘(’加一个num属性，记录当‘(‘出栈时所增加的值，如果当一’(‘出栈时，栈不为空，则将此位置的num加至最近的字符。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<stdio.h>
#include<algorithm>
#include<stack>
#include<string.h>
using namespace std;
char s[55];
struct point{
char c;
int num;
};
point p[55];
stack<point> sta;
int main()
{
scanf("%s", s);
int len = strlen(s);
int ans = 0;
for(int i = 0; i < len; i++){
if(s[i] == '('){
point a;
a.c = '(';
a.num = 0;
sta.push(a);
}
else{
point now = sta.top();
sta.pop();
if(sta.empty()){
if(now.num == 0)
now.num = 1;
ans += now.num;
}
else{
point a = sta.top();
sta.pop();
if(now.num == 0)
a.num += 2;
else{
a.num += now.num*2;
}
sta.push(a);
}
}
}
printf("%d\n", ans);
}
|