回 帖 发 新 帖 刷新版面

主题:(原创)栈的应用(算术表达式求值)

谁有数据结构题集的实习部分答案 给我份做参考啊共享下 有的联系我QQ327489180
自己写了个和大家共享下
认为好用的 给我顶下~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include<stdlib.h>
#include<stdio.h>
#define stack_init_size1 40
#define stack_init_size2 20
#define stackincrement1 40
#define stackincrement2 20
typedef struct{
    int *base;
    int *top;
    int stacksize;
}s_stack;
typedef struct{
    char *base;
    char *top;
    int stacksize;
}f_stack;

static char youxian[7][7]=
    {
        {'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},
        {'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},
        {'<','<','<','<','<','=','>'},{'>','>','>','>','>','>','>'},
        {'<','<','<','<','<','>','='}
    };

int in(char c)
{
    switch(c)
    {
    case '+': return 0;
    case '-': return 1;
    case '*': return 2;
    case '/': return 3;
    case '(': return 4;
    case ')': return 5;
    case '#':return 6;
    default:return 9;
    }

}

void s_push(s_stack *s,int e)
{

     if(s->top-s->base>=s->stacksize)
     {
         s->base=(int *)realloc(s->base,(s->stacksize+stackincrement1)*sizeof(int));
         if(!s->base) exit(0);
         s->top=s->base+s->stacksize;
         s->stacksize+=stackincrement1;
     }
    *s->top=e; s->top++;
    /*printf("the s_stack has the data:%d\n",*(s->top-1));*/
}
void  f_push(f_stack *f,char e)
{
     if(f->top-f->base>=f->stacksize)
     {
         f->base=(char *)realloc(f->base,(f->stacksize+stackincrement2)*sizeof(char));
         if(!f->base) exit (0);
         f->top=f->base+f->stacksize;
         f->stacksize+=stackincrement2;
     }
     *f->top=e;f->top++;
    /* printf("the f_stack has the sign:%c\n",*(f->top-1));*/
}

int s_gettop(s_stack *s)
{
    s->top--;
    return *s->top;
}

char f_gettop(f_stack *f)
{
    f->top--;
    return *f->top;
}

char pduan(f_stack *f,char c)
{
    int m,n;
    char w;
    m=in(c);
    w=*(f->top-1);
    n=in(w);
    return youxian[n][m];
}

int yunsuan(int p,char r,int q)
{
        switch(r)
    {
        case '+': return q+p;
        case '-': return q-p;
        case '*': return q*p;
        case '/': return q/p;
    }
}

回复列表 (共36个回复)

沙发

int main()

{
    int h=0,jieguo,wrong;
    char c;
    s_stack s;
    f_stack f;
    s.base=(int*)malloc(stack_init_size1*sizeof(int));
    if(!s.base) return 0;
    s.top=s.base;
    s.stacksize=stack_init_size1;

    f.base=(char*)malloc(stack_init_size2*sizeof(char));
    if(!f.base) return 0;
    f.top=f.base;
    f.stacksize=stack_init_size2;
    *f.top='#';f.top++;

    printf("please press the sizi end by enter!");
    c=getchar();
    while(c!='\n')
    {   int t;
        int p,q;
        char r;
        if(in(c)==9)
        {   if(h>0)
         {
            t=s_gettop(&s);
            s_push(&s,t*10+c-48);
         }
         else s_push(&s,c-48);
         h++;c=getchar();

        }
        else
        switch(pduan(&f,c))
        {
          case '<':
               f_push(&f,c);c=getchar();h=0;break;
          case '=':
               f.top--;
               f.stacksize--;
               c=getchar();h=0;break;
          case '>':
               p=s_gettop(&s);
               q=s_gettop(&s);
               r=f_gettop(&f);
             if(r=='/'&&p==0)
               {wrong=1;break;}
             else
               { jieguo=yunsuan(p,r,q);
                 s_push(&s,jieguo);h=0;break;
               }
        }
    }
    while((c=='\n')&&(*(f.top-1)!='#'))
    {
        int p,q;
        char r;
        p=s_gettop(&s);
        q=s_gettop(&s);
        r=f_gettop(&f);
    if(r=='/'&&p==0)
        {wrong=1;break;}
    else
        jieguo=yunsuan(p,r,q);
        s_push(&s,jieguo);
    }
    if(wrong==1)
        printf("It is wrong!\n");
    else
        printf("the answer is %d\n",s_gettop(&s));
}
[em9][em9]

板凳

再加一些注解就更好了!

3 楼

楼主啊,非常鼓励发原创文章,要是写得更好一些,可以写成小论文的形式,那就更好啦~~

已经加精并收集了~~

4 楼

多谢老大指教 下次一定做的更好 满足大家的要求!
A za za fingting!
[em3]

5 楼

我想请教上面的斑竹:
 if(in(c)==9)
        {   if(h>0)
         {
            t=s_gettop(&s);
            s_push(&s,t*10+c-48);//乘10又减48是什么意思???希望下次斑竹最                                //好把注释也写上
         }
         else s_push(&s,c-48);
         h++;c=getchar();

        }

6 楼

应该我getchar 来拿进数据 比如我要拿进数字12 而且不进行类型转换 用t*10+c-48 就对应着数字12 因为我开始插入的t是c-48那么就是1 显然t*10+c-48的结果就是12 只是用来处理连续输入数字的情况 你用atoi函数进行操作的效果是一样的 

7 楼

这个程序写的不错,真的厉害,小弟佩服.我也写了个,但是有点问题.
#define max 100
#include<iostream>
#include<malloc.h>
using namespace std;
typedef struct
{char *base; 
 char *top;
}Stack;

void InitStack(Stack &S)
{S.base=(char*)malloc(max*sizeof(char));
 S.top=S.base;
}

int GetTop(Stack S)
{char e;
 e=*(S.top-1);
 return e;
}

void Push(Stack &S,int e)
{
 *S.top++=e;
}

void Pop(Stack &S,int &e)
{
 e=*--S.top;
}

int is_operator(int oper)
{switch(oper)
 {case '+':
  case '-':
  case '*':
  case '/':
  case '(':
  case ')':
  case '#':
  return 1;
  default:return 0;
 }
}

int priority(int a)
{switch(a)
 {case '#':return 1;
  case '-':return 2;
  case '+':return 3;
  case '*':return 4;
  case '/':return 5;
  case '(':
  case ')':return 6;
  default:return 0;
 }
}

int Operate(int a,int b,int c)
{switch(b)
 {case '+':return(a+c);
  case '-':return(a-c);
  case '*':return(a*c);
  case '/':return(a/c);
  default:return 0;
 }
}

int main()
{int x,f,theta,a,b,c;
 Stack OPTR,OPND;
 InitStack(OPTR);
 Push(OPTR,'#');
 InitStack(OPND);
 cin>>c;
 while(c!='#'||GetTop(OPTR)!='#')
 {if(is_operator(c)!=0)
    {Push(OPND,c);
      c=getchar();
     }
  else if(priority(GetTop(OPTR))<priority(c))
         {Push(OPTR,c);
           c=getchar();
          }
        else {if(priority(GetTop(OPTR))==priority(c))
                 {Pop(OPTR,x);c=getchar();
                  }
               else  
                   {Pop(OPTR,theta);
                    Pop(OPND,b); Pop(OPND,a);
                    Push(OPND,Operate(a,theta,b));
                    }
                }
 }
 Pop(OPND,f);
 cout<<"f="<<f<<endl;
 return 0;
}

8 楼

你写的的确不错,但是当我的表达式是[(3+4)*5]/5,类似这种就不行了,结果不对,是不是在有些地方忽略了一些东西。

9 楼

static char youxian[7][7]=
    {
        {'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},
        {'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},
        {'<','<','<','<','<','=','>'},{'>','>','>','>','>','>','>'},
        {'<','<','<','<','<','>','='}
    };
在这个中,那些符号的安排有什么规律吗?

10 楼

这个是多维的数组 行列依次都是+.-.*./(.).#
象你说的那样 开始写的时候就考虑了()这样的情况 大括号的没写进去 呵呵 这也许是个缺陷了 但是如果都写的话还有个{}中括号 在判断上就有点复杂了
[em19] 有时间改了再传吧.哪位高手帮我改下也行啊.也包括你.小弟感激不尽!

我来回复

您尚未登录,请登录后再回复。点此登录或注册