您的位置 首页 > 娱乐休闲

你知道计算机是怎么计算加减乘除算式的么? 后缀表达式在线转换

说到加减乘除运算,只要学过乘法口诀的应该没有不会算的吧。

什么一一得一,一二得二.。。。信手拈来,简直不要太容易。

难一点的无非也就是这四种运算符号组合起来而已,但是如此简单的运算对于计算机而言,真的不是一件轻松的活啊。

就运算速度上,计算机远超你我。

就运算简易程度而言,你我胜过计算机。

为什么这么说呢?

下面举个栗子,求一个算式(也叫中缀表达式)结果:5+(6-3)*4+8/2=?

对于我们而言,这个算式轻松的得到答案是21。那么计算机,又是如何得出这个结果的呢?

谈到这个问题,首先我们应该了解两个知识:栈(stack)和后缀表达式。

  • 什么是栈?

    栈又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

    可以这么理解栈:栈相当于一个没有瓶盖的空瓶子。向瓶子内放入东西叫做入栈,从瓶子里倒出东西叫做出栈。瓶底叫栈底,瓶口叫栈顶。虽然不是很恰当,但是这么理解还是可以的。

  • 什么是后缀表达式?

    后缀表达式也叫逆波兰式。它是波兰的逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面,例如,把a+b写成ab+,所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算,不需要使用括号,也便于用械实现求值。对于表达式x:=(a+b)*(c+d),其后缀式为xab+cd+*:=。

计算机对上述运算表达式的过程大致分为两个步骤:

①将中缀表达式转换为后缀表达式

②通过执行后缀表达式得出结果

首先介绍转换为后缀表达式的过程。转换的过程中遵循一个规则(符号进栈,数字输出):

  • 从左到右遍历中缀表达式的每个数字和符号

  • 如果是数字就加入后缀表达式

  • 如果是符号,判断括号:如果是左括号“(”,直接入栈;是右括号“)”,则依次从栈中取出运算符加入后缀表达式中,直至取到“(”后停止,并且将栈中“(”删除

  • 如果是括号以外的其他运算符,判断这个运算符和栈顶符号优先级:其优先级低于或者等于栈顶符号则先将栈中符号依次弹出加入后缀表达式后自身入栈,否则自身就直接入栈

  • 直到遍历中缀表达式结束,得到后缀表达式

详细过程:

  • 将5输出,+进栈; 目前输出为5,栈中为+;

  • 遇到(,进栈; 目前输出为5,栈底到栈顶依次为+ (;

  • 将6输出,减号进栈,3输出; 目前输出为5 6 3,栈底到栈顶依次为+ (-;

  • 遇到),去匹配(,栈顶符号出栈,直到(出栈; 目前输出为5 6 3-,栈中为+;

  • 遇到乘号进栈,6输出;目前输出为5 6 3 - 4,栈底到栈顶依次为+ *;

  • 遇到+,由于+的优先级比*低,所以栈中所有元素都出栈,自身进栈; 目前输出为5 6 3 - 4 * +,栈底到栈顶依次为+;

  • 遇到10输出,除号进栈;目前输出为5 6 3 - 4 * + 8,栈底到栈顶依次为+/;

  • 遇到2输出;目前输出为5 6 3 - 4 *+ 8 2,栈底到栈顶依次为+/;

  • 表达式结束,栈中全部依次出栈,最终为5 6 3 - 4 * + 8 2 / +;

其次是后缀表达式的执行过程。其执行过程也遵循一个规则:

  • 从左向右遍历后缀表达式的每个数字和符号,

  • 遇到是数字就进栈

  • 遇到是符号,就将处于栈顶两个数字出栈,三者进行运算得到的运算结果进栈, 直到最后获得运算结果

  • 5 6 3 依次进栈,然后遇到了减号;此时栈底到栈顶依次为5 6 3;

  • 处于栈顶的3和6出栈,相减得到3,将3进栈;此时栈底到栈顶依次为5 3;

  • 4进栈,然后遇到乘号;此时栈底到栈顶依次为5 3 4;

  • 处于栈顶的4和3出栈,相乘得到12,将12进栈;此时栈底到栈顶依次为5 12;

  • 遇到加号,处于栈顶的12和5出栈,加一下得到17,将17进栈;此时栈里只有一个17;

  • 8 2依次进栈,然后遇到除号;此时栈底到栈顶依次为17 8 2;

  • 处于栈顶的2和8出栈,相除得到4,将4进栈;此时栈底到栈顶依次为17 4;

  • 遇到加号,处于栈顶的4和17出栈,想加得到21,将21进栈;

  • 表达式结束,输出结果21,栈变空。

看完感觉怎样?

是不是很复杂?

其实还好吧,233。。。

有的小伙伴可能又要吐槽了,知道这些过程有个屁用,实际工作中会让你写这个过程么?

是的,工作可能不需要你了解底层如何计算,你需要告诉计算机这些数字和运算符,剩下的就等着拿到结果就ok。

我想说,编程重要的不是你能不能完成单纯的开发任务,而是你能不能从任务中看到背后的编程思想。

思想决定高度!

思想有多远,你就能走多远~~~~~~~~

责任编辑: 鲁达

1.内容基于多重复合算法人工智能语言模型创作,旨在以深度学习研究为目的传播信息知识,内容观点与本网站无关,反馈举报请
2.仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证;
3.本站属于非营利性站点无毒无广告,请读者放心使用!

“如何转换后缀表达式,转换后缀表达式数据结构,表达式转换为后缀表达式,中缀表达式转换为后缀表达式”边界阅读