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

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

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

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

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

#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编辑过]

好,如果我版主的话当然会加精,真的很用心哇~

话说第二个和第一个方法类似吧,那个?要填的话我也需要相当长时间来理解代码~
至于第三个马走日了解过一下,是一幅图走哈密顿回路,可以用回溯算法~

按照7楼修改后代码能正常运行~

printf("(3))3=%d..................测试括号匹配以及表达式问题\n",eval("(3))3"));
printf("-+3+3=%d..................测试正负混搭问题\n",eval("-+3+3"));
printf("3+-+-3=%d..................测试正负混搭问题\n",eval("3+-+-3"));
这就见笑了~

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

第一个空是++i;
第二个空是i+=*s+1;

我需要花些时间看完程序才能给出合理的意见,其实认真点的这代码虽然精巧,但逻辑有点散,不好维护先不说,有数组最好要进行越界判断(当然这个除非有真的特意这样做,但还是有一定必要的)~例如如果要添加平方或者取余运算符这些比较麻烦,还有如果进行加个平方运算(这样原来数值就可能会比原来要长而覆盖其它数字了)~
所以有种感觉这代码可能就是不再更新的终端代码了

再说一句网上代码或者比较复杂但其经典不是没有道理的,因为从可读性和可维护性可移植性以及效率问题的角度来说还是有很多值得借鉴的地方,所以这代码重点就在于运用了递归思想,至于其它细节地方给我有点生硬的感觉(当然这是一个风格方面的小问题而已),但就是比较容易读懂或者更适合刚刚接触这方面的大众,还是笑了思想可以借鉴,但是实现细节方面还是综合参考来看比较好~

当然上面只是我个人意见,如果楼主认为自己做可以那就没问题了(哇,或者我看得太认真了,评价也这么认真,如果有什么说得不到位的地方请勿见怪哈)~

https://bbs.bccn.net/viewthread.php?tid=475893&highlight=%2Brenkejun1942

顺便帮renkejun1942那个中缀计算器顶一下,可以综合起来看看~

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

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

二楼的算法的确好看简洁很多,关键是可以很容易找到或者提现算法本身的实现原理,这个我有时间再认真看看,相对于1楼的算法而言这个算法每个细节处理都恰到了好处,当然看懂还是需要一定的时间的,值得借鉴

PS:那个if (i)i++;这样把i的初值设置成-1就可以了,我就说为啥我写i+=*s+1;这么难以理解但又无语地正确的代码呢~
因为这样可以每次少一个if判断,算是一个微优化吧~

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

用栈实现,基本思想就是要用两个栈,一个符号栈,一个数字栈,两个符号的优先级比较,如果前者小于的进栈,大于或者等于的出栈,本来之前还说了别的,不过我认真看后还是觉得自己说法有些欠缺编辑掉了~~

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