解析算术表达式[3]扩展与延伸

在之前的文章中,我们已经实现了输入一个四则运算表达式(即只包含加减乘除和括号的表达式)的字符串,然后求出其运算结果的功能。整个过程的算法是非常明确,而且并不复杂,包括转换及求值,算法的时间复杂度为O(N),事实上,如果我们在字符一个个读入的时候同时进行转换求值,也是可以的。在实现了四则运算后,这样的程序几乎就可以作为一个比较“智能”的计算器的后台了(这时候我们输入2+3*4,得到的结果不会再是20,而是会得到正确的结果14),但是这样并不能使我们满足,我们所实现的四则运算,实在太简单,而如果想计算更为复杂的表达式,仅仅通过这四种运算,就显得力不从心了。这篇文章,作为解析算术表达式的最后一篇,我想主要来延伸讨论下面几个问题: 1.四则运算属于左结合的运算符,那么对于右结合的运算符,能否很好的加入进来呢?比如“^”这样的幂指运算符(对于习惯C语系的童鞋来说,a ^ b这样的运算等效于pow(a, b)),至于左结合和右结合的区别,稍后会在下文中谈到。 2.能否加入函数运算,让表达式支持sqrt(a+b)+c

解析算术表达式[2]计算求值

不知道有没有人看了上一篇文章后会有疑问,为什么转换后的表达式要存入表达式栈中呢?虽然在调试器中可以清楚的看到表达式被成功转换了,但如果想要输出的话,岂不是就是倒序了?其实我是在这部分埋下了一个小小的伏笔,我们转换为后缀表达式,是为了计算机能够计算我们输入的“字符串”形式的中缀表达式,而通过后缀法计算,也是要利用栈的,这次,我们还是用图来说话,以计算 1, 2, 3, 4, +, 5, *, +, 6, +, * 这个已经转化好的后缀表达式为例: 1.读入数字入栈 2.然后读入了一个运算符+,这时候就弹出栈中的两个数字,进行加法运算,然后再压回 3.还是继续读入数字 4.此时读入了运算符*,弹出两个数字,进行乘法运算,然后压回 5.再次读入一个加法运算符,弹出两个数字,进行加法运算,然后压回 6.读入数字 7.读入运算符加法,弹出两个数字,进行加法运算,然后压回 8.最后读入乘法运算符,将栈内最后两个数字弹出,进行乘法运算,压回。至此...

解析算术表达式[1]后缀式(逆波兰式)

解析算术表达式[1]后缀式(逆波兰式)
后缀(postfix, 也成逆波兰 reverse Polish)表达式在我们的生活中并不常见,在我们日常中见到的,通常都是中缀(infix)式,例如: 3.14 + 15 * (9.2 – 6.5) 这是便于人类理解的表达式,之所以便于人类理解,是因为人从小便接受识别此类表达式的教育,而且这种记号方式将运算符和数字明确的分开,不会产生数字堆叠在一起的混乱情况。 但是对于计算机而言,这样的表达式并不好理解,计算机是一种线性读入信息,线性输出信息的工具,人类所通识的中缀式,对于这种规规矩矩按照顺序计算的工具而言,是不容易理解的。你可能一眼就看出来要先算小括号里的表达式,然后算乘法,最后算加法。而计算机直接读入的话,可能会先算3.14 + 15,这自然是荒谬的,而后缀法就为计算机计算表达式提供了一种非常有效的解决方案。这篇文章主要的内容是介绍如何将中缀表达式转换为后缀表达式。 说了这么半天,后缀表达式又是什么样子呢?它又有什么样的优势呢? 我们现在来看一组对比: 后缀表达式为什么会有优势呢?因为...

栈(stack)是一种数据结构,它遵循一个简单的规则,即后进先出(Last in First out, LIFO)。 栈的工作方式很容易理解,用一个图表形象的表示就是这样,见图1: 这个只有上端开口的容器,就是用来存放数据的栈,我们要取容器中的东西,必须从最顶端开始,一个一个拿掉,才能取到我们想要的,而如果要放一个元素呢,也只能放在最顶端,这也就是栈的后进先出原则。 这样的数据结构可以使用C++标准库来实现,非常简单,下面就对C++标准库中的栈做一点简介: C++提供了三种顺序容器(sequential container)vector(支持快速随机访问)、list(支持快速插入删除)、deque(双端队列),vector比较类似与数组,而list则更加像链表结构。C++标准库为顺序容器提供了三种容器适配器(adaptor), 不要被名字吓到,所谓适配器,就像你的电脑电源适配器一样,将交流电(这里是顺序容器)做出一定的调整,来适合电脑工作,也就是说,容器适配器,是利用容器来...