去除最少括号输出合法的括号字符串

 今天去福田的一家公司面试，某某奇公司。让我做一道算法题，大概这样：
要求写一个函数，输入参数为一个字符串，含有小写字母和’(’，’)'字符，要求去掉最少的括号使字符串成为一个合法的括号字符串。
例如：
输入"))(("
输出""
输入"nc(kjn(d)ca))"
输出"nc(kjn(d)ca)" 或"nc(kjn(dca))" 。
 反正就是要让括号能匹配，成对出现。我当时就懵了，因为算法一直没怎么研究，最近几天都是在看cocos引擎部分，昨天还看了android。我知道可以用stack来解决括号匹配的问题，以前有看过检测括号是否匹配的算法，但有点忘了，而且这个不是单纯检测是否合法，还要去除最少括号。最后还是没做出来。然后也没应聘上。
下午回家躺床上在想这个问题，想着想着就想出来了。代码如下：

//用数组模拟栈
char *minMoveToValidArray(char *str){
	int nNum = strlen(str);

	char *stackCh = new char[nNum];
	char *strTemp = new char[nNum+1];
	
	char *pStr = strTemp;
	int nCurIndex = 0;
	for (int i = 0; i < nNum;++i)
	{
		if (str[i]=='(')
		{
			//放入左括号
			stackCh[nCurIndex++] = str[i];

			*pStr++ = str[i];
		}else if (str[i]==')')
		{
			if (nCurIndex==0|| stackCh[nCurIndex-1]!='(')
			{
				//舍弃右括号
			}
			else{
				//放入右括号
				--nCurIndex;
				*pStr++ = str[i];
			}
		}else{
			//放入非括号字符
			*pStr++ = str[i];
		}
	}
	*pStr = '\0';

	int nMax = strlen(strTemp);
	int nLeftCount = nCurIndex;
	int nCount = nCurIndex;
	if (nCount == 0)
	{
		//没有需要去除的左括号
		strcpy_s(str, nNum + 1, strTemp);
		str[nNum] = '\0';
	}
	else{
		//最后需要去除后面那些无法匹配的左括号
		for (int i = nMax - 1, j = nMax - 1 - nCount; i >= 0; --i)
		{

			if (strTemp[i] != '(' || nLeftCount <= 0)
			{
				str[j--] = strTemp[i];
			}
			else if (nLeftCount>0){
				--nLeftCount;
			}
		}
		str[nMax - nCount] = '\0';
	}

	delete strTemp;
	delete stackCh;

	return str;
}

//用到栈结构
char *minMoveToValidStack(char *str){
	int nNum = strlen(str);

	stack<char> stackCh;
	
	char *strTemp = new char[nNum + 1];

	char *pStr = strTemp;
	int nCurIndex = 0;
	for (int i = 0; i < nNum; ++i)
	{
		if (str[i] == '(')
		{
			//放入左括号
			stackCh.push(str[i]);
			*pStr++ = str[i];
		}
		else if (str[i] == ')')
		{
			if (stackCh.empty() || stackCh.top() != '(')
			{
				//舍弃右括号
			}
			else{
				//放入右括号
				stackCh.pop();
				*pStr++ = str[i];
			}
		}
		else{
			//放入非括号字符
			*pStr++ = str[i];
		}
	}
	*pStr = '\0';

	int nMax = strlen(strTemp);
	int nLeftCount = stackCh.size();
	int nCount = nLeftCount;
	if (nCount == 0)
	{
		//没有需要去除的左括号
		strcpy_s(str, nNum + 1, strTemp);
		str[nNum] = '\0';
	}
	else{
		//最后需要去除后面那些无法匹配的左括号
		for (int i = nMax - 1, j = nMax - 1 - nCount; i >= 0; --i)
		{
			if (strTemp[i] != '(' || nLeftCount <= 0)
			{
				str[j--] = strTemp[i];
			}
			else if (nLeftCount > 0){
				--nLeftCount;
			}
		}
		str[nMax - nCount] = '\0';
	}

	delete []strTemp;

	return str;
}

 基本思路就是遍历字符串，如果是非括号字符或者左括号的话就放到目标字符串里，如果是右括号的话就判断能否跟栈顶的括号配对，可以的话也放进目标字符串里，不可以的话就说明是需要舍弃的，就不放进去。到最后的话目标字符串的后面可能有一些左括号没匹配，也需要将它们去除，最后剩下的就是我们需要的字符串了。
 简单测试了几下，都能输出正确结果，也没做优化。如果有错误请赐教。
ps:最后想吐槽一次，用纸写代码真反人类。

---

以下是题外话。
虽然面试没成功，但遇到了以前公司的同事，他在这公司里做没多久，感谢他认出了我，叫住了我。我在离开的时候心情不好闷头走，是有听到有人叫我名字，但我以为是听错了就没回头。最后还是他跑出来追我。他人挺nice的。聊了几句，最后加了wx。让我心情也没那么郁闷了。缘分真是一个圆。

本文地址：https://blog.csdn.net/dan452819043/article/details/114328534