关于算法:22张图带你深入剖析前缀中缀后缀表达式以及表达式求值

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

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

表达式求值这是一个比拟经典的计算机系统根底问题，然而整个过程比拟形象，本文次要通过图解的办法帮忙大家了解这个问题。

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

咱们常见的数学表达式就是中断表达式，比如说：$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<Integer> 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();}
}

本文次要给大家介绍了如何将中断表达式转化成后缀表达式，以及代码依据后缀表达式求值。本文所谈到的问题可能绝对于其余问题来说逻辑上可能更加简单，须要大家本人浏览和依据文字和图进行了解。

以上就是本文所有的内容了，心愿大家有所播种，我是 LeHung，咱们下期再见！！！（记得点赞珍藏哦！）

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。

关于算法:22张图带你深入剖析前缀中缀后缀表达式以及表达式求值

深刻分析前缀、中断、后缀表达式以及表达式求值

前言

表达式介绍

中断表达式

后缀表达式

前缀表达式

表达式之间转化的例子

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

后缀表达式求值

代码实现

总结