leetcode 1541. 平衡括号字符串的最少插入次数

Problem: 1541. 平衡括号字符串的最少插入次数

栈内只长期保存左括号’(‘，临时保存右括号’)’

若栈空且最开始的字符是")"，则统计右括号的频次，然后累加结果if(tr.size() == 0 && l < n && s[l]==‘)’) {

然后判断())这种情况，右括号需要挨在一起，此时pop掉，若是()(这种情况累加结果ans++然后pop掉

最后若栈顶是’)‘，则ans++，pop掉，最后栈内都是左括号’('，此时ans += m*2

Code

class Solution { public: int minInsertions(string s) { string tr; int l = 0; int n = s.size(), m, ans = 0; char ch; for(int i = 0; i < n; i++) { m = tr.size(); l = i; if(tr.size() == 0 && l < n && s[l]==')') { while(l < n && s[l]==')') l++; if(((l-i)&1)==1) ans += (l-i+1)/2 + 1; else ans += (l-i)/2; i = l; if(i==n) break; } ch = s[i]; if(ch == ')') { if(m > 1 && tr[m-1]==')' && tr[m-2]=='(') { tr.pop_back(); tr.pop_back(); continue; } if(i+1 < n && s[i+1]!=')') { ans++; tr.pop_back(); continue; } } tr += ch; } if(tr==")") return ans; m = tr.size(); if(tr.size() > 0) { if(tr.back()==')') ans += (m-2)*2 + 1; else ans += m*2; } return ans; } };