nbl.c

逆波兰式计算

#include <stdio.h> 
#include <ctype.h> 

void transform(char *str,int a[][2],int *n) 
//将输入的字符串转化为格式化的数组以记录输入的表达式，str为输入的字符串，a为目标数组，n记录数组a的大小 
{ 
int i; 
*n=1; 
a[0][0]=1; 
a[0][1]='(';//在表达式首添加一个括号 
for (i=0;str[i];) 
{ 
if (isdigit(str[i])) 
{ 
a[*n][0]=0; 
a[*n][1]=0; 
while (isdigit(str[i])) 
{ 
a[*n][1]=a[*n][1]*10+str[i]-'0'; 
i++; 
} 
} 
else 
{ 
if (str[i]=='(') a[*n][0]=1; 
else if (str[i]==')') a[*n][0]=2; 
else if (str[i]=='*') a[*n][0]=3; 
else if (str[i]=='/') a[*n][0]=4; 
else if (str[i]=='+' || str[i]=='-') 
{ 
if (i==0 || (!isdigit(str[i-1]) && str[i-1]!=')')) 
{ 
a[*n][0]=0; 
a[*n][1]=0; 
(*n)++; 
} 
if (str[i]=='+') a[*n][0]=5; 
else a[*n][0]=6; 
} 
a[*n][1]=str[i]; 
i++; 
} 
(*n)++; 
} 
a[*n][0]=2; 
a[*n][1]=')';//在表达式尾添加一个反括号 
(*n)++; 
} 

void poland(int a[][2],int n,int p[][2],int *m) 
//将格式化数组转化为逆波兰表达式，a为输入的数组，n为其长度，p为输出逆波兰表达式的目标，m记录逆波兰表达式的长度 
{ 
int i; 
int stack[1000];//转化所用的栈 
int depth;//栈的深度 
depth=0; 
*m=0; 
for (i=0;i<n;i++) 
{ 
if (a[i][0]==0) stack[depth++]=i; 
else if (a[i][0]==1) stack[depth++]=i; 
else if (a[i][0]==2) 
{ 
while (a[stack[depth-1]][0]!=1) 
{ 
depth--; 
p[*m][0]=a[stack[depth]][0]; 
p[*m][1]=a[stack[depth]][1]; 
(*m)++; 
} 
depth--; 
} 
else if (a[i][0]==3 || a[i][0]==4) 
{ 
while (a[stack[depth-1]][0]==0 || a[stack[depth-1]][0]==3 || a[stack[depth-1]][0]==4) 
{ 
depth--; 
p[*m][0]=a[stack[depth]][0]; 
p[*m][1]=a[stack[depth]][1]; 
(*m)++; 
} 
stack[depth++]=i; 
} 
else if (a[i][0]==5 || a[i][0]==6) 
{ 
while (a[stack[depth-1]][0]!=1) 
{ 
depth--; 
p[*m][0]=a[stack[depth]][0]; 
p[*m][1]=a[stack[depth]][1]; 
(*m)++; 
} 
stack[depth++]=i; 
} 
} 
} 

void print_poland(int p[][2],int m) 
//打印逆波兰表达式，p为逆波兰表达式，m为表达式长度 
{ 
int i; 
for (i=0;i<m;i++) 
{ 
if (p[i][0]==0) printf("%d",p[i][1]); 
else printf("%c",p[i][1]); 
} 
putchar('\n'); 
} 

double evaluate(int p[][2],int m) 
//对逆波兰表达式求值，p为逆波兰表达式，m为表达式长度 
{ 
double stack[1000];//求值所用的栈 
int depth;//栈的深度 
int i; 
depth=0; 
for (i=0;i<m;i++) 
{ 
if (p[i][0]==0) stack[depth++]=p[i][1]; 
else 
{ 
double a,b; 
b=stack[--depth]; 
a=stack[--depth]; 
if (p[i][0]==3) stack[depth++]=a*b; 
else if (p[i][0]==4) stack[depth++]=a/b; 
else if (p[i][0]==5) stack[depth++]=a+b; 
else stack[depth++]=a-b; 
} 
} 
return stack[0]; 
} 

int a[1000][2]; 
int n; 
int p[1000][2]; 
int m; 

main() 
{ 
transform("5*(8-2)+9",a,&n); 
poland(a,n,p,&m); 
print_poland(p,m); 
printf("The result of the expression is %lf\n",evaluate(p,m)); 
return; 
}