宝、⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

后缀表达式是栈的运用,如果你还不知道栈是什么,那请你先去看看关于栈的文章

文章目录

  • 一、什么是后缀表达式
  • 二、后缀表达式的运算顺序
  • 三、中缀表达式
  • 四、中缀表达式转化为后 缀表达式



一、什么是后缀表达式

后缀表达式是一种不需要括号的表达式。

对于四则运算,我们用括号来规定了它的运算顺序。

但是在早些年对于计算机,并没有括号来规定其运算顺序。

当没有了括号 比如想要输入 9+(3-1)x3+10/2 当没有了括号会怎么样呢,

总不能像这样:9+3-1x3+10/2 输入吧

那么伟大的科学家是怎么来解决四则运算顺序的呢?

20世纪50年代 波兰逻辑学家Jan Lukasiewicz 发明了一种没有括号的表达式(后缀表达式)

来解决这个问题,之所以叫后缀表达式 是因为所有的运算符号都要在数字后面出现才行;

二、后缀表达式的运算顺序

先给出一个后缀表达式吧如

四则表达式:9+(3-1)x3+10÷2

后缀表达式:9 3 1 - 3 x + 10 2 / +

相信你一定蒙圈了

我们先把四则表达式的结果算出来 我想想是多少呢

哦原来是20!(我太聪明了)

四则表达式显然不需要多bb

那后缀表达式是怎么算的呢

那显然就需要引用最开始说的栈了

因为后缀表表达式本来就是栈的一种应用

那么现在来说说后缀表达式的规则

先从左到右依次入栈

当是数字的时候直接入栈

当是运算符号的时候

就将栈的最上面两个数拿出进行运算 后 再将结果进栈 记住(栈顶元素永远在运算符号的右边)

 那现在我们来算

后缀表达式:9 3 1 - 3 x + 10 2 ÷ +

 第一步从左到右依次入栈 9 3 1

 现在栈从上到下1 3 9   进入符号 -   将1和3 拿出  3-1  =2 

栈顶元素永远在运算符号的右边

然后再把2进栈

现在栈从上到下是 2 9 

再进入3

现在栈从上到下是 3 2 9

再运算符号 x 拿出 2x3 =6 再进栈

现在栈从上到下是 6 9

在运算+ 6+9=15

现在栈从上到下是 15

后缀表达式:9 3 1 - 3 x + 10 2 ÷ +

进入 10  2

现在栈从上到下是 2 10 15

运算 ÷  10÷2=5 5 进栈

现在栈从上到下是 5 15

最后运算+  15+5

得20

最后20出栈

(累了)

后缀表达式:9 3 1 - 3 x + 10 2 ÷ +   =20

三、中缀表达式

啊??就是四则运算表达式 宝

 

四、中缀表达式转化为后缀表达式

相信看了前面的规则后,这个你应该也不难理解了

直接上规则:

9+(3-1)x3+10÷2

后缀表达式从左到右遍历,

1,是数字直接写上

2,是任何运算符号

①右括号----) 和优先级 不高于 栈顶元素 则 栈顶元素依次输出 并当前符号进栈(括号直接消失) 

好吧我知道你又麻了

直接诉说好吧,

中缀表达式 9+(3-1)x3+10÷2

从左到右

9 写上

当前表达式为 9

+ 入栈(目前栈空,栈空就进栈)

(     入栈

 目前栈里从上到下:(  +

3写上

当前表达式为 9  3

-  入栈

 目前栈里从上到下:-(  +

中缀表达式 9+(3-1)x3+10÷2

1写上

当前表达式为 9  3  1

)右括号 遇到右括号 输出栈顶元素 并抵消左括号

写上  -

当前表达式为 9 3 1 -

当前栈从上到下 +

中缀表达式 9+(3-1)x3+10÷2

x 优先级高于+ 直接入栈

3写上

当前表达式 9 3 1 - 3

当前栈从上到下 x +

接下来 +  判断优先级 +优先级小于x   x 出栈写上表达式

判断优先级  + 和+ 相同  属于 不高于  + 出栈 写上表达式  后面的+ 入栈

 当前表达式  9 3 1 - 3  x +

再后面 10 写上表达式

÷ 判断优先级 高于+  进栈

2 写上

当前表达式 9 3 1 - 3 x + 10  2

当前栈从上到下 ÷ +

由于已经没有符号和数字了

栈内依次出栈并写入表达式

最后得出 9 3 1 - 3 x + 10  2  ÷ +


总结

宝 你懂了没我纯文字描述真的很莽 (主要是我不会作图)以后会优化的,另外有错误一定要评论指出,我最怕 我一个人在这里乱bb 没人告诉我,我就淦了。另外这是参照大话数据结构写的。、大家要学数据结构建议买本书系统的学习

祝你越来越久,不要关注我(疯狂暗示)

爱你

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐