2010年机试真题
1．输入一串整数，输入命令排序！
输入 a t 在这串整数后面添加整数 t，
输入 c\m\n 有 n 替换 m，
输入 d t 删除 t，
输入 s 排序。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
vector<int> data;
vector<int>::iterator i;
string t;
cout<<"请输入一串整数，以#结尾：";
cin>>t;
while(t!="#"){
int r=0,j=0;
while(t[j]!='\0'){
r=r*10+t[j]-'0';
j++;
}
data.push_back(r);
cin>>t;
}
// 操作
cout<<"请输入："<<endl;
while(cin>>t){
// 添加的情况
if(t[0]=='a'){
int num;
cin>>num;
// 在末尾添加数字
data.push_back(num);
}
// 修改的情况
else if(t[0]=='c'){
int j=2,num1=0,num2=0;
// 提取数字
while(t[j]!='\\'){
num1=num1*10+t[j++]-'0';
}
j++;
while(t[j]!='\0'){
num2=num2*10+t[j++]-'0';
}
// 替换
for(i=data.begin();i!=data.end();i++)
if(*i==num1){
data.erase(i);
data.insert(i,num2);
}
}
// 删除的情况
else if(t[0]=='d'){
int num;
cin>>num;
for(i=data.begin();i!=data.end();i++)
if(*i==num)
data.erase(i);
}
// 排序的情况
else if(t[0]=='s'){
sort(data.begin(),data.end());
}
else{
cout<<"输入不合法！"<<endl;
}
// 输出
for(i=data.begin();i!=data.end();i++)
cout<<*i<<" ";
cout<<"请输入："<<endl;
}
return 0;
}
2. 输入表达式，输出值。
即中缀表达式求值：先将中缀表达式转化为后缀表达式，然后再求值。
#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;
/**
* 输入中缀表达式，转化为计算机可以计算的后缀表达式，即逆波兰表达式。
* 定义运算符的优先级次序依次是+、-、*、/、(、)，权值越大，优先级越高
* 在栈顶时的优先级别
* int op_pri_s[6]={1,1,2,2,0,0};
* 在字符串中的优先级别
* int op_pri_q[6]={1,1,2,2,3,0};
*/
/**
* ()输入是英文的符号，记得调好输入法，我因为这个调了半个小时bug
*/
// 判定栈顶优先级权值的函数
int psta(string opt){
char op[6]={'+','-','*','/','(',')'};
int op_pri_s[6]={1,1,2,2,0,0};
for(int i=0;i<6;i++)
if(opt[0]==op[i])
return op_pri_s[i];
}
// 判定字符串中优先级权值的函数
int pstr(char opt){
char op[6]={'+','-','*','/','(',')'};
int op_pri_q[6]={1,1,2,2,3,0};
for(int i=0;i<6;i++)
if(opt==op[i])
return op_pri_q[i];
}
int main(){
stack<string> s;
queue<string> q;
string data;
cin>>data;
// 转后缀表达式
int i=0;
while(data[i]!='\0'){
string t="";
// 如果是运算符时
if(data[i]=='+'||data[i]=='-'||data[i]=='*'||data[i]=='/'||data[i]=='('||data[i]==')'){
// 栈空，直接压栈
if(s.empty()){
t+=data[i++];
s.push(t);
t="";
}
// 栈顶运算符优先级较高
else if(psta(s.top())>=pstr(data[i])){
// ***可能多次弹栈，直到字符串的运算符，优先级较高
while(psta(s.top())>=pstr(data[i])){
if((data[i]==')'&&s.top()=="("))
break;
q.push(s.top());
s.pop();
// 防止栈空，造成空指针异常
if(s.empty())
break;
}
// 括号匹配的情况，!s.empty()防止栈空，造成空指针异常
if(!s.empty()&&data[i]==')'&&s.top()=="("){
i++;
s.pop();
}
else{
t+=data[i++];
s.push(t);
t="";
}
}
// 字符串运算符优先级较高
else{
t+=data[i++];
s.push(t);
t="";
}
}
// 如果是数字
else
{
// 提取数字
while(data[i]!='+'&&data[i]!='-'&&data[i]!='*'&&data[i]!='/'&&data[i]!='('&&data[i]!=')'&&data[i]!='\0'){
t+=data[i++];
}
// 直接入队
q.push(t);
t="";
}
}
// 把栈弹空
while(!s.empty()){
q.push(s.top());
s.pop();
}
// 测试输出后缀表达式
/*while(!q.empty()){
cout<<q.front();
q.pop();
}
cout<<endl;*/
// 计算，还得用到栈。遇到数字压栈，遇到运算符弹出栈顶两个数字，进行计算。
double a=0,b=0;
stack<double> st;
while(!q.empty()){
string d=q.front();
q.pop();
if(d=="+"){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a+b);
}
else if(d=="-"){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a-b);
}
else if(d=="*"){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a*b);
}
else if(d=="/"){
b=st.top();
st.pop();
a=st.top();
st.pop();
st.push(a/b);
}
else{
double temp=0;
int k=0,
flag=0; // 小数部分的标志
// 提取数字
while(d[k]!='\0'){
if(d[k]=='.'){
k++;
flag=10;
continue;
}
if(flag){
temp=temp+(d[k++]-'0')/(flag/1.0);
flag*=10;
}
else{
temp=temp*10+d[k++]-'0';
}
}
st.push(temp);
}
}
cout<<st.top()<<endl;
return 0;
}
2011年机试真题
1. 输入一组单词（区分大小写），统计首字母相同的单词个数，相同的单词不累加，输出格式：“字母，个数”
#include <iostream>
#include <map>
#include <set>
using namespace std;
int main()
{
set<string> s;
map<char,int> m;
string str;
while(cin>>str)
{
s.insert(str);
}
set<string>::iterator it;
for(it=s.begin(); it!=s.end(); it++)
{
++m[(*it)[0]];
}
map<char,int>::iterator mit;
for(mit=m.begin(); mit!=m.end(); mit++)
{
cout<<mit->first<<" "<<mit->second<<endl;
}
return 0;
}
2. 输入一组单词（区分大小写），输出其字典排序
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
int n=0;
string a[105],s;
while(cin>>s)
{
if(s=="0")
break;
else
a[n++]=s;
}
sort(a,a+n);
for(int i=0;i<n;i++)
cout<<a[i]<<endl;
return 0;
}
3．给一个字符串（aaaa（bbbb（cccc，dddd），eeee（ffff）））该字符串表明的是各个人的层次关系。比如aaaa是bbbb和eeee的领导，bbbb是cccc和dddd的领导。先输入一个名称，比如ffff，要求输出其领导关系，输出aaaa>eeee>ffff。
#include <iostream>
#include <string>
using namespace std;
int main()
{
//(aaaa(bbbb(cccc,dddd),eeee(ffff)))
int n=0;
string s,str[105],t;//str为字符串栈
cin>>s>>t;
for(int i=0; i<s.length(); i++)
{
if(s[i]=='(')
{
str[n++]=s[i];
}
else if(s[i]==',')//遇到逗号时将逗号和前一个左括号之间的内容删除
{
for(int k=n-1; k>=0; k--)
{
if(str[k]!="(")
n--;
else if(str[k]=="(")
{
break;
}
}
}
else if(s[i]==')')//遇到右括号将右括号和前一个左括号之间的内容和左括号删除
{
for(int k=n-1; k>=0; k--)
{
if(str[k]!="(")
n--;
else if(str[k]=="(")
{
n--;
break;
}
}
}
else//字母或数字
{
int j;
string tt="";
for(j=i; j<s.length(); j++)
{
if((s[j]>='a'&&s[j]<='z')||(s[j]>='A'&&s[j]<='Z'))
tt+=s[j];
else
{
str[n++]=tt;
break;
}
}
if(tt==t)//找到目标字符串则退出循环
break;
i=j-1;
}
}
for(int i=0; i<n; i++)
{
if(str[i]!="(")
{
if(str[i]!=t)
cout<<str[i]<<">";
else
cout<<str[i];
}
}
cout<<endl;
return 0;
}
