11 使括号有效的最少添加（921）

作者: Turbo时间限制: 1S章节: DS:栈

晚于: 2020-07-15 12:00:00后提交分数乘系数50%

截止日期: 2020-07-22 12:00:00

问题描述 :

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者

它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者

它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入："())"

输出：1

示例 2：

输入："((("

输出：3

示例 3：

输入："()"

输出：0

示例 4：

输入："()))(("

输出：4

说明：

S.length <= 1000

S 只包含 '(' 和 ')' 字符。

输入说明 :

输入一个由 '(' 和 ')' 括号组成的字符串 S

输出说明 :

输出一个整数，表示为使结果字符串有效而必须添加的最少括号数

输入范例 :

()))((

输出范例：

//遍历S字符串，stack的顶部与S中的字符串比较，匹配得到就下一个，
//没有就push入stack，最后结果堆得大小就是要添加的括号个数
#include <iostream>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    int minAddToMakeValid(string S) 
    {
        stack<char> temps;
        for(int i=0;i<S.size();i++)
        {
            if(temps.empty())
                temps.push(S[i]);
            else
            {
                if(S[i]==')'&&temps.top()=='(')
                    temps.pop();
                else
                    temps.push(S[i]);
            }
        }
    return temps.size();
    }
};
int main()
{
    string a;
    cin>>a;

    int t;
    t=Solution(). minAddToMakeValid(a);
    cout<<t<<endl;
    return 0;

}