数据结构与算法——栈(三)有关栈的三种表达式 —— 前缀、中缀、后缀表达式

三种表达式 —— 前缀、中缀、后缀表达式

前缀表达式(波兰表达式)

前缀表达式又称为 波兰表达式,前缀表达式的 运算符位于操作数之前

例如:( 2 + 3 ) × 4 – 5 对应的前缀表达式为:- × + 2 3 4 5

注意:前面这个表达式是一个中缀表达式,对应的是后面的这个前缀表达式。它的符号出现的顺序与中缀的顺序不一致。

前缀表达式中的符号顺序,就是他求值的规定了

前缀表达式求值过程

  1. 右到左 扫描表达式

  2. 遇到 数字 时,将数字压入堆栈

  3. 遇到 运算符

    1)弹出栈顶的两个数(栈顶和次顶),用运算符对它们做相应的计算,并将结果入栈。

    ? 计算顺序是: 弹出来的 (运算符) 弹出来的

然后重复以上步骤,直到表达式的最左端,最后运算出的值则是表达式的值。

看完前缀表达式的计算逻辑,那么你要明白的是,从一个 中缀表达式 转换为 前缀表达式 时,优先级顺序是已经处理好的,因为在求值时,不进行优先级的判定

例如:(3+4)x5-6 对应的前缀表达式为:- x + 3 4 5 6,前缀表达式求值步骤如下:

  1. 从右到左扫描,将 6、5、4、3 压入栈

  2. 遇到 + 运算符时:

    将弹出 3 和 4(3 为栈顶元素,4 为次顶元素),计算出 3 + 4 = 7,将结果压入栈

  3. 遇到 x 运算符时

    将弹出 7 和 5,计算出 7 x 5 = 35,将 35 压入栈

  4. 遇到 - 运算符时

    将弹出 35 和 6,计算出 35 - 6 = 29,压入栈

  5. 扫描结束,栈中留下的唯一一个数字 29 则是表达式的值

中缀表达式

中缀表达式就是 常见的运算表达式,如 (3+4)x5-6

中缀表达式的求值是人类最熟悉的,但是对于计算机来说却不好操作:

  • 需要计算运算符的优先级
  • 处理括号优先级

因此,在计算结果时,往往会将 中缀表达式 转成其他表达式,一般转成后缀表达式

后缀表达式(逆波兰表达式)

后缀表达式 又称为 逆波兰表达式,与前缀表达式类似,只是 运算符 位于 操作数之后

比如:(3+4)x5-6 对应的后缀表达式 3 4 + 5 x 6 -

再比如:

中缀表达式 后缀表达式
a + b a b +
a + (b-c) a b c -
a+(b-c)*d a b c - d * +
a+d*(b-c) a d b c - * +
a=1+3 a 1 3 + =

后缀表达式求值过程

  1. 左到右 扫描表达式

  2. 遇到 数字 时,将数字压入堆栈

  3. 遇到 运算符

    弹出栈顶的两个数(栈顶和次顶),用运算符对它们做相应的计算,并将结果入栈。

    计算顺序是: 弹出来的 (运算符) 弹出来的

    同样的也不用考虑符号优先级的问题

然后重复以上步骤,直到表达式的最右端,最后运算得出的值即为表达式的结果。

比如:(3+4)x5-6 对应的后缀表达式 3 4 + 5 x 6 -

  1. 从左到右扫描,将 3、4 压入堆栈

  2. 扫描到 + 运算符时

    将弹出 4 和 3,计算 3 + 4 = 7,将 7 压入栈

  3. 将 5 入栈

  4. 扫描到 x 运算符时

    将弹出 5 和 7 ,计算 7 x 5 = 35,将 35 入栈

  5. 将 6 入栈

  6. 扫描到 - 运算符时

    将弹出 6 和 35,计算 35 - 6 = 29,将 29 压入栈

  7. 扫描表达式结束,29 是表达式的值,由此得出最终结果

数据结构与算法——栈(三)有关栈的三种表达式 —— 前缀、中缀、后缀表达式

上一篇:常见面试题:HashMap线程不安全怎么办?


下一篇:【Java】Linux 系统安装 JDK