逆波兰表达式求值 c语言_波兰表达式

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<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #include<math.h> #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' || str[i+1] > '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; }