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));
}
}