逆波兰表达式求值

提示：注意输入有空格，运用continue即可解决

前言

逆波兰表达式求值就是计算后缀式，优点在于不需要括号。

1 输入样例 1 2 + 1 2 * + 输出样例 5 2 输入样例 1 1 + 2 * 输出样例 4

一、解题思路

1.分析

此过程符合栈的存储方式

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;
}

总结

提示：这里对文章进行总结： 记住以下即可：遇到数字入栈，遇到符号计算。