C语言堆栈应用之逆波兰法表达式求值

前言：大学的时候为了更好地理解栈的应用，写了个基于堆栈的表达式求值程序，今天搬上来，修行尚浅，不喜勿喷

一、实现功能

在窗口中输入要求的表达式，实现表达式的求值计算，包括带“（）”的表达式，以及小数表达式的求值，基本得以实现。经程序处理计算后输出结果 。

效果图如下

二、 算法概述

假设有两个栈：snum(用来存放运算数)、sope(用来存放符号)；

假设现有一表达式：3+2*4+6/（2+1），求值过程如下：

1. 判断是数字还是字符（+-*/ （）），是数字就入到snum栈。

2. ①若是字符‘+’‘-’‘*’‘/’ ‘（’时调用处理函数进行入栈或计算处理：（a）.若sope栈空或现在取到的符号为‘（’时入栈(b).获得sope栈顶元素的值并与现在取到字符进行优先级比较：如果现在的字符（运算符）的优先级小于SOpe栈顶元素的值的优先级，那么从snum中取出两个数字与现在字符进行计算，把得到结果入栈；否则将字符入到sope栈 ②当出现‘）’，取出sope中的栈顶元素（运算符）和snum中的两个数字进行相应计算，计算结果再次入栈并把sope的栈顶元素（’）’）出栈。

3. 在字符中没有出现字符串结束标识符（‘\0’）时，重复1、2步。

4. 对输入表达式（字符串），进行处理完后，若sope栈未空，则从snum取出两个数字、从sope中取出运算符进行计算处理，计算结果再入栈。

当sope为空栈时，从snum取出最后结果并输出结果。

三、 源代码

废话不多说，下面直接上源代码,程序不多，都有注释，不再一一解释。

#define.h头文件 #

#ifndef define_header
#define define_header
#include
#include
#include
#include
#include

#define STACK_INIT_SIZE 100//定义栈的初始分配空间
#define STACKINCRENMENT 10//栈的分配增量

//定义栈
typedef struct
{
 double *top;//栈顶
 double *base;//栈底
 int stacksize;//当前栈的大小
}stack;

stack *creatorStack(stack *s);//创建并初始化栈
stack *clearStack(stack *s);
void push(stack *s,double e);//入栈
void pop(stack *s,double *e);//出栈

void deal_ope(stack *snum,stack *sope,double ope);//符号出现+ - * /（ 时处理函数
void deal_bracket(stack *snum,stack *sope);//符号出现） 时处理的函数
int get_pri(double ope);//获取符号优先级
void compute(stack *snum,double ope);//计算函数
int stack_is_empty(stack *L);//判断是否为栈空函数
int Get_Top(stack *S, double *e) ;//获取栈顶元素
int f_int(double a);//浮点型转int型函数
#endif

#man.c文件#

#include"define.h"
int main()
{
 stack snum,sope;
 int i=0,j=0;
 double value1=0,value=0;
 int flag_shuzi=0,flag_dian=0;
 double old_ope=0,t;
 char str[32];

 creatorStack(&snum);
 creatorStack(&sope);

 printf("###################欢迎您使用表达式求值计算器#####################\n###################2017年10月25日#################################\n");
printf("请输入表达式，然后按回车键进行计算：\n");
 while(1)
 {
  gets(str);
 while (str[i]!= '\0')
    {
        //获取输入的数字
                if((str[i] >= '0' && str[i] <= '9')||str[i]=='.')
        {
            //value = value * 10 + str[i] - '0';
            value1=str[i]-'0';
            if(str[i]=='.')  //str[i]为‘.’时，说明是小数进行处理，并把此时的value1置0；保证valu不变
                {flag_dian=1;value1=0;}
            if(flag_dian)
            {
            t=1/(pow(10.0000,j));    //字符串转为小数的数值
                value=value+value1*t;
                j++;
            }
            else
            value=value*10+value1;//非小数点
            if ((str[i+1] < 0 stri1> '9')&&str[i+1]!='.')
            {
              flag_shuzi = 1;
               flag_dian=0;j=0;
            } 
        }
        else//ope
        {
            if (flag_shuzi)//value里面存储了数字，将其入栈
            {
           push (&snum, value);
            
            flag_shuzi = 0;//清0
            value1=value=0;
        }
        if(str[i] == ')')// ）出现时的处理
        {
            deal_bracket(&snum,&sope);
        }
        else //+-*/( 等情况 
        {
             deal_ope(&snum,&sope,str[i]);
        } 
        
    } 
     i++; 
       } 
 //如果flag_shuzi = 1.说明还有数值,将其入栈
 if (flag_shuzi)
    {
        push(&snum,value);
        flag_shuzi=0;
    } 
 while (!stack_is_empty(&sope))
    {
        pop(&sope,&old_ope);
        compute(&snum,old_ope);
    }
    value=0;i=0;
    pop(&snum,&value);//取出结果、打印结果
    printf("%s = %f\n",str,value); 
    value1=value=0;
    memset(str,0,32);
    printf("请再次输入：\n");
  }
 return 1;
}

#method.c文件#

#include"define.h"
void deal_ope(stack *snum,stack *sope,double ope)
{
  double old_ope;
    //如果sope符号栈是空栈或者符号为‘(’
    if (stack_is_empty(sope) || (f_int(ope)) == '(')
    {
        //将括号(入栈
        push(sope,ope);
        return ;
    }
    //获得当前的符号栈的栈顶
    Get_Top(sope,&old_ope);
    if (get_pri(ope) > get_pri(old_ope))//传入符号大于当前栈顶，则将传入符号入栈
    {      
        push(sope,ope);
        return ;    
    }

    while (get_pri(ope) <= get_pri(old_ope)) //如果传入的符号优先级小于当前栈顶符号
    {
        //将当前栈顶的符号取出与数字栈中顶端的两个数字进行计算
        pop(sope,&old_ope);
        compute(snum,old_ope);
        if (stack_is_empty(sope))
        {
            break;
        }
        Get_Top(sope,&old_ope);
    }
    push(sope,ope);
}
/*如果检测到符号时')',则执行该函数，参数为数字栈和符号栈*/
void deal_bracket(stack *snum,stack *sope)
{
     double old_ope;
    //获得当前的符号栈的栈顶符号
    Get_Top(sope,&old_ope); 
    while ((f_int(old_ope)) != '(')
    {   
        pop(sope,&old_ope);  //当前符号出栈然后将数字出栈两个进行计算,在括号内优先级最高，
        compute(snum,old_ope);
        
        Get_Top(sope,&old_ope);//然后再次取出当前符号栈栈顶符号，至到出现‘(’    
    }
    
    pop(sope,&old_ope);//最后将出现的左扩号出栈丢弃
}
int get_pri(double ope) //获取运算符的优先级
{
   switch(f_int(ope))
    {
    case '(':   return 0;break;
    case '+':
    case '-':   return 1;break;
    case '*':
    case '/':   return 2;break;
    default :   return -1;break;
    }
}

void compute(stack *snum,double ope)/* 将两个数出栈、根据ope符号计算，然后再次入栈 */
{
    double n,n1,n2;
    pop(snum,&n2);//依次获得数值栈的栈顶两个数
    pop(snum,&n1);
    switch(f_int(ope)) //计算
    {
        case '+':   n = n1 + n2; break;
        case '-':   n = n1 - n2; break;
        case '*':   n = n1 * n2; break;
        case '/':   n = n1 / n2; break;
    }
    push(snum,n); //计算完再入栈
    n=n1=n2=0;
}
int f_int(double a) //浮点型数据转为整型数据
{
    int b;
    b=a;
    return b;
}

#SqStack.c文件#

#include"define.h"
stack *creatorStack(stack *s)
{
 s->base=(double*)malloc(STACK_INIT_SIZE *sizeof(double));

 if(NULL==s) //假设s没有分配成功
 {
  exit(-1);
 }
 s->top=s->base;//初始化栈
 s->stacksize=STACK_INIT_SIZE;
}


stack *clearStack(stack *s)//清空栈
{
 if(NULL==s->base)
 {
  printf("\n Sorry, stack does not exist！\n");
  return ;
 }
 s->top=s->base;
 return s;
}


void push(stack *s,double e)//进栈操作
{

 if((s->top-s->base)>STACK_INIT_SIZE) //s是否已满，若栈满，重新分配空间
 {
  s->base=(double*)realloc(s->base,(STACKINCRENMENT+STACK_INIT_SIZE)*sizeof(double));
  if(NULL==s->base)
  {
   return;
  }
  //将栈顶指针指向栈顶
  s->top=s->base+s->stacksize;
  s->stacksize+=STACKINCRENMENT;
 }
 
 *(s->top)=e;//将元素e，写入栈顶
 s->top++;
}

void pop(stack *s,double *e)//出栈
{
 if(s->top==s->base)
 {
   exit(-1);
 }

 s->top--;
 *e=*(s->top);
}
int stack_is_empty(stack *s)//判断栈是否为空
{
    return (s->top ==s->base);
}
int Get_Top(stack *S, double *e) //获取栈点元素 
{  
    if(S->top == S->base)  
        return -1;  
    else 
    *e=*(S->top-1); 
    return 1;  
}