布爾表達式求值

問題來自1:Boolean Expressions

主要思路為遞歸解決。

將一個表達式視為這幾種情況：1.若干個小的表達式通過&或|等符號連接而成；2.由一個大括弧包括的大表達式;3.由！+（表達式）4.單個因子，如V或！F。

將整體表達式不斷遞歸成為小的表達式，最後算出每個子表達式的邏輯值，從而向上返回得出最後的結果。

下面上代碼

#include<iostream>using namespace std;const int MAX = 101;#include<string.h>void prodeal(char str[]);bool expression_value(char str[],int left,int right);bool factor_value(char str[]);bool term_value(char str[]);bool evalute_value(char ch);bool ifsingle(char str[],int left,int right);int main(){ char ch[MAX]; int i = 0; bool result[30]; while (cin.getline(ch,MAX)) { //key=0; //cin.getline(ch,MAX); //getchar(); prodeal(ch); // cout<<ch<<endl; int length=strlen(ch); //cout<<"here"; //cout<<"RESULT="<<expression_value(ch,0,length-1)<<endl; printf("Expression %d: ",i+1); if(expression_value(ch,0,length-1)){ printf("V"); } else{ printf("F"); } printf("
"); i++; } return 0;}void prodeal(char str[])//eliminate the space in the string { int length = strlen(str); int i = 0; char str_1[MAX]; int j = 0; for (i = 0; i < length; i++) { if (str[i] != ) { str_1[j++] = str[i]; //cout<<str[i]<< ; } } str_1[j]=; strcpy(str, str_1);}//the function is used to get the expression_value in str[] from the left to rightbool expression_value(char str[],int left,int right){ bool result=true; if((right-left+1)==1){ result=evalute_value(str[left]); return result; } else if((right-left+1)==2){ result=!(evalute_value(str[right])); return result; } else{ //consisent with the case 2 if(str[left]==(&&str[right]==)&&ifsingle(str,left,right)){ result=expression_value(str,left+1,right-1); } //consisent wiht the case 3 if(str[left]==!&&(str[left+1]==(||str[left+1]==!)&&str[right]==)&&ifsingle(str,left+1,right)){ if(str[left+1]==(){ result=!(expression_value(str,left+2,right-1)); } else { result=!(expression_value(str,left+1,right)); } } else{ int i=right; bool rear=true; int cnt=0; bool front=true;//注意i的初始位置在最右邊，否則在遞歸過程中，邏輯表達式的運算順序將會自右向左 while(i>=left){ if(str[i]==)){ cnt++; i--; continue; } if(str[i]==(){ cnt--; i--; continue; } if(str[i]==|&&cnt==0){ //result=expression_value(str,left,i-1)||(expression_value(str,i+1,right)); front=expression_value(str,left,i-1); rear=(expression_value(str,i+1,right)); result=front||rear; //調試用printf("i=%d,left=%d,right=%d front=%d,rear=%d
",i,left,right,front,rear); break; } else if(str[i]==&&&cnt==0){ result=expression_value(str,left,i-1)&&(expression_value(str,i+1,right)); front=expression_value(str,left,i-1); rear=(expression_value(str,i+1,right)); result=front&&rear; //調試用printf("i=%d,left=%d,right=%d front=%d,rear=%d
",i,left,right,front,rear); break; } i--; } } } return result;}bool evalute_value(char ch){ if(ch==V){ return true; } else{ return false; } }//add a stackbool ifsingle(char str[],int left,int right)//判斷該表達式是由括弧括起來的整個表達式還是多個表達式串聯而成 { bool isprime=true; int cnt=0; int i=left; bool have=false; while(i<=right){ if(str[i]==(){ cnt++; have=true; } else if(str[i]==)){ cnt--; } if(cnt==0&&i<right&&have){ isprime=false; return isprime; } i++; } return isprime;}

個人感覺自己的程序雖然AC但是還是比較混亂的，遞歸的層次分的比較少，因此需要進行很多的判斷語句來區分各種情況。將於下周推出改進版本。

推薦閱讀：