后缀表达式

elizapeden8450 云计算/大数据 1 次浏览 没有评论

对于一个算术表达式我们的一般写法是这样的

(3 + 4) × 5 – 6

这中写法是中序表达式
后序表达式则是将运算符放在操作数的后面,如

3 4 + 5 × 6 –

可以看出后序表达式中没有括号, 只表达了计算的顺序, 而这个顺序恰好就是计算器中的一般计算顺序。

运用后缀表达式进行计算的具体做法:

建立一个栈S 。从左到右读表达式,如果读到操作数就将它压入栈S中,如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算,再将运算的结果代替原栈顶的n项,压入栈S中 。如果后缀表达式未读完,则重复上面过程,最后输出栈顶的数值则为结束。

例 : 6 5 2 3 + 8 * + 3 + *

  • 先将前面的数字入栈

    栈 :6 5 2 3

  • 遇到 ” + ” 取栈顶的两个操作数做加法, 2 + 3 = 5 , 入栈

    栈 :6 5 5

  • 遇到 ” 8 ” 入栈

    栈 :6 5 5 8

  • 遇到 ” * ” 取栈顶的两个操作数做乘法, 5 * 8 = 40 , 入栈

    栈 :6 5 40

  • 遇到 ” + ” 取栈顶的两个操作数做加法, 5 + 40 = 45 , 入栈

    栈 :6 45

  • 遇到 ” 3 ” 入栈

    栈 :6 45 3

  • 遇到 ” + ” 取栈顶的两个操作数做加法, 45 + 3 = 48 , 入栈

    栈 :6 48

  • 遇到 ” * ” 取栈顶的两个操作数做加法, 6 * 48 = 288 , 入栈

    栈 :288

从中序表达式 转换为 后序表达式

由于后续表达式更易计算机去解决,所以我们在运算算术表达式时要先转换为后序的。方法如下

  1. 建立符号栈
  2. 顺序扫描中序表达式
    a) 是数字, 直接输出
    b) 是运算符
    i : “(” 直接入栈
    ii : “)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出
    iii: 其他符号, 将符号栈中的元素依次出栈并输出, 直到 遇到比当前符号优先级更低的符号或者”(“。 将当前符号入栈。
  3. 扫描完后, 将栈中剩余符号依次输出

例 : 3+(2-5)*6/3

  • 遇到 3 是数字输出

表达式 : 3
符号栈 :

  • 遇到”+” 号 , 利用法则iii ,栈中没有优先级更低的符号, 直接入栈

表达式 : 3
符号栈 : +

  • 遇到”(” , 利用 法则i, 直接入栈

表达式 : 3
符号栈 : + (

  • 遇到”2” 输出

表达式 : 3 2
符号栈 : + (

  • 遇到 “-” , 利用法则iii , 遇到”(“, 没有出栈符号, 直接入栈

表达式 : 3 2
符号栈 : + ( –

  • 遇到”5” 输出

表达式 : 3 2 5
符号栈 : + ( –

  • 遇到”)” 利用法则ii , 将”-“号出栈输出, “(” 出栈

表达式 : 3 2 5 –
符号栈 : +

  • 遇到”*” 利用法则ii , “*” 比”+”的优先级低, 所以遇到优先级更低的符号, 不用出栈, 将”*”入栈
    表达式 : 3 2 5 –
    符号栈 : + *
  • 遇到”6” 输出

表达式 : 3 2 5 – 6
符号栈 : + *

  • 遇到”/” 利用法则ii , “/” 与”*”的优先相同, 就是说”*”不是优先级更低的符号, 所以出栈输出, 继续 “+”比”/”的优先级低, 不用出栈, 将”/”入栈

表达式 : 3 2 5 – 6 *
符号栈 : + /

  • 遇到”3” 输出

表达式 : 3 2 5 – 6 * 3
符号栈 : + /

  • 扫描完成 将符号栈内的符号依次输出

表达式 : 3 2 5 – 6 * 3 / +

内容如有侵犯你的权益,请联系删除

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Go