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

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

大象踩蚂蚁 [专家分：0] 发布于 2006-04-04 07:56:00

谁有数据结构题集的实习部分答案给我份做参考啊共享下有的联系我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;
    }
}

本帖地址： http://bbs.pfan.cn/post/153809.html

回复列表（共36个回复）

31 楼

Glock18 [专家分：0] 发布于 2008-02-05 20:39:00

float Operate(float a,float b,char theoper)      //运算。。theoper为运算符
{
      float c;
      switch(theoper){
                     case '+':
                          c=a+b;
                          break;
                     case '-':
                          c=a-b;
                          break;                     case '*':
                          c=a*b;
                          break;
                     case '/':
                          c=a/b;
                          break;
                     default:
                           printf("wrong");
                          }
      return c;
      }
int isnum(char num)      //判断它是不是一个数
{
     if(num=='*'||num=='/'||num=='+'||num=='-'||num=='('||num==')'||num=='=')
                                              return false;
    else return true;
}

char Precede(char a,char b)       //判断a和b 的运算级
{
     switch(a){
               case ')':switch (b){
                                   case '(':return '=';
                                   default:return '>';
                                   }
               case '(':if(b==')')
                                  return '=';
                        else
                                  return '<';
               case '*':case'/':switch(b){
                                          case '(':return '<';
                                          default:return '>';
                                          }
               case '+':case '-':switch(b){
                                           case '(':case '*':case '/':return '<';
                                           default:return '>';
                                           }
               case '#': if(b=='=') return '=';
                         else return '<';
               }
}

32 楼

Glock18 [专家分：0] 发布于 2008-02-05 20:42:00

#define SIZE 10
int main()
{
    char array[MAXSIZE],temporary[SIZE];
    char temp;
    SqStack Soperate;
    SnStack Snumber;
    int Length,i,cnt;
    float tempn,a,b;
    InitStack(Soperate);
    InitStackn(Snumber);
    scanf("%s",array);
    Length=strlen(array);
    St_push(Soperate,'#');                     //先将一个#存入运算符栈底

33 楼

Glock18 [专家分：0] 发布于 2008-02-05 20:42:00

    for(i=0;i<Length;i++){
                          if(isnum(array[i])){
                                              for(cnt=0;isnum(array[i]);i++)
                                                                            temporary[cnt++]=array[i];
                                              temporary[cnt]='\0';
                                              tempn=(float)atof(temporary);               //temporary做缓冲区
                                             Sn_push(Snumber,tempn);
                                             i--;
                                             }
                          else{
                               temp=St_gettop(Soperate);
                               switch(Precede(temp,array[i])){
                                                               case '<':
                                                                    St_push(Soperate,array[i]);
                                                                    break;
                                                               case '=':
                                                                    St_pop(Soperate);
                                                                    break;
                                                               case '>':
                                                                    a=Sn_pop(Snumber);
                                                                    b=Sn_pop(Snumber);                                                    b=Operate(a,b,St_pop(Soperate));
                                                                    Sn_push(Snumber,b);
                                                                    i--;
                                                                    break;
                                                                    }
                               }
                          }
    printf("%f",Sn_gettop(Snumber));
    return 0;
    }

34 楼

雨下的时候 [专家分：440] 发布于 2008-03-02 12:57:00

我用c#也写了个，可以识别函数名，可以运算log(10,2),exp(3)等。

35 楼

diaoxue [专家分：600] 发布于 2008-03-15 12:44:00

也写了个，算法来自严蔚敏的数据结构。优先级数组栲楼主的，谢了，太懒了，不想输那么多。
vc6.0 通过，输入表达式，以‘#’结尾，且在一行即可。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define STACK_INIT_SIZE 100//初始分配量
#define STACKINCREMENT 10//分配增量
//#define EOF -1
#define OVERFLOW 1

typedef struct ///////定义结构
{
    char *base;
    char *top;
    int stacksize;
}SqStack;

void InitStack(SqStack &S)///初始化栈
{
    S.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
}

char GetTop(SqStack &S,char &e)///获得栈顶元素
{
    if(S.top==S.base)return 0;
    e=*(S.top-1);
    return e;
}

void Push(SqStack &S,char e)///入栈
{
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
        if(!S.base)exit(1);
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
}

char Pop(SqStack &S,char &e)///出栈
{
    if(S.top==S.base)exit(1);
    e=* --S.top;
    return e;
}
bool StackEmpty(SqStack &S)//判空
{
    if(S.base==S.top)return true;
    return false;
}

/*void ClearStack(SqStack &S)//清空栈
{
    S.base=S.top;
    S.stacksize=0;
}*/

bool InOptr(char c)
{
    int i=0;
    char opt[7]={'+','-','*','/','(',')','#'};
    for(i=0;i<7;i++)
    {
        if(opt[i]==c)
        {
            return true;
        }
    }
    return false;
}

char Precede(char c,char d)
{
    char youxian[7][7]=
    {
        {'>','>','<','<','<','>','>'},
        {'>','>','<','<','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'<','<','<','<','<','=','>'},
        {'>','>','>','>','>','>','>'},
        {'<','<','<','<','<','>','='}
    };
    char opt[7]={'+','-','*','/','(',')','#'};
    int m,n,i;
    for(i=0;i<7;i++)
    {
        if(c==opt[i])
        {
            m=i;
        }
        if(d==opt[i])
        {
            n=i;
        }
    }
    return youxian[m][n];
}

char Operate(char a,char theta,char b)
{
     switch(theta)
     {
     case '+':
          return (a-'0')+(b-'0')+'0';
          break;
     case '-':
          return (a-'0')-(b-'0')+'0';
          break;
     case '*':
          return (a-'0')*(b-'0')+'0';
          break;
     case '/':
          return (a-'0')/(b-'0')+'0';
          break;
     }
}

void EvaluateExpression()
{
    SqStack optr,//运算符
            opnd;//操作数
    char opt,//临时变量，存optr
         x,
         a,
         b,
         theta;
    InitStack(optr);
    Push(optr,'#');
    InitStack(opnd);
    char c=getchar();
    while(c != '#' || GetTop(optr,opt) != '#')
    {
        //if(! InOptr(c,OP))//不是运算符
        if(! InOptr(c))
        {
            Push(opnd,c);
            c=getchar();
        }
        else
        {
            switch(Precede(GetTop(optr,opt),c))
            {
            case'<':
                Push(optr,c);
                c=getchar();
                break;
            case'=':
                Pop(optr,x);
                c=getchar();
                break;
            case'>':
                Pop(optr,theta);
                Pop(opnd,b);
                Pop(opnd,a);
                Push(opnd,Operate(a,theta,b));
                break;
            }
        }
    }
    char result;
    int res=GetTop(opnd,result)-'0';
    printf("%d",res);
}

int main()
{
    EvaluateExpression();
    //system("pause");
    return 0;
}

36 楼

Erican [专家分：0] 发布于 2008-04-05 20:50:00

楼主各位高手。。能不能编个输入中缀表达式转换成后缀表达式求值....不要忽略小数。。负号。。

我来回复

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

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

回复列表（共36个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共36个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共36个回复）