题目描述

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

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

• 它是一个空字符串，或者
• 它可以被写成 AB（A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

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

样例

输入："())"
输出：1

输入："((("
输出：3

输入："()"
输出：0

输入："()))(("
输出：4

注意

• S.length <= 1000
• S 仅由 '(' 和 ')' 组成。

算法

(栈) $O(n)$

1. 判断是否是一个合法的括号序列只需要用栈扫一遍。如果遇到左括号，则将其压栈；遇到右括号，如果栈空则不合法；最后如果栈非空则不合法。
2. 这道题中，如果遇到右括号且栈空，则需要在前边补左括号，即答案加一。最后如果栈非空，则需要在最后补右括号。

时间复杂度

• 只需要扫所有字符一次，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int minAddToMakeValid(string S) {
        stack<int> s;
        int ans = 0;

        for (int i = 0; i < S.length(); i++) {
            if (S[i] == '(') {
                s.push(0);
            }
            else {
                if (s.empty())
                    ans++;
                else
                    s.pop();
            }
        }

        ans += s.size();
        return ans;
    }
};