22张图带你深入剖析前缀、中缀、后缀表达式以及表达式求值

createh52个月前 (02-01)技术教程14

前言

在本篇文章当中主要跟大家介绍以下几点

  • 前缀、中缀和后缀表达式。
  • 如何将中缀表达式转化成后缀表达式。
  • 如何使用后缀表达式进行求值。

表达式求值这是一个比较经典的计算机系统基础问题,但是整个过程比较抽象,本文主要通过图解的方法帮助大家理解这个问题。

表达式介绍

后缀表达式也称作逆波兰表达式,前缀表达式也称作波兰表达式,这个是因为这是由波兰数学家杨-武卡谢维奇提出来的,用于简化命题逻辑的一种方法。

中缀表达式

我们常见的数学表达式就是中缀表达式,比如说:1+2,像这种我们从小到大经常见到的表达式就叫做中缀表达式,这个表达式的特点就是将运算符(加减乘除)放在两个操作数(数字)中间。

后缀表达式

后缀表达式和中缀表达式的最大区别就是,他不是将运算符放在操作数中间,而是将运算符放在操作数后面,比如上面的中缀表达式1+2转化成后缀表达式就为12+。

前缀表达式

前缀表达式就是将运算符放在操作数的前面,比如上面的中缀表达式1+2转化成前缀表达式之后为+12。

表达式之间转化的例子

上面的表达式还是比较简单,可能不足以帮助大家好好理解表达式之间的转化过程。

中缀表达式:A+B?(C?D)?E/F

现在我们来将上面的中缀表达式转化成后缀表达式,我们的第一个计算的部分如下(括号里面的优先计算):

根据我们的转化原理:将运算符放在操作数后面,

上面的得到的后缀表达式继续进行转化(现在需要计算B乘以后面的那个部分):

继续进行转化(从左往后进行计算):

继续进行转化(除法的优先级比减法高):

得到最终的结果:

程序如何将中缀表达式转化成后缀表达式

将中缀表达式转化成后缀表达式有以下几条规则(下面的栈是存储操作符的栈,而且只存储操作符):

  • 从左到右进行遍历。
  • 遇到操作数,直接加入到后缀表达式当中。
  • 遇到界限符。遇到“(”直接入栈,遇到“)”则依次弹出栈内运算符并加入后缀表达式,直到弹出“(” 为止,注意:“(” 不加入后缀表达式。
  • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到“(”或栈空则停止。之后再把当前运算符入栈。

现在我们根据上面的规则来将上文当中的中缀表达式转化成后缀表达式。

  • 遍历到A,根据第二条规则,将A加入到后缀表达式当中,当前的后缀表达式为:A。
  • 现在遍历到加号,根据前面的规则需要弹出栈里面优先级大的运算符,再将加号加入到栈中,当前的后缀表达式为A。
  • 遍历到B,直接加入到后缀表达式当中,目前的后缀表达式为AB。
  • 遍历到?,根据规则直接将其加入到栈中,当前后缀表达式为AB。
  • 遍历到(,根据规则直接将其加入到栈中,当前后缀表达式为AB。
  • 遍历到C,则直接将其加入到后缀表达式当中,当前后缀表达式为ABC。
  • 遍历到?,根据规则将其加入到栈中,当前后缀表达式为ABC。
  • 遍历到D,则将其直接加入到后缀表达式当中,当前的后缀表达式为ABCD。
  • 遍历到),则需要将栈中的符号弹出,直到遇到(,当前的后缀表达式为ABCD?。
  • 遍历到?,需要将栈中优先级大于等于?的运算符弹出,则当前的后缀表达式为ABCD??+,再将?压入栈中。
  • 遍历到E,直接将数字加入到后缀表达式当中,则当前的后缀表达式为ABCD??+E。
  • 遍历到/,将栈中优先级大于等于/的运算符,再将/压入到栈中,当前的后缀表达式为ABCD??+E。
  • 遍历到F,直接将其加入到后缀表达式当中,则当前的后缀表达式为ABCD??+EF。
  • 最终将栈中所有的运算符都弹出,得到的后缀表达式为ABCD??+EF/?。

经过上面的过程就可以将一个中缀表达式转成后缀表达式了,大家如果想要代码实现,只需要在遍历数据的时候根据上面四个规则一个个进行判断即可,程序并不困难,就是逻辑稍微有点多,需要考虑更多的问题,在写代码的时候需要细致一点。

后缀表达式求值

在前文当中我们已经得到了表达式A+B?(C?D)?E/F的后缀表达式为ABCD??+EF/?。现在我们需要将这个后缀表达式进行求值。根据后缀表达式求值主要有以下两条规则:

  • 如果遇到数字直接将其加入到数字栈。
  • 如果遇到操作符直接从操作数栈弹出两个数据进行对应的运算,再将运算结果加入到栈中。

现在我们进行后缀表达式的求值过程;

  • 首先前面四个ABCD都是数字,根据上面提到的第一条规则,我们都需要将数字压入到栈当中,因此遍历四个数字之后,情况如下:
  • 现在遍历到?,我们需要将D和C弹出,然后进行?操作的运算,再将结果压入栈中。
  • 现在遍历到?,我们需要将C?D=M和B弹出,进行乘法运算,然后将结果压入栈中。
  • 现在我们遍历到+,需要将栈中剩余的两个数弹出,进行加法运算,在将结果压栈。
  • 遍历EF都需要将这两个数压入到栈当中。
  • 现在遍历到/,需要进行除法运算,在将得到的结果压入到栈中。
  • 最后遍历到?,将栈中的两个数弹出栈,进行减法运算得到最后的结果。

相信经过上面过程你对后缀表达式求值的过程已经非常清楚了。

代码实现

LeetCode中有一道题就是根据后缀表达式求值——剑指 Offer II 036. 后缀表达式

根据 逆波兰表示法,求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:

输入:tokens = ["2","1","+","3","*"]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

输入:tokens = ["4","13","5","/","+"]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

上面问题的代码如下:

class Solution {  public int evalRPN(String[] tokens) {    Stack stack = new Stack<>();    for (String token : tokens) {      switch (token) {        case "+": {          int a = stack.pop();          int b = stack.pop();          stack.push(b + a);          break;        }        case "-": {          int a = stack.pop();          int b = stack.pop();          stack.push(b - a);          break;        }        case "*": {          int a = stack.pop();          int b = stack.pop();          stack.push(b * a);          break;        }        case "/": {          int a = stack.pop();          int b = stack.pop();          stack.push(b / a);          break;        }        default:          stack.push(Integer.parseInt(token));          break;      }    }    return stack.pop();  }}

总结

本文主要给大家介绍了如何将中缀表达式转化成后缀表达式,以及代码根据后缀表达式求值。本文所谈到的问题可能相对于其他问题来说逻辑上可能更加复杂,需要大家自己阅读和根据文字和图进行理解。

相关文章

好程序员Java教程分享Java的五大特点

好程序员Java教程为大家分享Java的五大特点希望对初学者有所帮助。一、Java的(六大)特点:1.简单性相对于c语言来说c语言的核心 指针(保存地址)*pJava中没有指针的概念(使用的是引用概念...

文件后缀,也称为文件扩展名,用于标识文件的类型

文件后缀,也称为文件扩展名,用于标识文件的类型,帮助操作系统确定使用何种程序来打开文件。这里列举一些常见的文件后缀名及其所代表的文件类型:? 文本文件:? .txt:纯文本文件? .doc、.docx...

给我5分钟,一次性给你讲明白Java中的序列化和反序列化

原文链接:https://mp.weixin.qq.com/s/QFG1ELITvChbtTjtk6u3OA序列化是一个经常见到但是又被很多人忽视的知识点,重要吗?重要,经常见吗?是的,那你会吗?不会...

代工到研发,我给康师傅做自动化码垛产线 | 中德制造业研修院

文 / 巴九灵前两天,苹果CEO库克称芯片短缺限制iPad和Mac销量的发言登上了热搜,在一溜奥运新闻中特别显眼。事实上,从年初起,半导体产业就隔三差五登上热搜,尤其当它与“华为”“中芯”“造车”等自...

OFD文件用哪些软件可以打开预览?(ofd文件怎样打开)

阅读OFD文件,可以使用在线预览,也可以把OFD文件转换成PDF文件预览,下面安利四款OFD在线阅读工具,有电脑端的也有手机端的,方便做财务和会计的朋友们去选择自己需要的工具使用电脑端1、WPS打开W...

Java 如何执行字节码?一文解析!(jvm执行字节码过程)

Windows 操作系统上编译的 Java 程序,不经过修改就能够直接在 Linux 操作系统上运行;与之对比的是 C 语言,在 Linux 平台编译的 C 程序,一般情况下如果不进行特殊的转换,那么...