2 表達式計算
2.1 算符優先分析
算符優先分析是定義算符之間的某種優先關系,這種關系可以為表示以下三種:
a<ba的優先性低於b
a=ba的優先性等於b
a>ba的優先性高於b
其中a和b代表壹種算符,<、=和>不同於數學裏的大於、等於和小於,同時a<b並不代表b>a, a=b並不代表b=a。
2.2 表達式表示
在機器內部,任何壹個表達式都是由操作數、運算符和分界符組成,分界符表示壹個表達式的結束。假設在此討論的算符只含加、減、乘、除四種算術運算符和左、右圓括號。如壹個算術表達式A+(B-C/D)*E,這種算術表達式中的運算符壹般總是出現在兩個操作數之間稱中綴表達式。在計算機的編譯系統中,在處理中綴表達式之前,總是先將它變換成後綴表達式,即表達式中的運算符出現在操作數之後,且不含括號。把壹個中綴表達式變換成相應的後綴表達式首先考慮運算規則。算術運算的規則是:(1)先乘除後加減;(2)先括號內後括號外;(3)同級別時先左後右。則上面中綴表達式可寫成ABCD/-E*+,由此可知後綴表達式的兩個特點:(1)後綴表達式與中綴表達式的操作數先後次序相同,只是運算符的先後次序有所變化。後綴表達式的運算符次序就是其執行次序;(2)後綴表達式沒有括號(如表1)。
表1 後綴表達式的處理過程
2.3 算符優先關系
由後綴表達式特點(1)知,後綴表達式與中綴表達式的操作數排列次序相同,只是運算符改變了次序。編譯系統從左到右依次掃描中綴表達式,每讀到壹個操作數即將它作為後綴表達式的壹部分輸出。系統設置壹個存放運算符的棧,初始時棧頂置壹分界符#,並將其也看作運算符。每讀到壹個運算符,就將其優先級與棧頂位置運算符優先級進行比較,以決定是把所讀的運算符進棧還是將棧頂位置的運算符作為後綴表達式的壹部分輸出。表2給出了包括加、減、乘、除四種算術運算符和左、右圓括號和分界符的算術運算符間的優先級關系表。表中θ1代表棧頂運算符,θ2代表當前掃描讀到的運算符。
表2 運算符優先級關系
表2是四則運算三條規則的變形。對規則(1),當θ1為+或-,θ2為*或/時,θ1的優先級低於θ2的優先級(先乘除後加減);對規則(2),θ1當為+、-、*或/,θ2為(時,θ1的優先級低於θ2的優先級(先括號內後括號外);當θ1為+、-、*或/,θ2為)時,θ1的優先級高於θ2的優先級(先求出括號內的值);對規則(3),當θ1的運算符和θ2的運算符同優先級別時,令θ1的優先級高(同級別時先左後右)。由於後綴表達式無括號,當θ1為(,θ2為)時,用符號”=”表示去掉該對括號。當θ1為#時,θ2也為#時,表示整個表達式處理完畢。表2中空格處表示不允許出現這種情況,壹旦出現,即為中綴表達式語法出錯。
2.4 表達式計算
中綴表達式變換成相應的後綴表達式後,根據後綴表達式計算表達式的值方法為:設置壹個足夠大的堆棧,從前向後依次掃描後綴表達式,每讀到壹個操作數,就將其壓入堆棧;每讀到壹個運算符,就從棧頂取出兩個操作數施以該運算符所代表的操作,並把計算結果作為壹個新的操作數壓入堆棧,壹直到後綴表達式讀完。最後在棧頂位置的操作數就是該算術表達式的計算結果。
3 算法實現
#include
char newstr[20]; int p=0;
char proceed(char x1,char x2) /*算符比較*/
{char result1;
char Midstring[2];
result1='<';Midstring[0]=x2; Midstring[1]='\0';
if(((x1=='+'||x1=='-')&&strstr("+-)#",Midstring)!=-1)
||((x1=='*'||x1=='/')&&strstr("+-*/)#",Midstring)!=-1)
||(x1==')'&&strstr("+-*/)#",Midstring)!=-1))
result1='>';
else if((x1=='(' && x2==')')||(x1=='#' && x2=='#'))
result1='=';
else if((x1=='(' && x2=='#')||(x1==')' && x2=='(')||(x1=='#' && x2==')'))
result1=' ';
return(result1);}
int strstr(char str1[],char str2[])
{int i,j,k,m,n;
char tempStr1,tempStr2;
m=strlen(str1);
n=strlen(str2);
for(i=0;i {k=i;
for(j=0;j<1;j++,k++)
{tempStr1=str1[k];
tempStr2=str2[j];
if(tempStr1==tempStr2)
continue;
else break;}
if(j>=n) return(1);}
return(-1);}
/*中綴表達式變換後綴表達式*/
intprotfix(char str[])
{char stack[20];
char x1,x2,x;
int j=0,k=0;
stack[0]='#';
x2=str[j];
x1=stack[0];
while(1)
{if(x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&&x2!='('&&x2!=')'&&x2!='#')
{newstr[p++]=x2;
j++;x2=str[j];}
else
本文原文
if(proceed(x1,x2)=='<')
{stack[++k]=x2;
x1=stack[k];
j++; x2=str[j];
}else if(proceed(x1,x2)=='>')
{ x=stack[k--];
newstr[p++]=x;
x1=stack[k];}
else if(proceed(x1,x2)=='='&&x1=='('&&x2==')')
{k--;x1=stack[k];
j++;x2=str[j]; }
Else
if(proceed(x1,x2)=='='&&x1=='#'&&x2=='#')
return(1);
else if(proceed(x1,x2)= =' ')
break;}
return(0);}
double count(char str[])/*計算表達式的值*/
{double x1,x2,x; int a,i=0;
while(str[i]!='\0')
{if(isdigit(str[i]))
push(str[i]-48);
else
Switch(str[i])
{case '+': x1=pop();x2=pop();
x=x1+x2;push(x);break;
case '-': x1=pop();x2=pop();
x=x1-x2;push(x);break;
case '*': x1=pop();x2=pop();
x=x1*x2;push(x);break;
case '/': x1=pop();x2=pop();
x=x1/x2; push(x); break; }
i++;}}
return(x);}
4 結束語
表達式計算作為程序設計語言的基礎,是高級程序設計語言學習者和程序員必備的基礎知識,本文通過算符優先分析和堆棧的方法,給出了算術表達式的計算過程,同時給出了算法描述,有助於高級語言初學者和計算機編程人員熟悉計算機內部表達式計算的處理過程,更好地學習和掌握高級語言的編程技術。