首先窮舉的可行性問題。我把表達式如下分成三類——
1、 無括號的簡單表達式。
2、 有壹個括號的簡單表達式。
3、 有兩個括號的較復4、 雜表達式。
窮舉的開始我對給出的四個數進行排列,其可能的種數為4*3*2*1=24。我利用壹個嵌套函數實現四個數的排列,算法如下:
/* ans[] 用來存放各種排列組合的數組 */
/* c[] 存放四張牌的數組 */
/* k[] c[]種四張牌的代號,其中k[I]=I+1。
用它來代替c[]做處理,考慮到c[]中有可能出現相同數的情況 */
/* kans[] 暫存生成的排列組合 */
/* j 嵌套循環的次數 */
int fans(c,k,ans,kans,j)
int j,k[],c[];char ans[],kans[];
{ int i,p,q,r,h,flag,s,t;
for(p=0,q=0;p<4;p++)
{ for(r=0,flag=0;r if(k[p]!=kans[r]) flag++;
if(flag==j) t[j][q++]=k[p];
}
for(s[j]=0;s[j]<4-j;s[j]++)
{ kans[j]=t[j][s[j]];
if(j==3) { for(h=0;h<4;h++)
ans[2*h]=c[kans[h]-1]; /* 調整生成的排列組合在最終的表
達式中的位置 */
for(h=0;h<3;h++)
symbol(ans,h); /* 在表達式中添加運算符號 */
}
else { j++;
fans(c,k,ans,kans,j);
j--;
}
}
} 正如上面函數中提到的,在完成四張牌的排列之後,在表達式中添加運算符號。由於只有四張牌,所以只要添加三個運算符號就可以了。由於每壹個運算符號可重復,所以計算出其可能的種數為4*4*4=64種。仍然利用嵌套函數實現添加運算符號的窮舉,算法如下:/* ans[],j同上。sy[]存放四個運算符號。h為表達式形式。*/
int sans(ans,sy,j,h)
char ans[],sy[];int j,h;
{ int i,p,k,m,n; char ktans[20];
for(k[j]=0;k[j]<4;k[j]++)
{ ans[2*j+1]=sy[k[j]]; /* 剛才的四個數分別存放在0、2、4、6位
這裏的三個運算符號分別存放在1、3、5位*/
if(j==2)
{ ans=sy[k[j]];
/* 此處根據不同的表達式形式再進行相應的處理 */
}
else { j++; sans(ans,sy,j--,h); }
}
} 好了,接下來我再考慮不同表達式的處理。剛才我已經將表達式分為三類,是因為添加三個括號對於四張牌來說肯定是重復的。對於第壹種,無括號自然不用另行處理;而第二種情況由以下代碼可以得出其可能性有六種,其中還有壹種是多余的。
for(m=0;m<=4;m+=2)
for(n=m+4;n<=8;n+=2)
這個for循環給出了添加壹個括號的可能性的種數,其中m、n分別為添加在表達式中的左右括號的位置。我所說的多余的是指m=0,n=8,也就是放在表達式的兩端。這真是多此壹舉,呵呵!最後壹種情況是添加兩個括號,我分析了壹下,發現只可能是這種形式才不會是重復的——(a b)(c d)。為什麽不會出現嵌套括號的情況呢?因為如果是嵌套括號,那麽外面的括號肯定是包含三個數字的(四個沒有必要),也就是說這個括號裏面包含了兩個運算符號,而這兩個運算符號是被另外壹個括號隔開的。那麽如果這兩個運算符號是同壹優先級的,則肯定可以通過壹些轉換去掉括號(妳不妨舉壹些例子來試試),也就是說這壹個括號沒有必要;如果這兩個運算符號不是同壹優先級,也必然是這種形式((a+-b)*/c)。而*和/在這幾個運算符號中優先級最高,自然就沒有必要在它的外面添加括號了。 綜上所述,所有可能的表達式的種數為24*64*(1+6+1)=12288種。哈哈,只有壹萬多種可能性(這其中還有重復),這對於電腦來說可是小case喲!所以,對於窮舉的可行性分析和實現也就完成了。
接下來的問題就是如何對有符號的簡單表達式進行處理。這是棧的壹個著名應用,那麽什麽是棧呢?棧的概念是從日常生活中貨物在貨棧種的存取過程抽象出來的,即最後存放入棧的貨物(堆在靠出口處)先被提取出去,符合“先進後出,後進先出”的原則。這種結構猶如子彈夾。
在棧中,元素的插入稱為壓入(push)或入棧,元素的刪除稱為彈出(pop)或退棧。 棧的基本運算有三種,其中包括入棧運算、退棧運算以及讀棧頂元素,這些請參考相關數據結構資料。根據這些基本運算就可以用數組模擬出棧來。 那麽作為棧的著名應用,表達式的計算可以有兩種方法。 第壹種方法——
首先建立兩個棧,操作數棧OVS和運算符棧OPS。其中,操作數棧用來記憶表達式中的操作數,其棧頂指針為topv,初始時為空,即topv=0;運算符棧用來記憶表達式中的運算符,其棧頂指針為topp,初始時,棧中只有壹個表達式結束符,即topp=1,且OPS(1)=‘;’。此處的‘;’即表達式結束符。
然後自左至右的掃描待處理的表達式,並假設當前掃描到的符號為W,根據不同的符號W做如下不同的處理:
1、 若W為操作數
2、 則將W壓入操作數棧OVS
3、 且繼續掃描下壹個字符
4、 若W為運算符
5、 則根據運算符的性質做相應的處理:
(1)、若運算符為左括號或者運算符的優先級大於運算符棧棧頂的運算符(即OPS(top)),則將運算符W壓入運算符棧OPS,並繼續掃描下壹個字符。
(2)、若運算符W為表達式結束符‘;’且運算符棧棧頂的運算符也為表達式結束符(即OPS(topp)=’;’),則處理過程結束,此時,操作數棧棧頂元素(即OVS(topv))即為表達式的值。
(3)、若運算符W為右括號且運算符棧棧頂的運算符為左括號(即OPS(topp)=’(‘),則將左括號從運算符棧談出,且繼續掃描下壹個符號。
(4)、若運算符的右不大於運算符棧棧頂的運算符(即OPS(topp)),則從操作數棧OVS中彈出兩個操作數,設先後彈出的操作數為a、b,再從運算符棧OPS中彈出壹個運算符,設為+,然後作運算a+b,並將運算結果壓入操作數棧OVS。本次的運算符下次將重新考慮。 第二種方法——
首先對表達式進行線性化,然後將線性表達式轉換成機器指令序列以便進行求值。 那麽什麽是表達式的線性化呢?人們所習慣的表達式的表達方法稱為中綴表示。中綴表示的特點是運算符位於運算對象的中間。但這種表示方式,有時必須借助括號才能將運算順序表達清楚,而且處理也比較復雜。 1929年,波蘭邏輯學家Lukasiewicz提出壹種不用括號的邏輯符號體系,後來人們稱之為波蘭表示法(Polish notation)。波蘭表達式的特點是運算符位於運算對象的後面,因此稱為後綴表示。在對波蘭表達式進行運算,嚴格按照自左至右的順序進行。下面給出壹些表達式及其相應的波蘭表達式。
表達式 波蘭表達式
A-B AB-
(A-B)*C+D AB-C*D+
A*(B+C/D)-E*F ABCD/+*EF*-
(B+C)/(A-D) BC+AD-/ OK,所謂表達式的線性化是指將中綴表達的表達式轉化為波蘭表達式。對於每壹個表達式,利用棧可以把表達式變換成波蘭表達式,也可以利用棧來計算波蘭表達式的值。 至於轉換和計算的過程和第壹種方法大同小異,這裏就不再贅述了。 下面給出轉換和計算的具體實現程序——/* first函數給出各個運算符的優先級,其中=為表達式結束符 */
int first(char c)
{ int p;
switch(c)
{ case '*': p=2; break;
case '/': p=2; break;
case '+': p=1; break;
case '-': p=1; break;
case '(': p=0; break;
case '=': p=-1; break;
}
return(p);
}
/* 此函數實現中綴到後綴的轉換 */
/* M的值宏定義為20 */
/* sp[]為表達式數組 */
int mid_last()
{ int i=0,j=0; char c,sm[M];
c=s[0]; sm[0]='='; top=0;
while(c!='\0')
{ if(islower(c)) sp[j++]=c;
else switch(c)
{ case '+':
case '-':
case '*':
case '/': while(first(c)<=first(sm[top]))
sp[j++]=sm[top--];
sm[++top]=c; break;
case '(': sm[++top]=c; break;
case ')': while(sm[top]!='(')
sp[j++]=sm[top--];
top--; break;
default :return(1);
}
c=s[++i];
}
while(top>0) sp[j++]=sm[top--];
sp[j]='\0'; return(0); 文章來自: 好喜愛學習網( ) 網址: /bianchengyuyan/cyuyan/11945.html