学习总结三十三

括号序列

 如果它是一个右括号，考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。简单理解，找到一个右括号，向左找一个左括号匹配，找不到就补齐。

思路：

1.输入一个字符串，对这个字符串从左到右扫描

2.如果碰到左括号，入栈（字符，字符所在位置--数组下标）

如果是右括号，与栈顶匹配

栈为空，跳过

匹配不上，跳过

如果匹配得上，出栈，将能匹配上的两个位置标记为1

3.再对字符串进行扫描，如果位置标记为已匹配，则输出原字符。反之补齐

#include<iostream>
#include<string>
#include<stack>
using namespace std;
struct point {char c;int pos;
};
int main()
{string s;stack<point> ps;bool mark[110] = {0};cin >> s;for (int i = 0; i < s.size(); i++){if (s[i] == '(' || s[i] == '[') {ps.push({ s[i],i });continue;}if (ps.empty())continue;point p = ps.top();if ((s[i] == ')' && p.c == '(') || (s[i] == ']' && p.c == '[')){mark[i] = 1;mark[p.pos] = 1;ps.pop();}for (int i = 0; i < s.size(); i++){if (mark[i] == 1)cout << s[i];else if (s[i] == '(' || s[i] == ')')cout << "()";else cout << "[]";}}return 0;
}

10分。。。

最终代码:
 

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<utility>
using namespace std;int main()
{string s;cin >> s;stack<pair<char, int>> sta;//定义一个栈，存储字符和索引vector<int>mark(s.size(), 0);//定义一个向量，用于标记括号是否匹配，初始化为0for (int i = 0; i < s.size(); i++){if (s[i] == ')') {if (!sta.empty() && sta.top().first == '(') {  //栈不为空且栈顶字符为"（"mark[sta.top().second] = 1;//标记栈顶字符对应的括号为匹配mark[i] = 1;//标记当前对应字符对应的括号为匹配sta.pop();}}else if (s[i] == ']') {if (!sta.empty() && sta.top().first == '[') {mark[sta.top().second] = 1;mark[i] = 1;sta.pop();}}else sta.push({ s[i],i });//都不是右括号，则压入栈中}for (int i = 0; i < s.size(); i++){if (mark[i] == 0)//没有匹配上的{switch (s[i]) //根据字符类型补齐{case '(':cout << "()"; break;case ')':cout << "()"; break;case '[':cout << "[]"; break;case ']':cout << "[]"; break;}}else cout << s[i];}return 0;
}

pair：通俗来说就是一个结构体。代码中可以写成：

struct point {char c;int pos;
};

first-->c    second--->pos    就是这样。