4、栈

NC52.括号序列

1. 描述

   给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
   括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。数据范围：字符串长度 0≤n≤10000
   要求：空间复杂度O(n)，时间复杂度 O(n)
   示例1输入："["
   返回值：false示例2
   输入："[]"
   返回值：true
   

2. 思路

   根据题目，这个括号严格匹配。前一个是左括号下一个必是右括号

   可以确定：1、长度是2的倍数 2、下一个和左括号不匹配可以直接返回结果

3. 代码

   #include 
   using namespace std;bool isRight(string str) {if(str.size() % 2 != 0) return false;char pre;for(int i = 0; i < str.size(); i++) {if (i % 2 == 0) pre = str[i];else {switch (pre){case '(' : if(str[i] != ')')    return  false;else    break;case '[' : if(str[i] != ']')    return  false;else    break;case '{' : if(str[i] != '}')    return  false;else    break;}}}return true;
   }int main() {string str;cin >> str;bool res = isRight(str);if(res) cout << "true" << endl;else    cout << "false" << endl;return 0;
   }
   

leecode 1614.括号的最大嵌套深度

1. 描述

   如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
   * 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
   * 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
   * 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
   类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
   * depth("") = 0
   * depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
   * depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
   * depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串
   例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。 
   示例 1：
   输入：s = "(1+(2*3)+((8)/4))+1"
   输出：3
   解释：数字 8 在嵌套的 3 层括号中。
   示例 2：
   输入：s = "(1)+((2))+(((3)))"
   输出：3 提示：
   1 <= s.length <= 100
   s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
   题目数据保证括号表达式 s 是 有效的括号表达式
   

2. 思路

   遍历读取所有字符，(添加深度，)减少深度，实时更新最大值

3. 代码

   #include 
   using namespace std;
   #include class Solution {
   public:int maxDepth(string s) {stack ch;int m = 0;int n = 0;for(auto c:s) {if(c == '('){ch.push(c);n++;}else if (c == ')') {if (ch.top() != '(')    continue;ch.pop();m = max(m, n);n--;                }}return m;}
   };int main() {string s = "(1+(2*3)+((8)/4))+1";Solution sol;cout << sol.maxDepth(s) << endl;return 0;
   }