学习总结三十三

括号序列

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

思路：

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);//定义一个向量，用于标记括号是否匹配，初始化为0
	for (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    就是这样。