逆波兰表达式求值问题（c语言代码）
逆波兰表达式求值
提示：注意输入有空格，运用continue即可解决
前言
逆波兰表达式求值就是计算后缀式，优点在于不需要括号。
1 输入样例 1 2 + 1 2 * + 输出样例 5 2 输入样例 1 1 + 2 * 输出样例 4
一、解题思路
1.分析
由样例1可知从左到右先遇到一个数字 1 存下来，然后遇到一个数字 2 存下来，再遇到一个符号 + 此时取出2和1，进行计算 1+2 得到结果 3 存下来，继续向右遇到数字 1 存下来，向右遇到数字 2 存下来，再向右遇到符号 * 此时取出 2和1,进行计算2*1得到结果 2 存下来，向右遇到符号 + ，此时取出2和3 进行计算3+2 得到结果 5 存下来，存下来，最后输出 5 。此过程符合栈的存储方式
2.思路
所以解题思路： 1遇到数字就入栈。 2遇到符号就取出栈中两个数字，先是取出栈顶元素给B,再取出栈顶元素给A，后进行A ±*/ B计算，后将结果存回栈中，即栈顶元素为计算结果。 3最后字符数组为空时结束，取出栈顶元素并输出。
二、代码实现
#include <stdio.h>
#include <stdlib.h>
typedef int AElemType;
typedef struct Astatus* AStatus;
struct Astatus
{
AElemType Data;
struct Astatus* Next;
};
AStatus ACreatstatus()
{
AStatus headnode=(AStatus)malloc(sizeof(struct Astatus));
headnode->Next=NULL;
return headnode;
}
AStatus APush(AStatus D,int X)
{
AStatus newnode=(AStatus)malloc(sizeof(struct Astatus));
newnode->Data=X;
newnode->Next=D->Next;
D->Next=newnode;
}
AStatus APop(AStatus D)
{
if(D->Next==NULL)
return -1;
AStatus p=D->Next;
int X;
X=p->Data;
D->Next=p->Next;
free(p);
return X;
}
AStatus ATop(AStatus D)
{
if(D->Next==NULL)
return -1;
return D->Next->Data;
}
int AIsempty(AStatus D)
{
if(D->Next==NULL)
return -1;
return 0;
}
int main()
{
char scan[1024];
gets(scan);
AStatus D=ACreatstatus();//存储数字的栈
int i=0;
int x,y,z;
int change;
int sum=0;
for(i=0;scan[i]!=0;i++)
{
if(scan[i]== )
continue;
if((scan[i]>=0)&&(scan[i]<=9))
{
sum=0;
while((scan[i]>=0)&&(scan[i]<=9))
{
change=scan[i]-0;
sum=sum*10+change;
i++;
}
APush(D,sum);
i--;
}
else if(scan[i]==+)
{
y=APop(D);
x=APop(D);
z=x+y;
APush(D,z);
}
else if(scan[i]==-)
{
y=APop(D);
x=APop(D);
z=x-y;
APush(D,z);
}
else if(scan[i]==*)
{
y=APop(D);
x=APop(D);
z=x*y;
APush(D,z);
}
else if(scan[i]==/)
{
y=APop(D);
x=APop(D);
z=x/y;
APush(D,z);
}
}
printf("%d",ATop(D));
return 0;
}
总结
提示：这里对文章进行总结： 记住以下即可：遇到数字入栈，遇到符号计算。
上一篇：
通过多线程提高代码的执行效率例子