天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

后缀表达式求值

Posted on 2012-09-17 12:03 hoshelly 阅读(1408) 评论(0)  编辑 收藏 引用 所属分类: DS && Algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 1000
static int N; //N栈的大小
static int *s;
void STACKinit(int maxN) //建立一个动态数组s,相当于建立并初始化栈
{
    s = (int *)malloc(maxN*sizeof(int));
    N=0;
}
int STACKempty()
{
    return N==0;
}
void STACKpush(int item)
{
    s[N++] = item;
}
int STACKpop()
{
    return s[--N];
}

int main()
{
    char a[M];
    gets(a); //输入后缀表达式,每个整数之后至少要有一个空格
    int i,len,ok;
    char k[15]={' ','0','1','2','3','4','5','6','7','8','9','+','-','/','*'};
    len=strlen(a);
    while(1)  //检查输入字符串的合法性(仅限于检查输入是否为包含数字和+ - * / 和 ' '的字符串)
    {
       ok=0;
       for(i=0;i<len;i++) 
      {
         for(int j=0;j<15;j++)
         {
            if(a[i] == k[j])
            {
                ok=1;
            }
         }
         if(!ok)
         {
             printf("Input error! please input again:\n");
             break;
         }
       }
       if(!ok)
       {
          gets(a);
          len=strlen(a);
       }
       else
           break;
    }

    STACKinit(len); //初始化N=0
    for(i=0;i<len;i++)
    {
        if(a[i] == '+')
            STACKpush(STACKpop()+STACKpop());
        if(a[i] == '*')
            STACKpush(STACKpop()*STACKpop());
        if(a[i] == '-')
        {
            b = STACKpop();
            c = STACKpop();
            STACKpush(c-b);
        }

        if(a[i] == '/')
        {
            b = STACKpop();
            c = STACKpop();
            STACKpush(c/b);
        }

            
        if((a[i] >= '0') && (a[i] <= '9')) //如果遇到数字,则先压入0进栈
            STACKpush(0);
        while((a[i] >='0') && (a[i] <='9'))
            STACKpush(10*STACKpop()+(a[i++]-'0'));//再将“字符数字”转换为数字
    }

    printf("%d \n",STACKpop());
    return 0;
}

示例:

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理