华为2020届实习生笔试第二题
程序员文章站
2022-07-13 14:27:37
...
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
//程序的时间复杂度为num*repeat
bool leftbracket(char a)
{
if ((a =='(') || (a=='{') || (a=='['))
{
return true;
}
else
{
return false;
}
}
bool rightbracket(char b)
{
if ((b == ')') || (b == '}') || (b == ']'))
{
return true;
}
else
{
return false;
}
}
stack <int> lef;
vector <int> rig;
int main()
{
string str;
cin >> str;
//通过之前对这道题的分析,我选中通过下标对字符串进行操作
int len = str.size();
if (len > 100)
return 0;
//先遍历整个字符串,找到括号(){}[]的下标
for (int i = 0; i < len; i++)
{
if ( leftbracket(str[i]) )
{
lef.push(i);
}
if (rightbracket(str[i]))
{
rig.push_back(i);
}
}
rig.push_back(0);//防止越界
rig.push_back(0);//防止越界
int num = lef.size();//字符串中括号的个数
if (num == 0)
{
reverse(str.begin(), str.end());
cout << str << endl;
return 0;
}
for (int j = 0 ; j < num ; j++)
{
int begin = lef.top();//左括号最右边的
int end = rig[j];//右括号最左边的
int repeat = str[begin - 1]-'0';//括号里字符重复的个数
string temp = "";
string temp1 = "";
temp = str.substr(begin + 1,end-begin-1);//将括号里面的字符提取出来
int n = temp.size();//括号里字符的长度
for (int k = 0; k < repeat; k++)
{
temp1 = temp1 + temp;
}
str.erase(begin-1, end - begin +2);//将str字符串里面括号及括号里面的字符删除
str.insert(begin - 1, temp1);//将字符串重复reapeat次后,再插入字符串
lef.pop();
if (j<num-1)
{
if ((3 + n) >= (n*repeat))
{
rig[j + 1] = rig[j + 1] - 3 - n + n*repeat;//当删除插入字符后,后续的右括号的下标都改变了
rig[j + 2] = rig[j + 2] - 3 - n + n*repeat;//改变后续右括号的字符下标
}
if ((3 + n) < (n*repeat))
{
rig[j + 1] = rig[j + 1] - 3 - n + n*repeat;
rig[j + 2] = rig[j + 2] - 3 - n + n*repeat;
}
}
}
reverse(str.begin(),str.end());
cout << str << endl;
system("pause");
return 0;
}