论坛里多是求代码、布作业的，大多数都不愿意通过看代码学习，所以我将最近练习的几个小代码不完整的分享下，所谓不完整，就是有几个地方需要填写几句简单代码，程序才能正常运行，希望籍此发动各位写代码的兴趣。

一、递归方法完成带括号嵌套的整数四则混合运算
四则混合运算网上多是用栈方法完成的，还有什么用正则、用队列、用链表等等，看着头大。所以我自己琢磨了一个通过递归合并算式的方法完成。里面比较巧妙地通过在同一个字符串中分解为子串、递归将运算结果替代子串，最终得到运算结果，代码如下（代码中“//?”的行是需要补充的部分，一般都是简单的语句，填写对了，程序即可正常执行）

/********************************

 *可以括号嵌套的整数四则混合运算*

 ********************************/

#include <stdio.h>
int getnum(char *p,int *s)
{//获取一个操作数
    int i=*s,j=1,k;
    if(p[i]=='-')
    {//处理负数
        i++;
        j=-1;
    }
    for(k=0;p[i]&&p[i]!='#'&&p[i]>='0'&&p[i]<='9';i++)k=k*10+p[i]-'0';  //数据字符串转换为整数
    *s=i;
    return k*j;
}
int oper(char *p,char *op,int *s,int *e)
{
    int i=0,j,num1=0,num2=0;
    *s=*e=-1;
    char c='+';
    do
    {
        if(i)i++;
        *s=i;                                 //返回该算式在字符串中起始位置
        num1=getnum(p,&i);
        //? 这条语句稍微复杂点        ;      //比较运算符
    }while(i&&p[i]&&p[i]!='#'&&p[i]!=op[j]);           //获取第一个操作数
    if(p[i]&&p[i]!='#')
    {
        c=p[i];                               //获取运算符
        j=i+1;
        num2=getnum(p,&j);                    //获取第二个运算符
        *e=j-1;                               //返回该算式在字符串中结束位置
    }
    if(c=='+')num1+=num2;
    if(c=='-')num1-=num2;
    if(c=='*')num1*=num2;
    if(c=='/')
    {
        num2=num2?num2:1;                     //防止除0错误
        num1/=num2;
    }
    if(c=='%')
    {
        num2=num2?num2:1;                     //防止除0错误
        num1%=num2;
    }
    if(c=='^')
    {
        for(j=1;num2;num2--)j*=num1;          //幂运算
        num1=j;
    }
    return num1;                              //根据运算符对两个操作数做对应运算并返回运算结果
}

int eval1(char *p)
{
    int i,j,k,s,e;
    char b[3][10]={"^","*/%","+-"};
    for(i=j=0;p[i];i++)if(p[i]!=' ')p[j++]=p[i];;         //消算式中空格
    p[j]=0;
    for(s=e=k=0;p[e]&&p[e]!='#'&&p[e]!=')';e++)if(p[e]=='(')s=e;;  //左右扫描找到的第一个反括号一定是最内层的括号运算，同时s中是该反括号对应的正括号位置
    if(p[e]&&p[e]!='#')
    {//有括号优先处理括号中的算式运算
        p[s]=' ';
        p[e]='#';                                         //消除括号，把括号中算式当子串进行运算
        k=eval1(p+s);                                     //计算括号中的算式，结果在k中
        for(e=s;p[e]!='#';e++);
    }
    else
    {//否则是不含括号的纯算式
        for(i=0;i<3;i++)
        {
            k=oper(p,b[i],&s,&e);
            if(e>s)break;
        }
        //?             ;  //如果非算式（纯数字）则返回运算结果
    }
    //计算结果回填到算式中替换原算式。结果在k中，回填位置为s、e之间
    for(i=0;p[i];i++);
    for(;i>=e;i--)p[i+20]=p[i];
    e+=20;                                   //空出20个位置，插入运算结果，方便幂运算
    p[s]=' ';
    if(k<0)
    {
        p[s]='-';
        k=-k;                                //回填负数的处理，需要将该数转换为正整数填充
    }        
    for(i=e;i>s;i--)p[i]=' ';                //首先将s-e之间填充空格
    for(i=e;k&&i>s;k/=10)p[i--]=k%10+'0';    //其次将计算结果转换为数字字符填充
    if(p[e]==' ')p[e]='0';                   //如果全部空格，至少填充一个字符0
    return eval1(p);                         //回填后的算式递归
}

int eval(char *p)
{//这个过渡函数的主要作用是复制字符串，防止出现调用者因实参为字符串常量不能修改的Bug
    int i,j;
    char a[500];
    for(i=j=0;p[i];i++)
        if((p[i]>39&&p[i]<58&&p[i]!=44)||p[i]=='%'||p[i]=='^')a[j++]=p[i];  //拷贝并过滤非法字符（小数点未过滤）
    a[j]=0;
    return eval1(a);
}
void main()
{
    printf("5-15*((6+3)/(-3)-3*2)/5=%d...测试括号嵌套\n",eval("5-15*((6+3)/(-3)-3*2)/5"));
    printf("-3*5+(3+2)*12=%d.............测试合法算式开头负号\n",eval("-3*5+(3+2)*12"));
    printf("-3+-*/15=%d..................测试运算符乱叠\n",eval("-3+-*/15"));
    printf("-3/a-b+15=%d.................测试非法字符\n",eval("-3/a-b+15"));
    printf("-3--123=%d..................测试负负得正\n",eval("-3--123"));
    printf("3^12-10 Mod 6*5=%d.......测试幂运算、模运算\n",eval("3^12-10%6*5"));
    printf("6*6 mod 4=%d  实际值=%d........测试模运算\n",eval("6*6%4"),6*6%4);
    printf("不是算式也可以有结果，懒得做算式合法检测函数了=%d\n",eval("不是算式也可以有结果，懒得做算式合法检测了"));
}

程序运行结果：

[此贴子已经被作者于2018-4-5 21:31编辑过]

收到的鲜花

• lin5161678 于 2018-05-14 09:48 送鲜花  1朵  

二、用栈完成括号嵌套四则混合运算
严格说，这个代码不是我的，是我同学为考研做的练习题。他可是专业软件工程的，读了四年居然做这么简单的题目都困难，代码交给我时仅只要求做个位数的加减乘除，还根本不能运行。我大概用了半个小时帮他调试完成，并能做int范围内的混合运算。通过调试，我感觉这个算法有很多优点，如逻辑简明、容易扩展其他混合运算、无我一楼子串长度限制，很容易扩展到实数范围的运算（我一楼代码受限于字符串长度，只能在整数范围内运算，如果计算小数，很有可能因数据长度超过算式长度而得不到正确结果）。
这个代码的算法核心应该是根据运算符优先级决定数据是否出入栈参与运算，虽然没有用push、pop通用的栈函数，但基本思想还是用到了栈。本代码没有做覆盖性检测，可能还存在bug。

#include <stdio.h>
int oper(int x,int y,char z)
{
    switch(z)
    {
    case '+':return x+y;
    case '-':return x-y;
    case '*':return x*y;
    case '/':return x/y;
    }
    return y;     //不存在的操作符返回当前操作数y
}

int instack(char c)     //返回栈内的优先级
{
    switch(c)
    {
    case '*': return 2;
    case '/': return 2;
    case '+': return 1;
    case '-': return 1;
    case '(': return 0;
    case ')': return -1;
    }
    return 1;    //不存在的操作符等同于+
}
int outstack(char c)     //返回栈内的优先级
{
    switch(c)
    {
    case '*': return 2;
    case '/': return 2;
    case '+': return 1;
    case '-': return 1;
    case '(': return 4;
    case ')': return -1;
    }
    return -2;   //未包含的操作符肯定是最小的，将会触发栈内自动运算
}

void main()
{
    char str[100]="5-15*((6+3)/(-3)-3*2)/5";   
    char s2[20];
    int top1,top2,k,num,s1[20],flg;    //num为当前操作数
    //    gets(str);
    s2[0]='+';
    s1[0]=0;      //在栈底部压入默认数据和操作
    top1=top2=k=0;
    do
    {
        for(num=0;str[k]&&str[k]>='0'&&str[k]<='9';k++)num=num*10+str[k]-'0';  //取操作数
        //此时str[k]停在当前操作符或字符串结束符上，num是当前操作数
        while(top1>=0&&top2>=0&&outstack(str[k])<=instack(s2[top2]))
        {
            if(s2[top2]!='(')num=oper(s1[top1--],num,s2[top2--]);  //正括号不参与计算
            if(str[k]==')'&&s2[top2]=='(')
            {//如果正反括号相遇，则正括号出栈，k++移到下一个
                //?
                k++;
            }
        }
        if(str[k]!='(')s1[++top1]=num;      //如果是正括号当前数不入栈，因为正括号前一定是一个操作符，已经将当前数入栈了
        if(str[k]!=')')s2[++top2]=str[k];   //如果当前操作符是反括号不入栈
    }while(str[k++]);
    printf("%s=%d\n",str,s1[0]);
}

[此贴子已经被作者于2018-4-3 22:19编辑过]

三、马走日（合理剪枝的马满格）
马走日也是经典算法里的题目，在书里通常叫“马踏棋盘”，一般都是用递归完成的，也有老师专门要求用循环完成。这也是我那学软件工程的高中同学提交给我的，他的代码如下：

#include <stdio.h>
int step=0;                                     //8*8的棋盘1~64标注马的路径
void print(int a[][8])
{
    int i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            printf("%-3d",a[i][j]);
        }
        printf("\n");
    }
}
void fun(int a[][8],int i,int j)
{
    if(i<0||j<0||i>7||j>7)return;       //出界，返回
    if(a[i][j]>0)return;                //此步已走
    step++;                             //此步可走，步数加1
    a[i][j]=step;
    if(step==64)
    {
        print(a);
        return;
    }               //若此步是第64步，则走满，并返回
    fun(a,i-2,j+1);
    fun(a,i-1,j+2);
    fun(a,i+1,j+2);
    fun(a,i+2,j+1);
    fun(a,i+2,j-1);
    fun(a,i+1,j-2);
    fun(a,i-1,j-2);
    fun(a,i-2,j-1);
    if(step==64)return;
    //print(a);         //调试用
    a[i][j]=0;
    step--;
    if(step==0)printf("不能走满全格");
}
void main()
{
    int a[8][8]={0};
    int m,n;
    printf("输入起点:");
    scanf("%d %d",&m,&n);
    fun(a,m,n);
}

初看，这个代码没有什么问题，可是调试运行后发现，只有在起点坐标为0，0时有输出，其他坐标进入死循环了，输入坐标0，0时输出如下：

看这结果，的确踏满棋盘了，说明算法没问题。那其他坐标为什么进入死循环了呢？坐标0，0 是否可以模拟进入死循环状态？通过分析，是可以的，只要将马走日的顺序调整下，如把语句“fun(a,i-2,j+1);”下移一行，坐标0，0也进入死循环了，没有输出。实际上，这个递归最大的时间复杂度为O(n^64)，因此，不是死循环，而是需要等好长时间才有输出的，比如坐标7，7时，大概10几秒能出结果，而大部分坐标等上一个小时都不一定有结果。通过分析马走途无路时周边数据情况（开通print(a);语句调试执行）我找到一种剪枝方法，可以非常快速地获得所有坐标下踏满棋盘的结果，代码如下（同样地设了两个空，有兴趣的可以开动脑筋填上以保证程序正常执行）：

#include <stdio.h>
#define bd 8
void print(int a[][bd])
{//输出棋盘数据
    int i,j;
    for(i=0;i<bd;i++,printf("\n"))
        for(j=0;j<bd;j++)printf("%3d",a[i][j]);
}
int fun(int a[][bd],int x,int y,int s)
{//a:棋盘，x、y：坐标，s:步数
    int i,j,n,b[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};  //走马顺序
    if(x<0||x>bd-1||y<0||y>bd-1)return 0;
    if(a[x][y])return a[x][y]*100;        //返回该坐标周围符合马走日规则的数据，用于走途无路时剪枝参照
    a[x][y]=s;
    if(s==bd*bd)return s;
    for(i=j=0;i<8;i++)
    {
        n=fun(a,x+b[i][0],y+b[i][1],s+1);
        if(n==bd*bd)return n;
        if(n>100&&n/100<s-1&&n>j)j=n;     //确定剪枝数据     
        if(n&&n<s)                        
        {
            //?;
            return n;                     //剪枝
        }
    }
    a[x][y]=0;
    //?;                         //返回剪枝数据
}
void main()
{
    int a[bd][bd]={0};
    fun(a,1,2,1);
    print(a);
}

输出数据：

[此贴子已经被作者于2018-4-6 22:43编辑过]

很显然，你非常有IT精英的潜质！
根据你说的情况，我逐一回答：
1，关于修改部分，第一个“++i”正确，第二个“i+=*s+1”则不是标准答案，正确答案是“if(i)i++;”主要作用是只要不在字符串开头（位置0），跳到下一个位置取第二个数，位置0不能跳，否则要不取不到负号、要不少取一位数。但巧的很，你这样修改结果是正确的，巧就巧在“*s=*e=-1;”，我为了识别是否存在运算，将算式的起始和结束位置初始化为-1了，所以当从头扫描时，很巧地吻合了算法，如果我初始化为其他值，你这个语句就得不到正确结果了。
2，至于逻辑有点散、可维护性差等，这是仁者见仁、智者见智的事。我尽量在我理解的范围内组织算法逻辑，尽可能地按结构化要求组织函数功能，尽可能地详尽注释。我也百度了下“代码可读性、可维护性规范”词条，自认为基本符合。你能在短时间内读懂我的这个代码、填充正确语句、提出中肯意见，除了你自身基础好外，也正是我按规范组织代码的结果。
3，我在测试里已经说明了“没有做算式合法性检测”，你输入正确算式就能得到正确结果，算式不规范可能不一定结果正确，我只能保证不死循环，有结果输出。
4，我也百度了下“四则混合运算”词条，就是带括号的加减乘除而已，幂运算和模运算不属于此列。如果非要扩充，我的这个代码也是很容易扩充的，一楼代码已更正，扩充了幂运算和模运算功能。幂运算只能进行10以内5次方以下的运算，否则受限于算式长度而得不到正确结果。
5，我已经认识到这个算法的局限，当初是想算24点时想到这个算法的，二楼算法比较合理。
6，非常感谢你认真读我的代码，这个认真劲头值得我们学习。

仍然分开回答
1，答主填空“ if (e!=-1)break;”虽然可以正常执行，但不建议这样，标准答案是“if(e>s)break;”。因为值-1是函数内部定义的值，对于函数内部应该适用于黑盒测试法，对于应用函数的人只要知道接口参数和返回值，而对于内部可以不知情，因此应用了函数内部定义的值不合规范。对于这个函数，我们知道参数s和e分别对应与算术表达式的起点和下一个运算符位置，因此，如果该表达式如果参与运算了，下一个运算符位置一定大于起始值，反之如果不是表达式，只单纯是一个数字，则只有起始值，没有下一个运算符位置。
2，关于模运算优先级问题，我事先也百度了，也知道和乘除同级，只是要修改的较多，偷了个懒，就让模运算和幂运算同级了。现已修改，一样设置了两处填空。我设置填空主要目的是防止要作业的拷贝粘贴就轻松交作业，要作业也应该动脑子的，光拷贝粘贴是没有进步的。
3，关于幂运算受限算式长度问题，已经解决（参看一楼关于幂运算结果），现在这个代码已经很容易扩展为小数运算了，最长可容纳long long（有效位20位）的数据计算结果。
4，你在13楼提到的非法字符过滤问题，这个功能在eval中解决，eval1过滤空格，是因为空格参与了算法，递归中有用途，其他非法字符可一次性过滤。

谢谢答主参与讨论！

[此贴子已经被作者于2018-4-5 21:35编辑过]

厉害！
你填空了也不要紧，不走心的人根本看不懂这些讨论。
一楼代码已解决幂运算结果超长的问题，直接做到long long的有效位了，稍加修改可做double的四则混合运算，欢迎测试指正。

厉害！这种剪枝算法我也是在那种类死机状态下单步调试分析得来的，试了几种坐标，速度很快就得到结果，没有做广谱测试，有不足地方容后改进。
这种马走日好像还有一种更简便算法：得到在一个坐标下走满的数据，就可以此数据通过运算得到全部坐标下走满的数据，不需要每输入一次起始坐标都递归一次的。
最近忙毕业，上论坛少了，祝各位编程快乐！

[此贴子已经被作者于2018-5-19 07:49编辑过]