前言:大学的时候为了更好地理解栈的应用,写了个基于堆栈的表达式求值程序,今天搬上来,修行尚浅,不喜勿喷,我来为大家科普一下关于c语言设计函数求数组的平均值?下面希望有你要的答案,我们一起来看看吧!

c语言设计函数求数组的平均值(C语言堆栈应用之逆波兰法表达式求值)

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; }

,