USTC机试_07下

2021-01-12

1.输入字符串，倒序输出，例如：输入 I come from China.输出 China from come I.（单词不需倒序，只是句子倒了）

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
    string s;
    getline(cin,s);
    vector<string> v;
    while(s.find(' ')!=string::npos){
        int pos=s.find(' ');
        v.push_back(s.substr(0,pos));
        s=s.substr(pos+1);
    }
    v.push_back(s);
    for(int i=v.size()-1;i>=0;i--){
        cout<<v[i]<<" ";
    }
}

2.输入一个数判断是不是完数，是输出 yes，不是输出 no

#include<iostream>

using namespace std;

int fenjie(int x){
    int sum=0;
    for(int i=1;i<=x/2;i++){
        if(x%i==0) sum+=i;
    }
    return sum;
}

int main(){
    int x;
    cin>>x;
    if(fenjie(x)==x) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
}

3.件读取一个文件，做无向图的广度遍历输出，文件的第一行是图的节点个
数，后面是边的信息，0 0表示结束

#include<iostream>
#include<queue>
#include<vector>
#include<cstdlib>
#include<fstream>
#include<string>
using namespace std;

const int MAXN=100;
int visit[MAXN];
vector<int> G[MAXN];


void BFS(int x){//传过来的起始点
    queue<int> q;
    q.push(x);
    visit[x]=true;
    while(!q.empty()){//队列
        int current=q.front();
        cout<<current<<" ";
        q.pop();
        for(int i=0;i<G[current].size();i++){
            if(!visit[G[current][i]]){
                //cout<<"没访问"<<G[current][i]<<" ";
                q.push(G[current][i]);
                visit[G[current][i]]=true;
            }
        }
        //cout<<endl;
    }

}

int main(){
    //memset(visit,false,sizeof(visit));//在cstring中
    ifstream infile("in.txt");//在fstream中
    string line;//std::string类似通常的字符数组
    string n;
    getline(infile,n);
    while(getline(infile,line)){
        int pos=line.find(" ");
        //atoi中要将string转化为char*
        int a=atoi((char*)line.substr(0,pos).data());
        int b=atoi((char*)line.substr(pos+1).data());
        //cout<<a<<" "<<b<<endl;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    BFS(1);
}

4.没有括号只有加减乘除的表达式求值，表达式从文件读入，计算的结果
输出到文件上。

#include<iostream>
#include<fstream>
#include<stack>
#include<cstring>
using namespace std;
const int MAXN=100;
char out[MAXN];//存储逆波兰式
stack<char> s1;//生成逆波兰式
stack<double> s2;//计算逆波兰式
int Priority(char c){
    if(c=='*'||c=='/') return 2;
    else if(c=='+'||c=='-')return 1;
    else if(c=='#') return 3;
    else return 0;
}

bool isop(char c){
    return c=='+'||c=='-'||c=='*'||c=='/';
}

double cal(double x,double y,char op){
    if(op=='+')return x+y;
    else if(op=='-') return x-y;
    else if(op=='*') return x*y;
    else if(op=='/') return x/y;
}

void RePolish(string s){
    int j=0;//指向out
    for(int i=0;i<s.size();i++){
        //if(!s1.empty()) cout<<"栈顶："<<s1.top();
        if(isdigit(s[i])){
            //cout<<"数字:"<<s[i];
            out[j++]=s[i];
        }
        else if(isop(s[i])){
            //cout<<"操作符:"<<s[i];
            if(s1.empty()) s1.push(s[i]);
            else if(Priority(s[i])>Priority(s1.top())){
                s1.push(s[i]);
            }
            else{
                while(!s1.empty()&&Priority(s[i])<=Priority(s1.top())){//这里是<=，先进的优先级更高
                    out[j++]=s1.top();
                    //cout<<"此时栈顶"<<s1.top();
                    s1.pop();
                }
                s1.push(s[i]);
            }
        }
    }
    while(!s1.empty()){
        out[j++]=s1.top();
        s1.pop();
    }
    return ;
}

void Calculate(){//根据逆波兰式求值
    for(int i=0;i<strlen(out);i++){
        if(isdigit(out[i])) s2.push((double)out[i]-'0');
        else if(isop(out[i])){
            double b=(double)s2.top(); s2.pop();
            double a=(double)s2.top(); s2.pop();
            s2.push(cal(a,b,out[i]));
        }
    }
    cout<<s2.top();
}

int main(){
    ifstream infile("in.txt");
    string s;
    getline(infile,s);
    RePolish(s);
    for(int i=0;i<strlen(out);i++){//char*要用strlen而不是.size
        cout<<out[i];
    }
    cout<<endl;
    Calculate();
}