2014百度校招笔试题

二、算法与程序设计题（本题共45分）

1. 使用C/C++编写函数，实现字符串反转，要求不使用任何系统函数，且时间复杂度最小，函数原型：char* reverse_str(char* str)。(15分)

算法实现：

/*实现字符串翻转*/
char* reverse_str(char* str)
{
	if(NULL == str) //字符串为空直接返回
	{
		return str;
	}
	char *begin;
	char *end;
	begin = end = str;

	while(*end != '\0') //end指向字符串的末尾
	{
		end++;
	}
	--end;

	char temp;
	while(begin < end) //交换两个字符
	{
		temp = *begin;
		*begin = *end;
		*end = temp;
		begin++;
		end--;
	}

	return str; //返回结果
}
void main()
{
	char str[] = "123456";
	printf(reverse_str(str));
}

2. 给定一个如下格式的字符串，(1,(2,3),(4,(5,6),7))括号内的元素可以是数字，也可以是另一个括号，请实现一个算法消除嵌套的括号，比如把上面的表达式变成：(1,2,3,4,5,6,7)，如果表达式有误请报错。(15分)

分析：此题实际上考的是站的应用，即曾经练过的括号匹配问题。

算法实现：

#include <stdio.h>
#include <STACK>
using namespace std;

/*判断表达式是否合法*/
bool IsValid(char *str)
{
	if(NULL == str) return false;

	stack<char> op;

	while(*str)
	{
		if(*str == '(')
		{
			op.push(*str++);
		}
		else if(*str == ')')
		{
			if(op.empty())
				return false;
			else
				op.pop();
			str++;
		}
		else
		{
			str++;
		}
	}

	if(op.empty())
		return true;
	else
		return false;
}
/*消除中间的括号*/
char *Elimination_brackets(char *str)
{
	if(str == NULL)  //字符串为空返回
		return str;  
	
	char* temp = new char[strlen(str)+1];  
	char* result = temp;  
	
	*temp++ = *str++; //跳过第一个左括号
	while(*str!='\0')  
	{  
		if(*str == ')' || *str=='(')  //有括号，跳过赋值
		{  
			str++;  
			continue;  
		}  
		*temp++ = *str++;  
	}  
	*temp++ = ')';  //将有括号加上
	*temp = '\0';  
	
	return result;  
	
}
void main()
{
	  char str[] = "(1,(1,0),3)";
	  int a = 0;
	  if(IsValid(str))
	  {
		  printf(Elimination_brackets(str));
	  }

}