表达式求值(栈和队列)
时间： 1ms 内存：1000M
描述：
利用栈来实现含有加，减，乘，除等基本运算，输出表达式的值
输入：
3x(15/5)+8
输出：
17
示例输入：
24-[6+(27/3)x2]示例输出：
0提示：
参考答案（内存最优[752]）：
#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("%d\n",qiuhe(p,m));
return 0;
}参考答案（时间最优[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("%d\n",qiuhe(p,m));
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。