博客

原理：递归

这题让我深刻理解了递归：

1.将原问题拆分成更小的问题，这几个小问题的解决方案一致从而降低整个问题分析的难度。

2.递归并不一定只有一个函数，当放入一个函数递归特别复杂或操作可能相互冲突时可放入另一函数中。

此题如何将表达式拆成更小是关键，若以从左至右则会在各种运算的地方产生矛盾，难以攻克。这也侧面说明，算法如果太难，就一定要换一条思路。

括号内是一个表达式，这显而易见，可只抓住它还不够。还要对“普通表达式”（不含括号的）进行计算，而计算过程中“&”和“|”的排序至使计算不能简单的“从左往右”，所以还要对其进行分段处理。至于为什么不选“&”来处理因为由计算时的常理来进行分段更有效；

由此可大胆推测有几个划分表达式的步骤就以几个函数来处理要更为简便，即有几个关键点，就有几个函数互相递归实现。此外“&”在“成功条件”下判断失败时涉及到的数据更少，而“|”判断失败涉及到两者，若下次在“失败条件”下判断成功不知道会不会有反着的规律，反正将涉及多的“复杂的”先特殊处理后的算法应该会更简单。

算法是给予计算机人的智慧逻辑，所以首先要人的进步，练习算法亦是锻炼我们自己。

#include <iostream>
#include<string.h>
using namespace std;

void Spacebar (char a[]);//去掉空格，便于处理；

int Expression(char a[] , int start);//依照人的思维模式先将“|”分成几个表达式去处理

int Answar (char a[]);//处理没有 “|” 后的表达式；

char* Cut (char a[] , int start , int finish);//剪切a[]中下标为start到finish的片段

int main(){
    char a[20001];
    int num = 1;
    while(gets(a) != NULL){

        Spacebar(a);
//        puts(a);
        if(Expression(a , 0) ){
            printf("Expression %d: V\n" , num);
        }else{
            printf("Expression %d: F\n" , num);
        }
        num++;
    }
    return 0;
}

void Spacebar (char a[]){
    int num = 0;
    char temp = ' ';
    for(int i = 0;a[i] != '\0';i++){
        if(a[i] == temp){
            num++;
            int j = i+1;
            for( ;a[j] != ' ' && a[j-1] !='\0';j++){
                a[j-num] = a[j];
            }
            i = j-1;
        }
    }
}


int Expression(char a[] , int start){
    int len = strlen(a);
    char* b;
    int flag = 0 , begin = start,end = 0 ,num = 0;
    for( ;a[start] != '\0';start++){
        if(a[start] == '('){
            num++;
        }
        if(a[start] == ')'){
            num--;
        }
        if(a[start] == '|' && num==0){
            end = start;
            b = Cut(a,begin,end-1);
            break;
        }
    }


    if(start != len){
        if(Answar(b) || Expression(a , start+1)){
            flag = 1;
        }
    }else{
        b = Cut(a,begin,len-1);
        if(Answar(b)){
            flag = 1;
        }

    }

    return flag;
}

char* Cut (char a[] , int start , int finish){
    int len = finish-start+1+1;
    char* temp = (char*)malloc( sizeof(char)*len );
    for(int i = 0;i < len;i++){
        temp[i] = a[i+start];
    }
    temp[len-1] = '\0';

    return temp;
}

int Answar (char a[]){
    int flag = 1;

    for(int i = 0;a[i] != '\0'; ){
        int j = i +1;
        if(a[i] == '!' || a[i] == '&'){
            //无需操作，直接到下步
        }else if(a[i] == 'V'){
            flag = 1;
        }else if(a[i] == 'F'){
            flag = 0;
        }else if(a[i] == '('){
            int num = 1;
            for(/*j = i*/; a[j] != '\0';j++){
                if(a[j] == ')' && --num == 0){
                    char* b = Cut(a , i+1 ,j-1);
                    flag = Expression(b , 0);
                    break;
                }else if(a[j] == '('){
                    num++;
                }
            }
            j++;
        }
        if(i != 0 && a[i-1] == '!'){
            flag = !flag;
        }
        i = j;
        if(flag == 0){return flag;}
    }

    return flag;

}