美文网首页
后缀表达式

后缀表达式

作者: su9257_海澜 | 来源:发表于2021-01-11 01:12 被阅读0次

    平常我们所用的标准四则运算表达式,如:29+3-2(10-3)/5,叫做中缀表达式,今天介绍一种不需要括号的后缀表达法,我们也把它称为逆波兰(Reverse Polish Notation ,RPN)表示。后缀表示式为栈数据结构的一种应用。

    • 中缀表达式: 2 * 9 + 3 - 2 * (10-3) / 14
    • 后缀表达式: 2 9 * 3 + 2 10 3 - * 14 / -

    其中上面的中缀表达式和后缀表达式等价。

    后缀表达式遵循以下规则
    1. 从左到右遍历中缀表达式的每一个数字和符号。
    2. 若是数字就输出,即成为后缀表达式的一部分。
    3. 如果是符号,则判断其与栈顶符号的优先级,是右括号已有栈顶符号优先级(乘除优于加减)大于等于此符号则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。
    现在演示 2 * 9 + 3 - 2 * (10-3) / 142 9 * 3 + 2 10 3 - * 14 / - 转换的过程
    1. 第1个符号为数字,所以输出 2


      file
    2. 第2个符号为 * ,因为目前栈为空栈,所以直接进栈


      file
    3. 第3个符号为数字 ,输出9,现在为 2 9


      file
    4. 第4个符号为 + ,目前栈顶符号 * 优先级大于等于 + ,所以出栈并输出 + 符号进栈,现在的总输出为 2 9 *


      file
    5. 第5个符号为 3 ,输出 3,现在为 2 9 * 3


      file
    6. 第6个符号为 - ,栈顶符号 + 优先级大于等于 - ,所以 + 出栈输出 - 进栈,现在为 2 9 * 3 +


      file
    7. 第7个符号为 2 ,输出 2 ,现在为 2 9 * 3 + 2


      file
    8. 第8个符号为 * ,栈顶符号 - 优先级不大于等于 * ,所以 * 直接进栈,现在为 2 9 * 3 + 2


      file
    9. 第9个符号为( ,直接进栈,现在为 2 9 * 3 + 2


      file
    10. 第10个符号为 10 ,输出10,现在为 2 9 * 3 + 2 10


      file
    11. 第11个符号为- ,栈顶元素为(,直接进栈,现在为 2 9 * 3 + 2 10


      file
    12. 第12个符号为3 ,输出3,现在为 2 9 * 3 + 2 10 3


      file
    13. 第13个符号为) ,此时我们需要匹配左括号(,依次出栈直到找到左括号位置,现在为 2 9 * 3 + 2 10 3 -


      file
    14. 第14个符号为/ ,栈顶元素为*,优先级大于等于 / ,所以 /出栈 *进栈,现在为 2 9 * 3 + 2 10 3 - *


      file
    15. 第15个符号为 14 ,此时中缀表达式已经没有需要运算数字,所以栈中的符号依次出栈,现在为 2 9 * 3 + 2 10 3 - * 14 / -


      file
    以上就是中缀表达式转化为后缀表达式的全过程,后缀表达式的计算结果遵循如下规则
    • 从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号就将处于栈顶两个数字出栈,进行运算,运算的结果再进栈,以此类推直到得到最终结果。

    以下为演变示例图

    file file file file file file file file file
    最终出栈得到计算结果 20 。

    更多文章详见博客主页:https://aihailan.com/

    相关文章

      网友评论

          本文标题:后缀表达式

          本文链接:https://www.haomeiwen.com/subject/fedraktx.html