蓝桥杯之小型计算器-分治法思想+简单逻辑判断(c++实现)

上文链接:蓝桥杯之合根植物-并查集及父子节点规律求解简化(c++实现)


资源限制

时间限制:1.0s 内存限制:256.0MB

问题描述

  模拟程序型计算器,依次输入指令,可能包含的指令有

  1. 数字:'NUM X',X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
  2. 运算指令:'ADD','SUB','MUL','DIV','MOD',分别表示加减乘,除法取商,除法取余
  3. 进制转换指令:'CHANGE K',将当前进制转换为K进制(2≤K≤36)
  4. 输出指令:'EQUAL',以当前进制输出结果
  5. 重置指令:'CLEAR',清除当前数字

  指令按照以下规则给出:
  数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
  运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
  重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
  进制转换指令可能出现在任何地方

  运算过程中中间变量均为非负整数,且小于2^63。
  以大写的'A'~'Z'表示10~35

输入格式

  第1行:1个n,表示指令数量
  第2..n+1行:每行给出一条指令。指令序列一定以'CLEAR'作为开始,并且满足指令规则

输出格式

  依次给出每一次'EQUAL'得到的结果

样例输入

7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL

样例输出

2040

该算法之我的思路

    1. 我进行了以下过程的简化:

      • 1.将指令进行分类,建立对应的函数。也就是功能模块化
      • 2.将对应某进制计算的过程都转换为十进制的过程,最后输出结果时再讲十进制结果数,转换为对应结果数。为此我抽象了一个函数:str_to_int.
      • 3 将一组指令进行拆分数组,比如NUM 100000,拆分为NUM,和数字100000存放到一个数组中。函数为split
    1. .提示: 数据进行计算过程中,由于进制一直在变化,所以对应的进制数都要先转为十进制数,在计算。

    主要代码展示

    int main()
    {
        int n,i,temp,flag=-1; //n为指令数,i为当前指令索引,temp为对应指令,flag为上一指令标记 
        string ins[1000];//指令集  
        string ins_ad[]={"NUM","ADD","SUB","MUL","DIV","MOD","CHANGE","EQUAL","CLEAR"};
        cin>>n;
        //输入指令
        for(i=0;i<n;i++)
        {
            getline(cin,ins[i]);
        } 
        //处理相关指令
        i=0;
        while(n>i)
        {
            split(ins[i]);
            //匹配对应指令
            for(int j = 0;j<sizeof(ins_ad)/sizeof(ins_ad[0]);j++)if(splits[0]==ins_ad[j]) temp = j;
            switch(temp)
            {
                case 0:// NUM值进行计算。首先判断NUM前最近指令flag,然后进行对应操作
                if(flag==-1){result = str_to_int(splits[1]);}
                if(flag==1){add(splits[1]);flag=-1;}
                if(flag==2){sub(splits[1]);flag=-1;}
                if(flag==3){mul(splits[1]);flag=-1;}
                if(flag==4){div(splits[1]);flag=-1;}
                if(flag==5){mod(splits[1]);flag=-1;}
                if(flag==8){result = str_to_int(splits[1]);flag=-1;}
                break;
                case 1:flag=1;break;
                case 2:flag=2;break;
                case 3:flag=3;break;
                case 4:flag=4;break;
                case 5:flag=5;break;
                case 6:change(splits[1]);break;
                case 7:equal();break;
                case 8:flag=8;clear();break;
            }
            i++;
        } 

    算法展示

    #include <iostream>
    #include <string>
    #include <sstream>
    #include <cmath>
    #include <stdlib.h>
    using namespace std;
    long long result=0;//存储结果值
    string splits[2];//存储拆分的指令集
    int k = 10;//当前进制数
    //拆分指令集 
    void split(string result)
    {    
        int split = result.find(" ");
        if(split==-1)
        {
            splits[0] = result;
        }
        else
        {
            splits[0]=result.substr(0,split);    
            splits[1]=result.substr((split+1),result.size());
        }
    }
    //将某进制数转换为十进制数 
    long long str_to_int(string result)
    {
        long long ret = 0;
        int flag=0;
        if(k==10) 
        {
            stringstream sm;
            sm<<result;
            sm>>ret;
            return ret;
        }
        for(int i = 0;i<result.size();i++) 
        {
            if(result[i]-'0'>=0&&result[i]-'0'<=9)
            {
                ret += (result[i]-'0')*(long long)pow(k,result.size()-i-1);
                flag++;    
            }else ret += (result[i]-'A'+10)*(long long)pow(k,result.size()-i-1);
        }
        
        return ret;
    }
    //加减乘商余计算 
    void add(string beadd){result+=str_to_int(beadd); }
    void sub(string besub){result-=str_to_int(besub); } 
    void mul(string bemul){result*=str_to_int(bemul); }
    void div(string bediv){result/=str_to_int(bediv); }
    void mod(string bemod){result%=str_to_int(bemod); }
    //进制转换 
    void change(string K)
    {
        stringstream sm; 
        sm<<K;
        sm>>k; 
    }
    //打印输出 
    void equal()
    {
        string s;
        //将十进制数result转换对应的k进制数
        while(result)
        {
            s+=(char)(result%k>=0&&result%k<=9)?result%k+'0':result%k-10+'A';
            result/=k;
        } 
        //因为十进制的高位对应为k进制的低位,所以倒序输出
        for(int i = s.size()-1;i>=0;i--)
        {
            cout<<s[i];
        }
        cout<<endl; 
    }
    //清除结果 
    void clear(){result = 0;}
    
    
    int main()
    {
        int n,i,temp,flag=-1; //n为指令数,i为当前指令索引,temp为对应指令,flag为上一指令标记 
        string ins[1000];//指令集  
        string ins_ad[]={"NUM","ADD","SUB","MUL","DIV","MOD","CHANGE","EQUAL","CLEAR"};
        cin>>n;
        //输入指令
        for(i=0;i<n;i++)
        {
            getline(cin,ins[i]);
        } 
        //处理相关指令
        i=0;
        while(n>i)
        {
            split(ins[i]);
            //匹配对应指令
            for(int j = 0;j<sizeof(ins_ad)/sizeof(ins_ad[0]);j++)if(splits[0]==ins_ad[j]) temp = j;
            switch(temp)
            {
                case 0:// NUM值进行计算。首先判断NUM前最近指令flag,然后进行对应操作
                if(flag==-1){result = str_to_int(splits[1]);}
                if(flag==1){add(splits[1]);flag=-1;}
                if(flag==2){sub(splits[1]);flag=-1;}
                if(flag==3){mul(splits[1]);flag=-1;}
                if(flag==4){div(splits[1]);flag=-1;}
                if(flag==5){mod(splits[1]);flag=-1;}
                if(flag==8){result = str_to_int(splits[1]);flag=-1;}
                break;
                case 1:flag=1;break;
                case 2:flag=2;break;
                case 3:flag=3;break;
                case 4:flag=4;break;
                case 5:flag=5;break;
                case 6:change(splits[1]);break;
                case 7:equal();break;
                case 8:flag=8;clear();break;
            }
            i++;
        } 
        return 0;
    }
    

    下文链接:蓝桥杯之分考场-深度优先遍历(DFS)+简单逻辑判断简化版(c++实现)

    评论

    暂无评论