题目描述
利用栈来实现含有加,减,乘,除等基本运算,输出表达式的值
输入
3x(15/5)+8
输出
17
样例输入
24-[6+(27/3)x2]
样例输出
0
参考代码
#include <stdio.h>
#include <ctype.h>
int youxian(char ch)
{
switch(ch)
{
case '[':
case '(': return 1;
case ']':
case ')': return 2;
case 'x': return 3;
case '/': return 4;
default: return 0;
}
}
void ruzhan(char *str,int a[][2],int *n)
{
int i,t;
*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
{
t=youxian(str[i]);
if(t!=0)
a[*n][0]=t; else
{
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)
{
int i;
int stack[1000];
int d=0;
*m=0;
for (i=0;i<n;i++)
{
if(a[i][0]==0)
stack[d++]=i; else if(a[i][0]==1)
stack[d++]=i; else if(a[i][0]==2)
{
while (a[stack[d-1]][0]!=1)
{
d--;
p[*m][0]=a[stack[d]][0];
p[*m][1]=a[stack[d]][1];
(*m)++;
}
d--;
} else if(a[i][0]==3||a[i][0]==4)
{
while (a[stack[d-1]][0]==0||a[stack[d-1]][0]==3||a[stack[d-1]][0]==4)
{
d--;
p[*m][0]=a[stack[d]][0];
p[*m][1]=a[stack[d]][1];
(*m)++;
}
stack[d++]=i;
} else if(a[i][0]==5||a[i][0]==6)
{
while(a[stack[d-1]][0]!=1)
{
d--;
p[*m][0]=a[stack[d]][0];
p[*m][1]=a[stack[d]][1];
(*m)++;
}
stack[d++]=i;
}
}
}
int qiuhe(int p[][2],int m)
{
int stack[1000];
int d=0;
int i;
for (i=0;i<m;i++)
{
if (p[i][0]==0) stack[d++]=p[i][1]; else
{
int a,b;
b=stack[--d];
a=stack[--d];
if (p[i][0]==3) stack[d++]=a*b; else if (p[i][0]==4) stack[d++]=a/b; else if (p[i][0]==5) stack[d++]=a+b; else stack[d++]=a-b;
}
}
return stack[0];
}
int main()
{
int a[1000][2],p[1000][2];
int n,m;
char s[1000];
gets(s);
ruzhan(s,a,&n);
poland(a,n,p,&m);
printf("%dn",qiuhe(p,m));
return 0;
}
解析
暂无