前言:
今天姐妹们对“c语言栈实现表达式求值”大体比较珍视,朋友们都需要分析一些“c语言栈实现表达式求值”的相关知识。那么小编同时在网络上收集了一些对于“c语言栈实现表达式求值””的相关文章,希望各位老铁们能喜欢,你们快快来学习一下吧!C语言是面向过程的,而C++是面向对象的
由于工作必要比来在研究PHP扩展,无可按捺的涉及到了C说话。从出了黉舍往后C说话在实际工作中还没有效到过,所以必需要前进前辈行一点复习工作。小我认为对付熟悉一样工具说最好的编制是上手理论。于是便想起了那时大学的时辰教员安插过的一道问题问题,用C说话实现简单数学表达式的分析和求值,斗劲遗憾的是当初没能把问题问题完成。就想侧重新试一试,算是补一下当初的功课。
还记适当初的思绪是,轮回C字符串。用链表将不合的计较项存储到链表中。然后在停止轮回求值。若是碰着括号就递归挪用。回忆并清算了一下当初的思绪大抵如下。
1.输入 3+5*(2-6)/2
2.解析为
3.计较 经由过程两次轮回对不合优先级进交运算得出成效
第一次对*/停止计较,拿当前节点,和节点的next节点,求值后将值赋给next节点,并删除本身节点
第二次对+-停止求值,直到碰着end
最后也筹算按这个思绪去实现的,之后创造解析的轨范会斗劲复杂,涉及到屡次的字符串搜索,比对。再加上C本身不支撑正则表达式,所以就抛却了当初的思绪。找了一些相干的质料后创造了一种更简单也更科学的编制,那就是将输入转换成后缀表达式再停止求值,这后缀表达式现实是什么呢,请继续看下去。
一、后缀表达式
百度百科引见: 不包含括号,运算符放在两个运算工具的后面,所有的计较按运算符出现的挨次,严格从左向右停止(不再考虑运算符的优先轨则,如:(2 + 1) * 3 , 即2 1 + 3 *
体味了后缀表达式才晓得,本来我们习觉得常的数学表达式被称之为中缀表达式。花了点时辰研究了一下创造后缀表达式的计较还蛮简单的,也更适宜计较机运算。
计较编制,从左往右停止计较。取运算符号前两位数字进交运算,运算成效替代运算符以及前两位数字,连续运算到最右边得出成效。
这么说起来可能斗劲难理解,我们看几个例子
最简单的 21+
计较过程为 2 + 1 = 3
值为 3
通俗的 325-2*+
计较过程 从左往右先计较 2-5=-3,-3庖代前面的25-之后为 3-32*+,完好的计较轨范如下
计较2-5=3 计较完之后表达式为 3 -3 2 *+
计较-3*2=-6 计较完之后表达式为 3 -6 +
计较3+-6=-3 计较完之后表达式为 -3
值为 -3
略微复杂一点的 21+3*5387-/*-
计较过程 从左往右先计较 2+1 = 3,4庖代前面的21+之后为 33*5387-/*- 完好的计较轨范如下
计较2+1=3 计较完之后表达式为 3 3 *5 3 8 7 -/*-
计较3*3=9 计较完之后表达式为 9 5 3 8 7 -/*-
计较8-7=1 计较完之后表达式为 9 5 3 1 /*-
计较3/1=3 计较完之后表达式为 9 5 3 *-
计较5*3=15 计较完之后表达式为 9 15 -
计较9-15=-6 成效为 -6
值为 -6
看完了以上成效,我们会创造每一次介入计较的数字,都是最接近运算符号的两位数字。然后由运算出来的成效庖代介入运算的数字和运算符,直到表达式只剩下一个值,计较完成。
按照如许的纪律,轨范措置起来就简单了。
1.从左往右的轮回整个输入。
2.断定是否是数字,若是是数字就保留起来。若是碰着符号,则把保留的前两个值掏出来,计较后把本次计较成效存回去
3.轮回完成之后,剩下的表达式便是计较成效了
按照如上轨则不难创造每次介入计较的两个数字都是末了存进去的,如许一来我们便可以用栈轻松的完成如许一个轨范了,下面跟大师简单引见一下栈。
二、栈
百度百科的诠释斗劲复杂,就不摘抄了。其实栈可以简单的理解为一个存放数据的空间,数据按照后进先出的准绳停止存取。对数据的把持有push和pop,分袂称之为压入,弹出。
由于斗劲简单,所以直接用代码实现了一个简单的栈,包含如下四个编制。
简单的停止测试,输入成效为
item is : 1.120000
item is : 2.800000
2.800000
1.120000
实现了预期输出,一个简单的栈就搞定了,接下来就可以把持整个简单的栈来完成求值的函数了。
三、后缀表达式求的详细实现
由于栈已经实现了,所以只必要按照后缀表达式求值的逻辑进交运算在配合栈就可以实现整个计较过程了。编制斗劲简单,用while轮回整字符串,在配合switch对数字和运算符做不合的措置就可以完成一个简单的后缀表达式求值函数了。以下是第一版的实当代码
在第一个版本的过程中,碰着一个C说话知识点是 C说话的字符串指针指向的地点是字符串第一个字符的地点。
所以当i为0的时辰,&str[i] = &str, atof 领受的是一个字符串指针,若是使用 STACKpush(atof(&str[i])),i为0时,会将整个字符串传入进去转换。接纳了一个char变量,讲str[i]拷贝出来,然后传入&num,则可以处理这个问题。
其实这段轨范里还涉及到一个指针运算的知识点,可是这里的轨范里涉及还斗劲简单易懂,后续还有更难的地方涉及到这个知识点,所以先放到后面再跟大师分享。
对上面的编制停止了测试,输入我们之前分析的三个表达式,得出成效如下
printf("%f ", calculate("21+")); //3
printf("%f ", calculate("325-2*+")); //-3
printf("%f ", calculate("21+3*5387-/*-")); //-6
测试经由过程,跟之前的计较成效不息。以上便是一个简单的后缀表达式的计较轨范了。停止了多几回的测试创造了一个小问题,就是今朝无法停止多位数的识别。由于轨范没一次都将一位数压入站内了。思虑了一下在表达式的每个计较项上加了一个空格符作为数字的区分。变为 21 3 +这种情势,于是脱手将代码做了一点小改动
在 switch 中参加了对空格的措置,以及多位数的措置
//若是碰着空格,则重置标识表记标帜位
这些是C/C++能做的
服务器开发工程师、人工智能、云计算工程师、信息安全(黑客反黑客)、大数据 、数据平台、嵌入式工程师、流媒体服务器、数据控解、图像处理、音频视频开发工程师、游戏服务器、分布式系统、游戏辅助等
标签: #c语言栈实现表达式求值